Vous pouvez battre la recherche binaire

• Le test d’appartenance dans un tableau trié peut être rendu plus rapide que la recherche binaire classique des manuels, et SIMD Quad s’est montré plus rapide que std::binary_search dans toutes les conditions mesurées
• SIMD Quad divise un tableau trié d’entiers non signés 16 bits en blocs de 16 éléments, applique une recherche par interpolation quaternaire aux frontières des blocs, puis des comparaisons SIMD en parallèle à l’intérieur des blocs
• Les architectures ARM 64 bits modernes et x64 (Intel/AMD) peuvent comparer 8 entiers 16 bits en une seule instruction, ce qui réduit l’intérêt de conserver telle quelle une structure de recherche binaire qui ne vérifie qu’une valeur à la fois
• Le benchmark a été réalisé sur 100�000 tableaux triés de taille 2 à 4096, avec 10 millions de requêtes d’appartenance ; le mode cold simule des défauts de cache, tandis que le mode warm simule des succès de cache
• Sur Intel, SIMD Quad était plus de deux fois plus rapide que la recherche binaire avec cache warm ; sur Apple, plus de deux fois plus rapide avec cache cold ; et sur Intel, pour les grands tableaux en cache cold, l’approche quaternaire exploite mieux le parallélisme au niveau mémoire

---

Goulot d’étranglement du test d’appartenance dans un tableau trié

• La manière la plus simple de vérifier si une valeur existe dans un tableau trié est la recherche linéaire, qui parcourt les valeurs une par une ; en C++, on peut obtenir le même effet avec std::find
• Pour les grands tableaux, la recherche binaire est plus rapide ; elle élimine à répétition la moitié haute ou basse de l’intervalle de recherche en se basant sur la valeur du milieu, jusqu’à trouver la valeur ou atteindre un intervalle vide
• En C++, std::binary_search renvoie 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 emploie la recherche binaire pour vérifier la présence d’une valeur

Point de départ de SIMD Quad

• La plupart des processeurs modernes disposent d’instructions de parallélisme de données SIMD, et ARM 64 bits comme x64 (Intel/AMD) peuvent comparer 8 entiers 16 bits à une valeur cible en une seule instruction
• Grâce à cette propriété, il n’est pas nécessaire de faire descendre la recherche binaire jusqu’à des blocs de moins de 8 éléments, et il devient peu coûteux de comparer aussi des groupes de 16 éléments ou plus
• La recherche binaire examine une valeur à la fois, mais les processeurs récents peuvent charger et tester plusieurs valeurs en une seule fois, avec un bon parallélisme au niveau mémoire
• Au lieu de couper le tableau en deux, on peut essayer une recherche quaternaire qui le divise en quatre ; même si cela augmente légèrement le nombre d’instructions, il est possible que le goulot d’étranglement ne soit pas là

Structure de l’algorithme SIMD Quad

• SIMD Quad est un algorithme de recherche pour des tableaux triés d’entiers non signés 16 bits, qui combine recherche par interpolation quaternaire et SIMD
• Le tableau est divisé en blocs de taille fixe de 16 éléments, le dernier bloc pouvant faire exception
• Le dernier élément de chaque bloc sert de clé d’interpolation pour 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
• Le principe central est une recherche hiérarchique : réduire le nombre de comparaisons par recherche d’interpolation aux frontières des blocs, puis effectuer des comparaisons parallèles SIMD à l’intérieur du bloc
• Les étapes de fonctionnement sont les suivantes
  • Si le nombre d’éléments est inférieur à 16, on effectue une recherche linéaire simple sur l’ensemble
  • Le tableau de taille cardinality est découpé en blocs de 16 éléments consécutifs, et le nombre total de blocs est num_blocks = cardinality / 16
  • On utilise comme clés les derniers éléments des blocs aux positions 16-1, 32-1, etc., et on compare au pos cible les points situés à 1/4 de l’intervalle de recherche courant afin d’ajuster base
  • En fonction du résultat de l’interpolation, on sélectionne l’indice de bloc approprié lo
  • Si le bloc est valide, on charge ses 16 éléments avec NEON sur ARM ou SSE2 sur x64 pour effectuer une comparaison d’égalité en parallèle avec la valeur cible ; en cas de correspondance, la fonction renvoie true
  • Les éléments restants, non inclus dans un bloc complet de 16, sont parcourus linéairement

Méthode de benchmark

• Le benchmark génère, pour chaque taille de tableau de 2 à 4096, 100�000 tableaux triés d’entiers non signés 16 bits
• 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 afin de simuler des défauts de cache
  • Mode warm : les requêtes sont regroupées par tableau, et le même tableau est interrogé 100 fois de suite afin de simuler des succès de cache
• La métrique mesurée est le temps moyen par requête ; les algorithmes comparés sont la recherche linéaire (std::find), la recherche binaire (std::binary_search) et SIMD Quad
• Les systèmes de mesure utilisent un Apple M4 avec Apple LLVM, ainsi qu’un processeur Intel Emerald Rapids avec GCC

Résultats des mesures

• En comparant recherche linéaire et recherche binaire, la recherche binaire prend l’avantage quand les tableaux grossissent
• En cache cold, les accès supplémentaires aux données augmentent les échecs de cache, ce qui désavantage davantage la recherche linéaire
• Une fois la supériorité globale de la recherche binaire sur la recherche linéaire établie, la comparaison est faite avec SIMD Quad
• Les résultats diffèrent nettement entre les plateformes Intel et Apple
  • Sur la plateforme Intel, avec cache warm, SIMD Quad est plus de deux fois plus rapide que la recherche binaire
  • Sur la plateforme Intel en cache cold, le gain est plus faible
  • Sur la plateforme Apple, à l’inverse, SIMD Quad est plus de deux fois plus rapide en cache cold, et le gain est plus limité en cache warm
• Dans tous les cas, SIMD Quad est plus rapide que la recherche binaire
• La partie SIMD réduit le travail grâce à des instructions spécialisées, avec moins d’instructions et de branches, ce qui rend le gain de vitesse facile à comprendre

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 standard, a également été comparée
• Sur la plateforme Apple, l’effet de l’approche quaternaire est faible
• Sur la plateforme Intel, dans le cas de grands tableaux en cache cold, l’approche quaternaire constitue une optimisation significative
• 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_quad reçoit un tableau uint16_t, le nombre d’éléments cardinality et la valeur recherchée pos, puis renvoie un booléen
• gap est fixé à 16 ; si cardinality < gap, la recherche se fait avec une simple boucle
• La boucle de recherche par blocs, tant que n > 3, lit les derniers éléments des blocs aux positions 1/4, 2/4 et 3/4, les compare à pos, puis déplace base selon la somme des trois résultats de comparaison
• Ensuite, tant que n > 1, une comparaison sur la moitié restante réduit encore l’intervalle, avant de sélectionner finalement le bloc lo
• Le bloc sélectionné est comparé en deux groupes de 16 éléments via vceqq_u16 sur ARM NEON ou _mm_cmpeq_epi16 sur x64 SSE2
• Pour la zone des éléments restants, on renvoie le résultat de v == pos au point où v >= pos ; si aucun élément n’est trouvé jusqu’au bout, on renvoie false

Conclusion et ressources

• La recherche binaire classique des manuels est un bon algorithme, mais il est possible de la dépasser de façon significative en performances réelles
• Les algorithmes standard ne sont souvent pas conçus en partant du principe du haut niveau de parallélisme des ordinateurs actuels
• SIMD Quad est une approche qui cherche à exploiter à la fois le parallélisme au niveau mémoire et le parallélisme de données
• De meilleurs algorithmes restent possibles, et des approches plus créatives sont nécessaires
• Code source
• Faster intersections between sorted arrays with shotgun