- La recherche binaire, couramment utilisée pour trouver une valeur dans un tableau trié, ne compare qu’une seule valeur à la fois, alors que les CPU modernes peuvent comparer plusieurs valeurs simultanément avec une seule instruction ; exploiter cette capacité peut donc nettement accélérer la recherche
- SIMD Quad est un algorithme de recherche hiérarchique qui découpe le tableau en blocs de 16 éléments, réduit rapidement la zone de recherche via une recherche par interpolation quaternaire, puis compare d’un coup les 16 éléments du bloc avec des instructions SIMD
- Dans les benchmarks, sur Intel avec cache warm, il a montré des performances plus de 2 fois supérieures à la recherche binaire ; sur Apple avec cache cold aussi, et il a surpassé
std::binary_searchdans toutes les conditions mesurées - Au lieu de diviser par deux comme la recherche binaire, un découpage en quatre augmente légèrement le nombre d’instructions, mais exploite mieux le parallélisme au niveau mémoire sur les grands tableaux Intel, ce qui améliore les performances en cache cold
- Les algorithmes de manuels ont été conçus sans supposer le parallélisme des données et de la mémoire des CPU actuels ; une refonte tenant compte des caractéristiques matérielles peut donc apporter des gains de performance concrets
Idée clé
- La recherche binaire compare une seule valeur à la fois, mais les processeurs ARM 64 bits et x64 modernes peuvent comparer simultanément 8 entiers 16 bits en une seule instruction
- En exploitant cette capacité matérielle, on peut faire passer l’unité de recherche de l’élément individuel au bloc, et ainsi réduire fortement le nombre de comparaisons
- Au lieu de couper le tableau en deux, un découpage en 4 (recherche quaternaire) augmente un peu le nombre d’instructions, mais il est probable que le goulot d’étranglement ne soit pas là, tout en permettant de mieux exploiter le parallélisme au niveau mémoire
Méthodes de base pour tester l’appartenance dans un tableau trié
- La méthode la plus simple pour vérifier la présence d’une valeur dans un tableau trié est la recherche linéaire, qui parcourt les valeurs une à une ; en C++, on obtient le même effet avec
std::find - Sur les grands tableaux, la recherche binaire est plus rapide ; elle répète l’opération qui consiste à éliminer la moitié haute ou basse de l’intervalle à partir de la valeur centrale
- En C++,
std::binary_searchrenvoie un booléen indiquant la présence ou non de la valeur - Le format Roaring Bitmap utilise des tableaux d’entiers 16 bits de taille 1 à 4096 et s’appuie sur la recherche binaire pour vérifier la présence d’une valeur
Structure de l’algorithme SIMD Quad
- Le tableau trié d’entiers non signés 16 bits est découpé en blocs de taille fixe de 16 éléments
- Le dernier élément de chaque bloc sert de clé d’interpolation afin de réduire la recherche à un seul bloc susceptible de contenir la valeur cible, puis les 16 éléments de ce bloc sont testés simultanément via SIMD
- Étapes de fonctionnement :
- si le nombre d’éléments est inférieur à 16, on effectue une simple recherche linéaire sur l’ensemble
- le tableau est découpé en blocs de 16 éléments consécutifs, avec un nombre total de blocs
num_blocks = cardinality / 16 - en utilisant le dernier élément de chaque bloc comme clé, on compare les positions situées aux quarts de l’intervalle courant à la valeur cible, puis on ajuste
base - si le bloc est valide, on charge 16 éléments avec NEON sur ARM ou SSE2 sur x64 pour effectuer une comparaison d’égalité en parallèle
- les éléments restants qui ne remplissent pas un bloc complet sont traités par recherche linéaire
Méthode de benchmark
- Pour chaque taille de tableau de 2 à 4096, 100 000 tableaux triés d’entiers non signés 16 bits sont générés
- Pour chaque taille, 10 millions de requêtes d’appartenance sont exécutées selon deux modes
- mode cold : chaque requête interroge un tableau différent pour simuler des cache misses
- mode warm : le même tableau est interrogé 100 fois de suite pour simuler des cache hits
- La mesure porte sur le temps moyen par requête, avec comme points de comparaison la recherche linéaire (
std::find), la recherche binaire (std::binary_search) et SIMD Quad - Les systèmes mesurés sont Apple M4 (Apple LLVM) et Intel Emerald Rapids (GCC)
Résultats
- Quand la taille du tableau augmente, la recherche binaire dépasse nettement la recherche linéaire ; en cache cold, la recherche linéaire est encore plus pénalisée à cause du plus grand nombre d’accès mémoire
- Plateforme Intel : en cache warm, SIMD Quad est plus de 2 fois plus rapide que la recherche binaire ; en cache cold, le gain est plus limité
- Plateforme Apple : en cache cold, SIMD Quad est plus de 2 fois plus rapide ; en cache warm, le gain est plus modeste
- Dans tous les cas, SIMD Quad a été plus rapide que
std::binary_search - La partie SIMD réduit le travail grâce à des instructions spécialisées, avec moins d’instructions et moins de branches, ce qui explique clairement l’accélération
Effet de la recherche quaternaire
- Une version SIMD binary, qui conserve l’optimisation SIMD mais remplace la recherche par interpolation quaternaire par une recherche binaire, a aussi été comparée
- Sur la plateforme Apple, l’effet de l’approche quaternaire est resté faible
- Sur la plateforme Intel, l’approche quaternaire constitue une optimisation significative en cache cold sur de grands tableaux
- Sur les serveurs Intel, la recherche quaternaire exploite mieux le parallélisme au niveau mémoire
Points clés de l’implémentation
- La fonction
simd_quadprend en entrée un tableau deuint16_t, un nombre d’élémentscardinality, et la valeur recherchéepos, puis renvoie un booléen gapest fixé à 16 ; sicardinality < gap, la recherche se fait avec une simple boucle- La boucle de recherche de bloc lit et compare les dernières valeurs des blocs aux positions 1/4, 2/4 et 3/4 tant que
n > 3, puis déplacebaseselon la somme des trois résultats de comparaison - Le bloc sélectionné compare ses 16 éléments en deux groupes en parallèle à l’aide de
vceqq_u16sur ARM NEON ou de_mm_cmpeq_epi16sur x64 SSE2 - Dans la zone des éléments restants, la fonction renvoie si
v == posau premier point oùv >= pos
Conclusion
- La recherche binaire classique des manuels est correcte, mais on peut réellement faire mieux en pratique
- Les algorithmes standard sont souvent conçus sans partir du principe que les ordinateurs actuels offrent un haut degré de parallélisme
- SIMD Quad est une approche qui cherche à exploiter à la fois le parallélisme au niveau mémoire et le parallélisme des données
- Il est possible que de meilleurs algorithmes existent encore, et des approches plus créatives restent nécessaires
- Code source
- Faster intersections between sorted arrays with shotgun
1 commentaires
Commentaires sur Hacker News
Indépendamment des optimisations matérielles de bas niveau évoquées par Daniel Lemire, la recherche binaire ou ses variantes d’implémentation ne sont optimales que lorsqu’on ne sait rien d’autre sur les données que le fait qu’elles sont triées/monotones
S’il existe des informations préalables sur la distribution des données, on peut les exploiter pour construire des algorithmes bien plus rapides. L’exemple typique est celui d’une personne qui, dans un dictionnaire papier, se déplace vers le bon groupe de pages plus vite qu’avec une recherche binaire pure
Mathématiquement, la recherche dans une liste triée se rapproche de la recherche de l’inverse d’une fonction monotone avec un algorithme de contrôle en boucle fermée ; on peut aussi définir une fonction de coût et utiliser une descente de gradient ou des variantes accélérées. Plus généralement, il est toujours plus efficace d’exploiter davantage d’informations sur le problème précis à résoudre que d’aller chercher une solution à une formulation trop abstraite, et cela peut apporter des gains de performance évolutifs bien supérieurs aux améliorations par facteur constant obtenues en tirant mieux parti du matériel
Un nombre fixe d’itérations est bon pour le prédicteur de branchement, et la boucle centrale est aussi très serrée et optimisée pour le matériel cible en évitant les multiplications. Les tentatives pour rendre ça plus intelligent ont dégradé la boucle sans apporter de gain. Le format en tableau de structures a une taille de 12, et en général N est petit, ce qui complique aussi les choses
Je ne l’ai pas mis en favori, donc je le recherche à nouveau environ deux fois par an. La légende dit que je suis toujours en train de le chercher
C’est pour cela que les B-arbres sont la norme dans les bases de données. Les données peuvent être n’importe quoi, et si l’on charge un gros lot de nouvelles lignes, leurs caractéristiques peuvent changer radicalement à tout moment
On peut certes construire un algorithme qui accélère les recherches avec une approche de type descente de gradient, mais les B-arbres sont déjà très rapides et présentent aussi de nombreux avantages : performances en pire cas, prévisibilité des besoins d’E/S, scans de plages, parcours triés, prise en charge des conditions de préfixe, etc.
On peut concevoir des algorithmes de recherche plus efficaces sur certaines distributions de données, mais on perd souvent des propriétés importantes. Même si un autre algorithme donne une estimation initiale plus proche, il peut être plus lent pour trouver le dernier élément, ou avoir un pire cas tellement mauvais qu’il devient inutilisable malgré de bonnes performances moyennes
Même dans un dictionnaire papier, après l’estimation initiale, on utilisait presque une recherche binaire. Cette estimation initiale n’épargne que quelques étapes. Une fois arrivé au bon groupe de pages, on parcourt souvent ensuite linéairement plus de pages que nécessaire ; une recherche binaire stricte pourrait être plus rapide, mais il faut aussi trouver le bon compromis avec le temps de tourner les pages
Ed Kmett a affiné ces idées dans la bibliothèque Haskell discrimination[2], et la présentation technique associée[3] est elle aussi très intéressante
[1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
[2]: https://hackage.haskell.org/package/discrimination
[3]: https://www.youtube.com/watch?v=cB8DapKQz-I
La « recherche quaternaire », au fond, n’est-ce pas juste une boucle de recherche binaire déroulée d’un cran ? Pour trouver l’intervalle contenant l’élément, on dirait que le nombre de comparaisons reste à peu près le même, sauf qu’on traite 4 possibilités à la fois au lieu de 2. On pourrait sans doute obtenir le même effet avec du déroulage de boucle
Du point de vue du processeur, presque toutes les boucles sont donc déjà partiellement déroulées, et il ne reste que le faible surcoût propre à la boucle. Dans une recherche binaire, le coût principal vient du chargement des données depuis la mémoire ou le cache ; le vrai enjeu est donc de demander le plus tôt possible les données qui seront nécessaires plus tard, afin d’attendre moins leur arrivée
La différence d’un algorithme comme la recherche quaternaire, c’est qu’au lieu de précharger profondément un seul côté de chaque branche, il préfetche superficiellement tous les cas possibles. Ainsi, les préfetchs qui finiront forcément par être utiles sont bien émis, tout en dépensant un peu moins de bande passante sur des données qui ne seront pas utilisées dans le chemin d’exécution réel
Pour prédire les performances réelles d’un algorithme de recherche, le « nombre de comparaisons » est presque une métrique inutile. Le goulot d’étranglement n’est pas la quantité de comparaisons qu’on peut faire, mais la capacité à exploiter au maximum la bande passante mémoire et cache. Si l’on tient compte du comportement interne des branches sur les processeurs modernes, on peut effectivement voir ça comme une forme de déroulage de boucle
Dans tous les cas, les deux recherches restent en O(log N), avec des constantes différentes. En cours d’algorithmique, les constantes comptent peu ; dans le monde réel, elles peuvent avoir un impact considérable
J’ai récemment écrit un article[1] sur la recherche exponentielle[2]. C’est un algorithme utile lorsqu’on doit effectuer de façon répétée une recherche binaire dans un tableau, avec des éléments recherchés eux-mêmes déjà triés, et sur notre charge de travail nous avons obtenu un gain de vitesse de 8x
[1] https://lalitm.com/post/exponential-search/
[2] https://en.wikipedia.org/wiki/Exponential_search
HEAD /users/1 -> 200 OK
HEAD /users/2 -> 200 OK
HEAD /users/4 -> 200 OK
...
HEAD /users/2048 -> 200 OK
HEAD /users/4096 -> 404 Not Found
Ensuite, on fait une recherche binaire entre 2048 et 4096 pour trouver l’utilisateur le plus récent et, au passage, le nombre d’utilisateurs. Une information utile quand on enquête sur des concurrents SaaS
Le CPU lit toujours toute une ligne de cache, généralement 64 octets, en une seule opération ; il vaudrait donc mieux exploiter toute la ligne. Une fois les données dans le CPU, cela devient pratiquement gratuit
J’aimerais donc essayer une approche où, dans la recherche « binaire », on examine toutes les valeurs de la ligne de cache centrale, puis on part à gauche ou à droite s’il n’y a pas de correspondance. La recherche dans une ligne de cache peut se faire avec une seule instruction SIMD 512 bits. Une ligne de cache de 64 octets contient 32 entiers 16 bits ; on pourrait donc être presque 32 fois plus rapide qu’une recherche binaire simple, ou au moins réduire d’un facteur 32 les accès mémoire, ce qui dominerait dans la plupart des programmes réels
Avec des clés de 4 octets et des pointeurs de fils de 4 octets, ou des indices de tableau, un nœud interne peut remplir exactement une ligne de cache de 64 octets avec 7 clés, 8 pointeurs de fils et 1 pointeur suivant. Sur un million d’éléments, la profondeur de l’arbre passe d’environ 20 à environ 7, et les premiers niveaux ont de fortes chances de rester en cache
Avec un peu de réflexion, on peut accélérer la recherche à l’intérieur d’un nœud de B-arbre avec du SIMD, mais les dépendances de données restent très fortes
Pour des tableaux plus petits, une recherche linéaire avec valeur sentinelle en fin de tableau est déjà difficile à battre. Mais l’affirmation reste un peu floue, parce que « petit » est une condition trop vague pour être parlante intuitivement
Globalement, j’aime beaucoup cet article. Il explore parfaitement quelque chose que je me demandais depuis longtemps, avec en plus des expériences d’élimination très utiles
J’ai fait quelques expériences de recherche dans de petits tableaux, de 16 à 32 éléments, et la recherche binaire faisait partie des pires méthodes à cause du nombre de branches. Sur les petits tableaux, la méthode la plus rapide était une recherche linéaire sans branchement
Le principe est de parcourir tous les éléments sans jamais interrompre la boucle au milieu. Par exemple, si l’on veut savoir si un nombre est présent dans un tableau, on combine les résultats des tests de tous les éléments avec un OU logique. Je n’ai pas utilisé SIMD, mais sur de petits tableaux, les branches coûtent tellement cher qu’il est plus rapide de tester simplement tous les éléments sans branchement
L’explication de l’algorithme m’a un peu embrouillé
La partie SIMD n’est utilisée qu’à la dernière étape, c’est-à-dire pour rechercher dans les 16 derniers éléments
La partie recherche quaternaire consiste à tester 3 points pour créer 4 chemins, mais elle cherche en réalité le bon bloc, pas simplement la bonne clé
Le détail est intéressant : l’auteur utilise le dernier élément de chaque bloc pour la recherche quaternaire. Je me demande comment l’algorithme changerait si l’on utilisait le premier élément ou un élément arbitraire
L’intuition clé ici, à savoir les comparaisons multiples en SIMD, semble pouvoir s’appliquer à des tailles plus grandes que la seule étape finale
En gros : a) récupérer plusieurs éléments à 16 positions régulièrement espacées avec un gather b) comparer en parallèle avec une instruction SIMD c) se concentrer sur le bon bloc d) basculer en recherche linéaire quand le bloc est petit, sinon répéter le cycle gather/comparaison
Les instructions gather lisent dans une mémoire non contiguë, et dans le cas d’une recherche binaire elles lisent plus de données qu’il n’en faut réellement. Malgré cela, si elles permettent des comparaisons multi-voies et de condenser 4 étapes de recherche binaire, elles pourraient l’emporter sur de grandes tables
Il n’est d’ailleurs pas possible de faire de vraies comparaisons dans 16 directions pour tous les types de données. La recherche sur des float64 est limitée à des comparaisons dans 8 directions, même avec AVX-512, tandis que int32 et float32 permettent des comparaisons dans 16 directions
Je pense qu’une recherche binaire sera en pratique plus rapide qu’une approche fondée sur gather
Les algorithmes classiques de l’informatique ont en réalité été « conçus » pour des CPU essentiellement dépourvus de parallélisme : pas de multicœur, pas de Hyper-threading, pas d’instructions SIMD, tous les accès mémoire ayant le même temps, sans notions de latence de cache L1/L2/L3, et en supposant des données génériques/aléatoires
Dès qu’on sort d’une seule de ces hypothèses, il y a beaucoup de réglages possibles pour améliorer les performances
Les algorithmes classiques offrent un très bon point de départ pour développer des solutions plus optimisées lorsqu’on connaît mieux la forme des données ou les caractéristiques/fonctionnalités d’un CPU donné
Quand on pousse l’optimisation jusqu’au bout, on finit souvent par examiner comment les données sont stockées et accédées en mémoire, et si les changements censés améliorer cela ne nuisent pas aux étapes suivantes. Dans un ancien emploi, quelqu’un avait passé beaucoup trop de temps à optimiser une portion de code ; résultat, cette optimisation évinçait du cache beaucoup d’informations utiles plus tard, et l’application entière en devenait plus lente
C’est probablement une reformulation de la 5e règle de programmation de Rob Pike, elle-même proche de ce que Fred Brooks disait dans The Mythical Man Month. Référence : https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
Quand j’étais ado, j’ai passé tout un week-end à me dire que si la recherche binaire était bonne parce qu’elle divisait l’espace de recherche par deux à chaque étape, alors la recherche ternaire devait être meilleure puisqu’elle divisait par trois
Au lieu de comparer uniquement la valeur du milieu, je comparais la valeur au premier tiers puis, si elle était trop faible, celle aux deux tiers
Mais comme on réduisait à chaque étape par un facteur 1/3 au lieu de 1/2 pour la recherche binaire, tout en faisant selon moi en moyenne 3/2 fois plus de comparaisons, j’en avais conclu que cela revenait au même
Correction : en lisant la réponse de zamadatix, j’ai vu qu’en réalité, dans 2/3 des cas, il faut faire 2 comparaisons, donc la moyenne est de 5/3
Premier tiers : 1 comparaison
Deuxième tiers : 2 comparaisons
Troisième tiers : 2 comparaisons
(1+2+2)/3 = 5/3 comparaisons en moyenne. On peut facilement se tromper et croire à 50 % parce qu’on a l’impression de « faire 1 ou 2 comparaisons », mais en réalité la probabilité de conclure dès la première comparaison est de 1/3, et celle d’en faire 2 est de 2/3
On peut donc montrer que, sur le nombre total moyen de comparaisons, la recherche ternaire est un tout petit peu moins bonne : 5/3*Log_3[n] = 1.052... * Log_2[n]
En d’autres termes, on réduit le nombre d’étapes, mais on effectue en moyenne davantage de comparaisons pour aller jusqu’au bout. Cela vaut généralement pour tous les types de recherche de ce genre, c’est-à-dire dès que le nombre de partitions est supérieur à 2. Bien sûr, cela repose sur quelques hypothèses, notamment une distribution uniforme des valeurs recherchées et un coût d’opération idéalisé, et c’est précisément là qu’intervient la discussion de l’article
Pas comme version ternaire de l’algorithme de recherche binaire. En réalité, ce n’est pas une vraie recherche ternaire, mais plutôt une recherche binaire biaisée, car la comparaison est intrinsèquement binaire. Tous les algorithmes de recherche reposant sur des comparaisons sont donc une forme de recherche binaire, et choisir autre chose que l’élément central est moins efficace du point de vue de la complexité algorithmique. En revanche, sur du matériel réel, cela peut être meilleur dans certaines conditions. Pour une vraie recherche ternaire, il faut comme opération primitive une comparaison à 3 voies
Cela devient intéressant lorsqu’on considère l’« efficacité de base »[1]. Le meilleur choix est 3, l’entier naturel le plus proche de e. Cela se relie aussi aux arbres de recherche, et un arbre ternaire peut être meilleur qu’un arbre binaire
[1] https://en.wikipedia.org/wiki/Optimal_radix_choice
Donc même si l’idée n’était pas praticable sur les CPU de l’époque, elle est peut-être devenue plus plausible sur les CPU d’aujourd’hui