Aujourd'hui, nous partageons du code open source qui peut trier des tableaux de nombres environ dix fois plus rapidement que std::sort de C++, et surpasse les algorithmes spécifiques à l'architecture de pointe, tout en étant portable sur toutes les architectures de CPU modernes. Ci-dessous, nous discutons de la façon dont nous y sommes parvenus.

D'abord, un peu de contexte. Il y a une tendance récente vers les bases de données en colonnes qui stockent consécutivement toutes les valeurs d'une colonne particulière, plutôt que de stocker tous les champs d'un enregistrement ou "ligne" avant ceux de l'enregistrement suivant. Cela peut être plus rapide à filtrer ou à trier, qui sont des éléments clés pour les requêtes SQL ; nous nous concentrons donc sur cette disposition des données.

Étant donné que le tri a été intensivement étudié, comment pouvons-nous trouver une accélération de 10x ? La réponse réside dans les instructions SIMD/vectorielles. Celles-ci effectuent des opérations sur plusieurs éléments indépendants en une seule instruction—par exemple, opérer sur 16 float32 à la fois lors de l'utilisation du jeu d'instructions AVX-512, ou quatre sur Arm NEON.

Si vous connaissez déjà SIMD, vous avez peut-être entendu parler de son utilisation dans les superordinateurs, l'algèbre linéaire pour les applications d'apprentissage automatique, le traitement vidéo, ou les codecs d'images tels que JPEG XL. Mais si les opérations SIMD n'impliquent que des éléments indépendants, comment pouvons-nous les trier, ce qui implique de réorganiser des éléments adjacents du tableau ? Imaginez que nous ayons une manière spéciale de trier, par exemple des tableaux de 256 éléments. Ensuite, l'algorithme Quicksort pour trier un tableau plus grand consiste à le partitionner en deux sous-tableaux : ceux inférieurs à une valeur "pivot" (idéalement la médiane), et tous les autres ; puis à récurser jusqu'à ce qu'un sous-tableau soit d'au plus 256 éléments, et à utiliser notre méthode spéciale pour les trier. Le partitionnement représente la majeure partie du temps CPU, donc si nous pouvons l'accélérer en utilisant SIMD, nous avons un tri rapide.

Heureusement, les jeux d'instructions modernes (Arm SVE, RISC-V V, x86 AVX-512) incluent une instruction spéciale adaptée au partitionnement. Étant donné une entrée séparée de valeurs oui/non (si un élément est inférieur au pivot), cette instruction "compress-store" stocke en mémoire consécutive uniquement les éléments dont l'entrée correspondante est "oui". Nous pouvons ensuite nier logiquement les valeurs oui/non et appliquer à nouveau l'instruction pour écrire les éléments dans l'autre partition. Cette stratégie a été utilisée dans un Quicksort spécifique à AVX-512. Mais qu'en est-il des autres jeux d'instructions comme AVX2 qui n'ont pas de compress-store ? Des travaux antérieurs ont montré comment émuler cette instruction à l'aide d'instructions de permutation. Nous nous appuyons sur ces techniques pour réaliser le premier Quicksort vectorisé portable sur six jeux d'instructions à travers trois architectures, et qui surpasse en fait les tris spécifiques à l'architecture antérieurs.

Notre implémentation utilise les fonctions SIMD portables de Highway, nous n'avons donc pas à réimplémenter environ 3 000 lignes de C++ pour chaque plateforme. Highway utilise compress-store lorsqu'il est disponible et sinon les instructions de permutation équivalentes. Contrairement à l'état de l'art précédent—qui était également spécifique aux entiers 32 bits—nous prenons en charge une gamme complète d'entrées de 16 à 128 bits. Malgré notre implémentation portable unique, nous atteignons des vitesses record sur AVX2, AVX-512 (Intel Skylake) et Arm NEON (Apple M1). Pour un million de nombres 32/64/128 bits, notre code exécuté sur Apple M1 peut produire une sortie triée à des taux de 499/471/466 Mo/s. Sur un Skylake à 3 GHz avec AVX-512, les vitesses sont de 1123/1119/1120 Mo/s. Fait intéressant, AVX-512 est 1,4 à 1,6 fois plus rapide qu'AVX2—une accélération qui vaut la peine pour un effort supplémentaire nul (Highway vérifie quelles instructions sont disponibles sur le CPU et utilise les meilleures disponibles). Lorsqu'il est exécuté sur AVX2, nous mesurons 798 Mo/s, alors que l'état de l'art antérieur optimisé pour AVX2 ne gère que 699 Mo/s. En comparaison, la bibliothèque standard atteint 58/128/117 Mo/s sur le même CPU, nous avons donc réalisé une accélération de 9 à 19x selon le type de nombres.

Auparavant, le tri était considéré comme coûteux. Nous sommes intéressés de voir quelles nouvelles applications et capacités seront débloquées en pouvant trier à 1 Go/s sur un seul cœur de CPU. La source sous licence Apache2 ...