Static Search Trees : 40 fois plus rapides que la recherche binaire

• Implémentation d’un arbre de recherche statique appelé « S+ tree » pour effectuer des recherches rapides dans des données triées
• Le code proposé dans un billet d’Algorithmica sert de point de départ, puis est optimisé et enrichi avec les idées supplémentaires et améliorations proposées
• Analyse du code assembleur puis optimisation de toutes les instructions possibles afin de maximiser les performances
• Introduction du batching pour traiter plusieurs requêtes en parallèle et améliorer le throughput
• L’objectif est d’exécuter efficacement des requêtes sur des données triées avec le S+ tree tout en maintenant un throughput élevé

1. Introduction et motivation

• Définition du problème :

  • Entrée : une liste triée d’entiers non signés 32 bits vals: Vec<u32>
  • Sortie : une structure de données de taille minimale qui renvoie une valeur supérieure ou égale à une requête donnée (q)
  • Métrique : le nombre de requêtes indépendantes pouvant être traitées par seconde

• Objectif :

  • Construire des structures de données efficaces en bioinformatique, en particulier pour accélérer la recherche dans les suffix arrays destinés à l’indexation des séquences d’ADN
  • Viser des performances maximales en exploitant les capacités du CPU et les instructions SIMD

• Ressources recommandées :

  • Recherche sur la recherche binaire et la disposition des tableaux (« Array Layouts for Comparison-Based Searching »)
  • Ressources d’introduction sur les S+ trees et les B-trees statiques

2. S+ tree et optimisations

2.1 Recherche binaire et disposition Eytzinger

• La recherche binaire de la bibliothèque standard Rust est peu efficace du point de vue du cache, et ses performances se dégradent quand la taille des données augmente
• Disposition Eytzinger :
  • Stocke un arbre binaire de recherche sous forme de tableau afin de maximiser l’utilisation du cache
  • Performances : jusqu’à 4 fois plus rapide que la recherche binaire pour des données qui dépassent le cache L3

2.2 Concept du S+ tree

• S-tree :
  • Forme d’arbre 16-aire contenant 15 valeurs triées par nœud
  • Plus efficace qu’un B-tree et plus compressible que la disposition Eytzinger
• S+ tree :
  • Stocke toutes les données dans les nœuds feuilles, avec duplication dans les nœuds supérieurs
  • Offre une recherche simple et une structure efficace

2.3 Optimisation de la fonction find

• Recherche linéaire de base :
  • Parcourt les données et renvoie la première valeur correspondant à la condition (inefficace)
• Vectorisation automatique :
  • Transformation en code sans branchement, avec un gain de performance multiplié par 2 grâce aux instructions SIMD
• Implémentation SIMD manuelle :
  • Optimisation manuelle à l’aide d’instructions SIMD, avec des performances maximisées en 5 instructions

3. Batching et prefetching

3.1 Batching

• Traite plusieurs requêtes en parallèle pour compenser le temps d’attente mémoire
• Le throughput augmente avec la taille du batch, puis se stabilise à une taille maximale de 16

3.2 Prefetching

• Charge à l’avance le nœud suivant en mémoire, ce qui améliore les performances pour des données dépassant le cache L3
• Combiné au batching, le temps de traitement passe de 45 ns/requête à 30 ns/requête

4. Optimisation de la disposition des données et de la structure

4.1 Modification de la taille des nœuds

• Réduction à 15 valeurs par nœud pour simplifier les opérations de multiplication et améliorer l’efficacité du cache
• Léger gain de performances pour les données tenant dans le cache L3

4.2 Modification de la disposition mémoire

• Expérimentation avec un stockage en ordre inverse ou une configuration minimisant le padding
• Ni la disposition inversée ni la réduction du padding n’ont d’impact majeur sur les performances

5. Partitionnement des données

5.1 Partitionnement basé sur les préfixes

• Séparation des partitions selon les bits de poids fort des données
• Amélioration des performances sur de petits jeux de données, mais avec un surcoût mémoire

5.2 Sous-arbres compressés

• Packing de chaque sous-arbre afin d’améliorer l’efficacité spatiale
• Nécessite de suivre la taille des partitions, avec une légère baisse de la vitesse des requêtes

6. Comparaison multithread

• Avec 6 threads, le temps par requête passe de 27 ns à 7 ns
• La limite de bande passante RAM devient le principal goulot d’étranglement

7. Conclusion et travaux futurs

• Amélioration de performances de plus de 40 fois par rapport à la recherche binaire (1150 ns/requête → 27 ns/requête)
• Travaux futurs :
  • Optimisation de l’équilibrage des données et réduction des accès RAM
  • Gestion des range queries et des requêtes triées
  • Intégration à la recherche dans les suffix arrays

[beenzinozino]

Waouh... si cela était appliqué aux bibliothèques intégrées de divers langages, l’effet d’entraînement pourrait être considérable.

[GN⁺]

Avis Hacker News

• On constate que Rust est de plus en plus utilisé dans les contenus bas niveau liés aux algorithmes. Par le passé, ces contenus étaient surtout écrits en C(++) ou en pseudo-code scientifique

  • Sans bien connaître Rust, il a été possible de comprendre le contenu écrit dans ce langage. C’est comparable au fait qu’un programmeur Rust puisse comprendre des exemples d’algorithmes écrits en C
  • Il serait préférable que Rust se standardise, et ce serait bien que Zig soit aussi utilisé

• La manière de regrouper les requêtes en lots n’a pas été explorée. Le coût principal vient des consultations dans des tables hors cache

  • Avec un nombre suffisant de requêtes, on peut résoudre plusieurs niveaux de l’arbre en une seule fois
  • Cela peut toutefois poser le problème de devoir réordonner les résultats dans le bon ordre de sortie

• Le nombre de valeurs int32 n’est pas très élevé, et le bitmap complet fait 512MB. Pour une structure de données générale, Roaring Bitmaps est recommandé

  • Si seuls des accès simples sont nécessaires, une fonction de hachage parfaite minimale peut valoir le détour

• Il y a de l’étonnement devant les moyens d’améliorer l’efficacité bas niveau en Rust. Une comparaison avec une implémentation C++ serait intéressante

• L’avantage de l’arbre Eytzinger est qu’il existe une formule pour convertir les indices des nœuds en positions de parcours infixe

  • C’est utile lorsque le stockage des clés sous-jacent est un ensemble de clés triées
  • Avec Eytzinger, plusieurs itérations de boucle peuvent être anticipées à l’avance

• Il est surprenant qu’une surcharge d’environ 27ns apparaisse pour rechercher des u32 dans 4GB de mémoire

  • On se demande comment l’optimisation progresse avec une taille de lot de 8
  • Les résultats en multithreading sont aussi intéressants. Le passage de 1 à 6 threads améliore la surcharge d’un facteur 4

• Il y a beaucoup de discussions sur Rust et C++, mais on se demande comment implémenter cela en Common Lisp tout en conservant le SIMD

• À chaque lecture d’un article sur l’optimisation bas niveau, il y a de la gratitude envers l’auteur qui a pris le temps d’économiser des nanosecondes

  • On se demande combien de temps ces optimisations accumulées ont fait gagner à l’humanité

• Il semble qu’il y ait une erreur dans la figure 3 de la section 1.7. Il est suggéré que l’étiquette de l’axe Y de la figure 1 de la section 1.3 devrait être « débit inverse »

• S’il faut parfois prendre en charge l’écriture, on peut utiliser un grand arbre de recherche statique et un petit arbre modifiable

  • Quand il y a suffisamment de changements, on peut les transférer vers une nouvelle version de l’arbre statique