La recherche binaire branchless la plus rapide

 (mhdm.dev)
1 points par GN⁺ 2023-08-13 | 1 commentaires | Partager sur WhatsApp
  • sb_lower_bound conserve la même interface que std::lower_bound et, lorsque la branche de comparaison est compilée en déplacement conditionnel (cmov), affiche des résultats jusqu’à 2× plus rapides qu’une recherche binaire classique
  • Le résultat des comparaisons d’une recherche binaire est souvent sujet aux échecs de prédiction de branche, car la position recherchée n’est pas connue à l’avance ; sur x86, l’option clang -mllvm -x86-cmov-converter=false aide à les réduire
  • Cette implémentation divise length par deux à chaque boucle et ne met à jour que first selon le résultat de la comparaison, ce qui réduit le nombre d’instructions ; dans l’intervalle 2^k <= n < 2^(k+1), elle effectue toujours k+1 comparaisons
  • Dans le benchmark clang -cmov, les temps d’exécution moyens étaient de 61,30 ns pour std::lower_bound, 33,24 ns pour sb_lower_bound et 32,73 ns pour bb_lower_bound ; les moyennes géométriques étaient respectivement de 39,17 ns, 19,81 ns et 21,33 ns, avec un écart important
  • Dans une recherche sur des chaînes de 8 octets, où la fonction de comparaison est lente, std::lower_bound était parfois légèrement devant ; sur de grands tableaux, une variante avec préchargement était en moyenne environ 2,3× plus rapide que std::lower_bound

Structure de base de sb_lower_bound

  • sb_lower_bound est une fonction C++ de même forme que std::lower_bound
    • Les entrées sont first, last, value, comp
    • La valeur de retour est l’itérateur de la position où la comparaison échoue pour la première fois ; si tous les éléments satisfont la condition, elle renvoie last
  • La boucle principale divise length par deux et ne déplace first vers l’avant que lorsque comp(first[length], value) est vrai
  • Ici, « branchless » ne signifie pas que le if disparaît, mais que ce if est compilé en instruction de déplacement conditionnel comme cmov, plutôt qu’en saut conditionnel
  • Avec clang, l’option -mllvm -x86-cmov-converter=false peut permettre de compiler cette forme en déplacement conditionnel

Là où std::lower_bound ralentit

  • Une recherche binaire classique compare l’élément du milieu avec value, puis choisit la partie gauche ou droite
  • Quand on ne connaît pas la position de l’élément recherché, if (comp(first[half], value)) devient facilement une branche difficile à prédire
  • Le CPU exécute à l’avance les instructions suivantes grâce à la prédiction de branche, mais si la prédiction est fausse, il doit jeter le travail déjà effectué
  • Avec un déplacement conditionnel, on peut choisir une valeur selon le résultat de la comparaison tout en réduisant les sauts conditionnels
  • clang -cmov peut aussi transformer certains if/else de std::lower_bound en déplacements conditionnels, ce qui l’a rendu environ 25 % plus rapide
  • gcc n’a pas de bonne option pour forcer le déplacement conditionnel dans cette situation, et sb_lower_bound n’émet pas non plus de code branchless actuellement, quel que soit le niveau d’optimisation

Une recherche « optimale » du point de vue du nombre de comparaisons

  • Ici, « optimal » désigne une recherche binaire qui minimise le nombre de comparaisons
  • Dans une liste de taille n, std::lower_bound peut produire n+1 résultats possibles : n positions d’éléments plus une position de fin
  • Si la taille de la liste est 2^k - 1, il y a 2^k résultats possibles et, chaque comparaison donnant 1 bit d’information vrai/faux, le nombre optimal de comparaisons est k
  • Dans les cas « nice » où la longueur vaut 2^k - 1, une recherche optimale est possible avec une boucle très courte
  • Si la longueur ne convient pas, un accès hors limites peut se produire, comme lorsque value vaut 4 dans [0, 1, 2, 3, 4, 5]

Caractéristiques de performance et contraintes de sb_lower_bound

  • Lorsque sb_lower_bound divise une plage de longueur paire, dans certains cas elle ne saute pas suffisamment d’éléments même si le résultat de la comparaison est vrai
  • Dans l’intervalle 2^k <= n < 2^(k+1), elle effectue toujours k+1 comparaisons
  • Dans le même intervalle, std::lower_bound effectue k ou k+1 comparaisons, avec environ log2(n+1) comparaisons en moyenne
  • Le nombre de comparaisons peut donc être plus élevé, mais le nombre d’instructions dans la boucle est bien plus faible, ce qui réduit le temps d’exécution global
  • Si la fonction de comparaison est très lente, l’écart entre k+1 et log2(n+1) comparaisons peut affecter les performances
  • Pour forcer le déplacement conditionnel avec gcc, on peut utiliser du cmov en assembleur inline spécifique à x86, mais l’approche simple augmente le nombre d’instructions et les alternatives nécessitent un assembleur distinct selon les types

La variante plus rapide bb_lower_bound

  • bb_lower_bound découpe d’abord la plage différemment jusqu’à obtenir une longueur de la forme 2^k - 1, puis effectue la recherche avec une seconde boucle rapide
  • length & (length + 1) sert à déterminer si la longueur est de la forme 11..1, c’est-à-dire 2^k - 1
  • Pour les longueurs non conformes, elle utilise une valeur MAGIC, auto step = length / 8 * 6 + 1, afin de se rapprocher rapidement d’une plage « nice »
  • step doit généralement être au moins égal à length / 2 pour pouvoir passer souvent à la boucle rapide, mais s’il est trop proche de length, on perd les avantages de la recherche binaire
  • À cause du break, bb_lower_bound comporte des branches
  • L’utilisation d’une table précalculée avec le step le plus rapide pour chaque longueur reste une piste qui n’a pas encore été explorée

Une implémentation totalement branchless n’était pas plus rapide

  • Sur une machine 64 bits, la boucle de sb_lower_bound s’exécute au plus 64 fois ; on peut donc créer une version « totalement branchless » qui supprime même le test sur length, avec un switch et des fall-through intentionnels
  • Cette approche saute vers la position de code correspondant au nombre de comparaisons nécessaire via std::bit_width(length)
  • En pratique, les performances n’étaient pas meilleures
  • Les CPU x86 modernes gèrent bien les branches prévisibles comme les conditions de boucle, donc supprimer le test sur length n’apportait pas d’avantage
  • La boucle classique a aussi été jugée préférable car elle évite les templates, les macros et la duplication-modification de 64 cas

Résultats des benchmarks

  • Les résultats en temps d’exécution moyen (ns) avec clang -cmov sont les suivants
    • std::lower_ : 61,30
    • branchless_lower_ : 43,43
    • asm_lower_ : 54,32
    • sb_lower_ : 33,24
    • sbm_lower_ : 35,54
    • bb_lower_ : 32,73
  • En moyenne géométrique du temps d’exécution (ns), sb_lower_ était aussi le plus bas
    • std::lower_ : 39,17
    • branchless_lower_ : 25,14
    • asm_lower_ : 31,21
    • sb_lower_ : 19,81
    • sbm_lower_ : 20,91
    • bb_lower_ : 21,33
  • sbm_lower_bound est une variante qui utilise la forme first += comp(first[length], value) * (length + rem) au lieu d’un if, afin d’inciter gcc à générer un déplacement conditionnel
  • Comme cette optimisation peut disparaître dans une future version de gcc, elle nécessite des commentaires et des précautions
  • Les commandes de benchmark utilisaient g++-10, clang++-10 et clang++-10 -mllvm -x86-cmov-converter=false, avec -march=haswell
  • -march=native ou l’absence de -march n’ont pas beaucoup influencé le classement, et les tests ont été effectués sur un Intel i7 Kaby Lake

Mesure des échecs de prédiction de branche

  • Une exécution clang classique mesurée avec perf a enregistré environ 6,94 milliards de branches et environ 1,20 milliard de branch-misses, soit un taux de 17,34 %
  • L’exécution clang -cmov a enregistré environ 4,07 milliards de branches et environ 35,95 millions de branch-misses, avec un taux réduit à 0,88 %
  • -cmov supprime environ 2,9 milliards de branches et environ 1,2 milliard d’échecs de branche
  • Les branches supprimées étaient des branches dont la prédiction échouait avec une probabilité d’environ 41 %
  • C’est proche des 50 % attendus pour une branche totalement imprévisible

Les résultats changent avec une fonction de comparaison lente

  • Pour observer une situation où la fonction de comparaison est plus lente, une recherche sur des chaînes de 8 octets a été testée
  • En temps d’exécution moyen (ns), std::lower_bound était légèrement plus rapide que sb_lower_bound, ou similaire
    • gcc : std::lower_ 160,01, sb_lower_ 165,66
    • clang : std::lower_ 157,71, sb_lower_ 162,68, bb_lower_ 157,22
    • clang -cmov : std::lower_ 156,06, sb_lower_ 164,71, bb_lower_ 157,48
  • Dans ce cas, std::lower_bound est très légèrement, mais systématiquement, plus rapide que sb_lower_bound
  • Une bibliothèque peut viser les meilleures performances en utilisant sb_lower_bound lorsqu’elle travaille directement sur des types primitifs, et std::lower_bound dans les autres cas

Différences visibles dans l’assembleur

  • La boucle chaude de std::lower_bound avec clang -cmov contient des déplacements conditionnels comme cmova et cmovbe, mais utilise plusieurs instructions pour mettre à jour la longueur et la position
  • La boucle chaude de sb_lower_bound calcule la demi-longueur, le reste et le pointeur à déplacer, puis met à jour first avec cmova
  • L’assembleur de branchless_lower_bound est très court et propre, mais dans les tests de performance, sb_lower_bound obtient de meilleurs résultats avec un overhead plus faible

Mise à jour : un sb_lower_bound plus court

  • Après un commentaire de l’auteur d’orlp.net, sb_lower_bound peut être refactorisé pour réduire le nombre d’instructions assembleur de la boucle chaude de 9 à 8
  • L’idée clé est que length - half est égal à half + length % 2
  • La forme refactorisée calcule half = length / 2, puis, si la comparaison est vraie, effectue first += length - half avant de mettre à jour length = half
  • Avec clang -cmov, le temps d’exécution moyen s’améliore légèrement, passant d’environ 33 ns à environ 32 ns

Sur les grands tableaux, le préchargement est efficace

  • Le préchargement proposé dans les commentaires consiste à amener à l’avance les données nécessaires dans les caches L1/L2 afin de réduire la latence lors de l’accès réel
  • Les exemples de latence sont d’environ 4 cycles pour L1, 12 cycles pour L2, 40 cycles pour L3 et 200 cycles pour la mémoire
  • gcc comme clang prennent en charge __builtin_prefetch()
  • Précharger la position length / 4 en gaspille 1 sur 2, et ajouter jusqu’à length / 8 en gaspille 5 sur 6
  • Le calcul des positions de préchargement et les appels eux-mêmes ajoutent aussi de l’overhead, et ce coût est important dans une boucle chaude raccourcie
  • Plusieurs stratégies de préchargement n’apportaient rien pour les tableaux de moins de 256 Ko
  • À partir de 256 Ko, sbp_lower_bound, qui ajoute du préchargement, a amélioré le temps d’exécution moyen d’environ 32 ns à environ 26 ns dans des tests allant jusqu’à environ 4 millions d’entrées, soit 16 Mo
  • Dans un test ensuite étendu à environ 128 millions d’entrées, soit 512 Mo, la version avec préchargement était environ 2,3× plus rapide que std::lower_bound en temps moyen
    • La comparaison était d’environ 161 ns pour std::lower_bound contre environ 71 ns pour la version avec préchargement

Observations et alternatives sur les grands jeux de données

  • Sur de très grandes tailles, le std::lower_bound branchless généré par clang -cmov était plus lent que la version avec branches
  • Les CPU modernes peuvent suivre les branches prédites et lancer des chargements mémoire ainsi que de l’exécution spéculative, ce qui peut fonctionner de fait comme du préchargement
  • sbpm_lower_bound est une version de sbm_lower_bound avec préchargement, qui utilise une multiplication booléenne pour inciter gcc à générer du code branchless
  • Des sauts apparaissent dans le graphe de performance entre 1 million et 10 millions d’éléments, ce qui laisse théoriquement de la place pour une implémentation plus rapide
  • Cependant, le code de préchargement devient de plus en plus complexe et multiplie les constantes magiques ; plus cette complexité augmente, moins il paraît probable de pouvoir le contribuer à gcc/libstdc++ ou llvm/libc++
  • Comme alternative qui s’affranchit des contraintes de std::lower_bound, il existe l’Eytzinger Binary Search, qui réorganise le tableau d’entrée en forme de tas de médianes binaires pour rendre les recherches plus cache-friendly
  • Dans le test d’arbre 16-aire sur int de Sergey Slotin à la CppCon 2022, les résultats étaient 7× à 15× plus rapides que std::lower_bound

Code et conditions d’utilisation

  • Si la recherche ou la comparaison est la partie la plus lente du programme et que le processeur a du mal à prédire les résultats des comparaisons, l’option -mllvm -x86-cmov-converter=false de clang sur x86 vaut la peine d’être essayée
  • Si une recherche binaire plus rapide est nécessaire, sb_lower_bound peut être essayé ; avec gcc, sbm_lower_bound est aussi une option
  • Le code est publié sous licence MIT
  • Le code et les benchmarks sont disponibles sur github.com/mh-dm/sb_lower_bound/

À lire aussi

1 commentaires

 
GN⁺ 2023-08-13
Avis sur Hacker News

  • Chaque fois que je vois des gens essayer de supprimer les branchements, je me demande s’ils savent que le fait qu’une mauvaise prédiction de branchement bloque un long pipeline n’est pas un élément indispensable de l’architecture CPU.
    Les pipelines sont longs parce qu’on effectue beaucoup d’analyses et de transformations juste avant l’exécution, mais comme ce n’est pas un algorithme très dépendant de l’état, la majeure partie pourrait être faite à l’avance.
    Les CPU Transmeta Crusoe fonctionnaient de cette manière, et on peut imaginer un monde où l’on n’aurait pas à se soucier des branchements.
    En allant plus loin, toute opération est un branchement qui regarde l’état des bits et modifie le résultat, mais ces branchements locaux à l’intérieur de l’ALU ne sont pas des branchements sur le pipeline principal, donc ils ne nuisent pas beaucoup aux performances.

    • Est-ce Dave ? :-) Il y avait autrefois un article qui comparait le CISC superscalaire et le RISC uniscalaire sous l’angle du débit horaire et du nombre d’instructions par cycle.
      Je me souviens avoir aussi dit à srk, à l’époque, que le choix entre IPC et débit comme métrique influait sur ce que l’on considérait comme bon ou mauvais.
      Le camp de l’IPC estime que si l’on augmente l’IPC, le procédé de fabrication permettra de monter la fréquence et tout le monde y gagnera ; le camp du débit adopte une approche plus réaliste, selon laquelle la loi de Moore est morte, faire tourner le silicium plus vite le fait fondre, et c’est donc la conception intelligente de l’ISA qui l’emportera.
      Au cours des 20 dernières années, les deux camps ont connu des succès et des déconvenues, et il est intéressant de voir RISC-V revenir aujourd’hui à ce type de questions dans l’architecture CPU.
      C’est aussi un bon terrain pour suivre comment des idées superscalaires modernes sont ajoutées grâce à la flexibilité du jeu d’instructions, et à long terme je pense que c’est cette voie qui gagnera.
    • C’est une idée complètement fausse.
      La traduction de Transmeta n’a pas supprimé le coût des branchements.
      Je me souviens que Linus, qui travaillait chez Transmeta, avait dit dans un fil comp.arch quelque chose comme : « le travail du CPU est de provoquer des cache misses le plus vite possible ».
      Les cache misses obligatoires existent, et aucun JIT ne peut les éliminer.
      Dans le monde réel, même avec les énormes caches actuels, on ne peut pas non plus éviter les capacity misses.
      Itanium pensait aussi pouvoir supprimer le coût des branchements par analyse statique ; il suffit de se rappeler comment cela s’est terminé.
      J’aimerais que les programmeurs lisent quelques livres d’architecture des ordinateurs avant de conclure avec assurance qu’ils peuvent facilement faire mieux que les processeurs modernes.
      À mon avis, ils sous-estiment d’au moins 7 ordres de grandeur l’ampleur de l’effort intellectuel investi dans les processeurs actuels.
    • Même s’il peut ne pas y avoir d’état, cela dépend beaucoup de facteurs inconnus au moment de la compilation.
      L’un d’eux est les données d’entrée traitées.
      La recherche binaire en est un cas typique : le compilateur ne sait pas à quelle position le résultat sera trouvé.
      Un autre est la microarchitecture, en particulier la hiérarchie de caches et la configuration des unités d’exécution.
      Si l’on passe à une ISA dont les instructions ressemblent aux micro-opérations des CPU actuels, il faudrait recompiler pour chaque microarchitecture.
      Cela dit, c’est techniquement soluble avec un JIT au niveau de l’OS, comme sur les GPU actuels : les programmes sont distribués sous forme de bytecode (DXBC, SPIR-V, NVPTX), puis le pilote GPU en mode utilisateur les recompile en instructions réelles pour le matériel.
      La variable la plus importante est toutefois que d’autres threads CPU exécutent du code inconnu.
      Même en supprimant l’hyperthreading pour rendre les cœurs indépendants, il reste des ressources partagées à l’échelle de la puce, comme le cache L3, la mémoire externe, la bande passante d’E/S, ainsi que la puissance et la dissipation thermique.
    • J’ai l’impression que le point clé est dans la définition de branchement.
      Si l’on redéfinit tout comme Branch™, alors certains Branch™, y compris des choses qui ne sont pas de vrais branchements, peuvent être précalculés.
      Mais la suppression de branchement dont on parle habituellement ne concerne-t-elle pas les cas où le chemin de calcul se sépare réellement, comme dans du code if/else ?
      Même dans ce monde, des optimisations utiles seraient possibles, mais elles se limiteraient aux Branch™ qui tentent de calculer simultanément plusieurs résultats futurs.
    • On pourrait aussi reformuler la raison pour laquelle les pipelines sont longs ainsi : il y a beaucoup de travail indépendant que le processeur peut faire simultanément.
      Chaque fois qu’il existe une opération pouvant être effectuée indépendamment, il existe d’autant plus de possibilités de l’exécuter en parallèle.
      Je ne parle pas seulement du décodage, du fetch et de l’exécution.
      Avec une ALU et un shifter indépendants, on peut décaler pendant qu’on additionne ; avec un additionneur et un multiplicateur dédiés, il n’y a pas de raison de ne pas tenter les deux en même temps.
      Cela conduit à vouloir garder plusieurs instructions en cours simultanément, ce qui signifie qu’il faut pouvoir récupérer et décoder les instructions plus vite qu’on ne les traite.
      Cela mène aussi naturellement à vouloir les réordonner pour éviter que N instructions Add n’empêchent de voir un Shift indépendant.
      On peut penser que l’architecture actuelle est plus complexe que nécessaire, et ce n’est peut-être pas faux.
      Mais comme une énorme quantité d’ingénierie est investie dans les architectures actuelles, si l’on pense pouvoir faire beaucoup plus rapide autrement, il faut creuser sérieusement pour vérifier à quel point cette affirmation est exacte.

  • À propos du passage « Si seulement il existait un langage bare metal propre et rapide pour écrire tout ça… », l’auteur a ajouté des notes « BUT RUST.. » et « BUT ZIG.. », mais je me demande ce qu’il en serait de Nim
    Il semble exister une implémentation native de bibliothèque pour lowerBound : https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al...
    À strictement parler, ce n’est pas un langage « bare metal », mais comme il compile vers C ou C++, il serait intéressant de voir en quel code cela se compile ici
    Et je me demande aussi quel est le problème avec C

  • Je ne suis toujours pas sûr que ce soit bien lower_bound
    J’ai peut-être mal lu le code, mais en présence de doublons, il semble renvoyer une correspondance quelconque plutôt que la première
    Si la fonction de comparaison cherche un préfixe de chaîne donné pour de l’autocomplétion, plusieurs éléments peuvent correspondre même dans une liste unique, et dans ce cas on veut le premier élément de la liste

    • À chaque correspondance, la longueur restante est divisée par deux, et la boucle ne se termine que lorsque la longueur vaut 0 ; il devrait donc renvoyer le premier élément
    • Avoir une option plus rapide quand on se moque de savoir quelle correspondance exacte est renvoyée me paraît intéressant
    • À mon avis, il renvoie bien la première correspondance
      Je serais curieux de savoir pourquoi tu penses le contraire

  • J’aimerais que tous les billets de blog commencent comme celui-ci : « Je sais que vous êtes occupés, alors allons droit au but. Voici l’implémentation de recherche binaire en C++ la plus rapide, générale et simple »

  • La bibliothèque standard de Zig n’appelle pas C++ pour la recherche binaire
    La recherche binaire actuelle se trouve ici : https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...

  • Je ne comprends pas bien
    Le problème de la recherche binaire et des branchements n’est pas le branchement lui-même, mais le fait qu’on ne sait pas quel emplacement mémoire du tableau charger ensuite tant que la comparaison n’est pas terminée
    Que l’on utilise un branchement ou autre chose n’y change rien : la question est ce que l’on veut au final que le processeur fasse
    Il y a une dépendance de données
    Avant d’avoir lu l’indice du milieu, on ne sait pas s’il faut chercher dans la moitié supérieure ou inférieure
    On peut spéculer et émettre les lectures des deux côtés, ce qui résout la dépendance mais augmente le trafic mémoire
    Tout l’enjeu est de savoir si c’est le bon compromis ; supprimer simplement les branchements n’est pas la réponse

    • Pour les grands tableaux, le préchargement est le bon compromis
      C’est abordé vers la fin du billet : https://mhdm.dev/posts/sb_lower_bound/#prefetching
    • Exact
      C’est pourquoi une recherche binaire réellement plus rapide utilise une disposition de tableau Eytzinger : https://algorithmica.org/en/eytzinger
    • Si le tableau tient entièrement dans le cache L1, le coût d’une mauvaise prédiction de branchement n’est-il pas bien supérieur à celui du chargement mémoire ?

  • Sur mon processeur Cascade Lake, -mllvm -x86-cmov-converter=false réduit presque de moitié les performances de la recherche binaire
    Les chiffres sont en nanosecondes par bsearch sur un tableau uint32 de 100 Mo
    clang 15.0.7 semble bien moins bon que gcc 13.2.1 pour optimiser ce code précis
    L’assembleur est consultable ici : https://godbolt.org/z/cbx5Kdjs6
    L’assembleur produit par gcc paraît beaucoup plus propre

    Benchmark gcc clang clang -cmov
    slow u32 23.4 46.7 45.8
    fast u32 18.1 19.8 31.4
    • Dans ce cas, il faut regarder https://mhdm.dev/posts/sb_lower_bound/#prefetching
      100 Mo, c’est suffisamment grand pour que la version avec branchements soit légèrement avantagée, mais c’est dû aux caractéristiques de l’exécution spéculative sur x86 plutôt qu’à une réelle supériorité

  • Quelqu’un sait-il vers quoi le lien « BUT RUST » était censé pointer à l’origine ?
    Il n’était pas figé sur une version, donc il semble déjà cassé, et il devait peut-être pointer vers le milieu du commentaire de documentation de starts_with

    • D’après les captures archive.org juste avant [1] et juste après [2] la publication de l’article, il semble qu’il visait cette ligne de code, qui est maintenant la ligne 2779 [3]
      let mid = left + size / 2;

[1] https://web.archive.org/web/20230602210213/https://doc.rust-...

[2] [https://web.archive.org/web/20230709221353/https://doc.rust-...](<https://web.archive.org/web/20230709221353/…;)

[3] [https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779](<https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779>;)

  • Il s’agissait de faire un lien vers l’implémentation de la recherche binaire de Rust
    Elle a été mise à jour vers https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#...

  • Il est intéressant de voir que le résultat ne se maintient pas avec une fonction de comparaison comp plus complexe
    L’article envisageait un scénario de recherche binaire assez réaliste où la fonction de comparaison est lente, comme pour des ID, des numéros de téléphone, des comptes ou des mots-clés, et indique avoir donc testé la recherche sur des chaînes de 8 octets
    Dans ce cas, std::lower_bound est très légèrement, mais systématiquement, plus rapide que sb_lower_bound, et pour obtenir toujours les meilleures performances, une bibliothèque devrait utiliser sb_lower_bound lorsqu’elle manipule directement des types primitifs, et std::lower_bound dans les autres cas
    J’aimerais voir l’analyse correspondante

    • Je pense que cela vient de la prédiction de branchement, qui permet de mettre plusieurs comparaisons en pipeline simultanément et de revenir en arrière quand le prédicteur se trompe
      Avec des données et des entrées réellement aléatoires, la prédiction se trompe environ une fois sur deux
      L’approche CMOV est bloquée après la fonction de comparaison à cause de la dépendance de données
      En moyenne, l’approche avec branchement effectue deux comparaisons à la fois, tandis que CMOV n’en effectue qu’une ; on peut donc s’attendre à un point de bascule lorsque le temps de comparaison devient supérieur à la pénalité d’un échec de prédiction de branchement
    • Si c’est le cas, il existe très probablement une bien meilleure version de recherche binaire pour les types primitifs
      Un prototype SIMD que j’avais bricolé auparavant est 3 fois plus rapide que std::lower_bound jusqu’à ce qu’il soit limité par la bande passante mémoire : https://github.com/matthewkolbe/ThinkingInSimd/tree/main/alg...
    • Dans l’article, je n’ai trouvé aucune garantie sur le jeu de données d’entrée ni sur le contenu des clés de recherche, à part le fait qu’ils sont « imprévisibles »
      Je suppose qu’ils sont purement aléatoires, mais si ces chaînes de 8 octets ne sont pas de l’information pure, les prédicteurs de branchement modernes peuvent facilement faire mieux que cmov

  • L’attribut unpredictable semble désormais influencer la passe de conversion en cmov
    Cela date du 1er juin, donc ce sera probablement inclus dans clang 17/18 : https://reviews.llvm.org/D118118