La recherche binaire branchless la plus rapide

• Cet article présente une implémentation générique de recherche binaire en C++ plus courte et deux fois plus rapide que la fonction standard std::lower_bound.
• La nouvelle implémentation est dite « branchless » car elle est compilée en instructions de déplacement conditionnel plutôt qu’en branchements/sauts conditionnels.
• La recherche binaire fonctionne en divisant une liste triée en deux parties à l’élément du milieu, puis en comparant la valeur médiane à la valeur recherchée. En fonction du résultat de la comparaison, on décide dans laquelle des deux sous-listes poursuivre la recherche.
• L’article aborde aussi le concept de prédiction de branchement, une technique qui permet au processeur d’exécuter des instructions en parallèle pour gagner en vitesse. Mais comme la recherche binaire est imprévisible, la prédiction de branchement n’est pas idéale ici.
• L’auteur présente une nouvelle implémentation de recherche binaire, sb_lower_bound, plus rapide que l’implémentation standard et que la version branchless_lower_bound, car elle contient nettement moins d’instructions dans la boucle.
• L’auteur présente également une version encore plus rapide, bb_lower_bound, qui utilise une autre méthode pour partitionner la liste de recherche.
• L’article se conclut par une suggestion : si la partie la plus lente de votre programme comprend des recherches et/ou comparaisons que le processeur ne peut pas prédire, essayez clang avec -mllvm -x86-cmov-converter=false. Et si vous avez besoin d’une recherche binaire plus rapide, essayez sb_lower_bound.
• L’auteur fournit aussi le code de ces nouvelles implémentations de recherche binaire et discute en détail des performances de chacune.
• L’article a également été mis à jour avec une version refactorisée de sb_lower_bound qui réduit le nombre d’instructions assembleur dans la boucle critique de 9 à 8, ce qui améliore légèrement la vitesse.
• L’auteur aborde aussi le concept de prefetching, qui consiste à faire remonter certaines zones mémoire dans le cache afin que, lorsque les données préchargées deviennent réellement nécessaires, seules les latences du cache L1/L2 s’appliquent. Une version de sb_lower_bound avec prefetching ajouté pour 256 KB+ est également fournie.
• Cet article est signé Mihail Dumitrescu et a été publié le 24 juin 2023.

[GN⁺]

Commentaires sur Hacker News

• L’article discute du concept de recherche binaire sans branchement et de ses avantages potentiels.
• Un commentaire remet en question la nécessité d’éliminer les branches et suggère que les blocages du pipeline causés par les erreurs de prédiction de branchement ne sont pas une partie intrinsèque de l’architecture.
• Le commentaire explique plus en détail que toutes les opérations sont fondamentalement des branches, et que si ces branches ne nuisent pas aux performances, c’est parce qu’elles ne se situent pas dans le pipeline principal.
• Un autre commentaire suggère d’utiliser le langage Nim, compilé vers un langage « bare-metal », pour implémenter lowerBound.
• Une discussion porte sur le fait de savoir si le code renvoie la première correspondance ou simplement une correspondance quelconque, en soulignant l’importance de bien comprendre le fonctionnement du code.
• Un commentaire salue l’introduction intuitive du billet de blog, qui présente rapidement l’implémentation C++ de recherche binaire générique la plus rapide.
• Un commentaire fait remarquer que la stdlib de Zig n’appelle pas C++ pour la recherche binaire et fournit un lien vers la recherche binaire de la stdlib de Zig.
• Une discussion porte sur le problème de la recherche binaire et des branches, en suggérant que le problème ne vient pas des branches elles-mêmes, mais de la dépendance aux données, qui empêche de savoir quelle position mémoire charger ensuite tant que la comparaison n’est pas terminée.
• Un commentaire partage des résultats de performances de recherche binaire sur des processeurs Cascade Lake et suggère que clang optimise ce code particulier moins bien que gcc.
• Un commentaire s’interroge sur la destination du lien « BUT RUST » et indique que ce lien semble obsolète.
• Un commentaire souligne que les résultats ne se maintiennent pas avec des fonctions de comparaison plus complexes, et suggère que les meilleures performances peuvent être obtenues en utilisant sb_lower_bound pour les types primitifs et std::lower_bound dans les autres cas.
• Enfin, un commentaire mentionne que la propriété d’imprévisibilité affecte désormais la passe de transformation cmov, et fournit un lien pour plus d’informations.