Quicksort vectorisé atteint une vitesse dix fois supérieure à std::sort

Présentation

Google a publié un algorithme de Quicksort entièrement vectorisé, capable de trier des tableaux numériques jusqu’à dix fois plus rapidement que la fonction std::sort de la bibliothèque standard C++. Le code, sous licence Apache 2.0, repose sur la bibliothèque portable Highway, qui abstrait les instructions SIMD de six jeux d’instructions répartis sur trois architectures (x86 AVX2, AVX‑512, Arm NEON, Arm SVE, RISC‑V V). Cette approche permet d’obtenir des performances record tout en conservant un unique code source d’environ 3 000 lignes.

Architecture et SIMD

Le gain principal provient de l’utilisation de l’instruction compress‑store, disponible nativement sur AVX‑512, Arm SVE et RISC‑V V. Cette instruction transforme un masque booléen (« yes/no » selon que chaque élément est inférieur au pivot) en un flux contigu de valeurs, réalisant en une seule opération le partitionnement du Quicksort. Sur les jeux d’instructions dépourvus de compress‑store, comme AVX2, l’équipe a reproduit le comportement à l’aide de permutations de vecteurs, technique déjà décrite dans la littérature. Highway sélectionne automatiquement la meilleure implémentation en fonction du CPU détecté, évitant ainsi la duplication du code.

Performances et comparaison

Sur un Apple M1 (Arm NEON) le tri de un million d’entiers de 32, 64 et 128 bits atteint respectivement 499 MB/s, 471 MB/s et 466 MB/s. Sur un processeur Intel Skylake 3 GHz avec AVX‑512, les débits sont 1 123 MB/s, 1 119 MB/s et 1 120 MB/s. En mode AVX2, le même algorithme atteint 798 MB/s, surpassant le précédent état de l’art optimisé pour AVX2 (699 MB/s). En comparaison, std::sort ne dépasse que 58 MB/s, 128 MB/s et 117 MB/s sur le même matériel, soit un facteur d’accélération de 9 à 19 fois selon la largeur de donnée. La différence entre AVX‑512 et AVX2 (1,4‑1,6×) se traduit sans effort supplémentaire, Highway adaptant dynamiquement les instructions disponibles.

Portabilité et limites

Le projet supporte des entrées de 16 à 128 bits, élargissant le champ d’application au‑delà des implémentations antérieures limitées aux entiers 32 bits. La stratégie de partitionnement repose sur un sous‑cas spécial de 256 éléments ; au‑delà, le tableau est découpé récursivement jusqu’à atteindre cette taille. Malgré la portabilité, la performance dépend fortement de la présence d’instructions SIMD avancées : sur des CPU dépourvus de vecteurs larges, les gains se réduisent. De plus, le modèle de données ciblé (colonnes contiguës) correspond surtout aux bases de données columnaires, limitant l’impact direct sur les charges de travail à base de structures de lignes.