Google accélère le tri vectorisé des tableaux par 10 avec un quicksort portable
En bref
- Google a publié un algorithme de tri vectorisé utilisant les instructions SIMD (compression, permutation) qui atteint 10 fois la vitesse du std::sort C++.
- Le code fonctionne sur six jeux d'instructions (AVX-512, AVX2, ARM NEON, SVE, RISC-V V) via la bibliothèque Highway sans réécriture plateforme.
- Taux de sortie : 1,1 GB/s sur Skylake AVX-512, 799 MB/s sur AVX2, 499 MB/s sur M1 ARM.
Ce que dit la source
Google présente une implémentation de quicksort vectorisé qui résout le goulot d'étranglement du partitionnement en exploitant les instructions compress-store (ou leur émulation par permutation). Le contexte justifiant ce travail : les bases de données colonaires (stockage vertical par colonne) font du tri un opération critique, et les travaux antérieurs restaient limités à une architecture spécifique (AVX-512, entiers 32-bit). L'équipe affirme avoir conçu le premier quicksort vectorisé portable sans sacrifier les performances absolues.
- L'algorithme s'appuie sur Highway, une bibliothèque SIMD portable, pour éviter 3 000 lignes de C++ à réécrire par plateforme.
- Supporte les entrées 16, 32, 64 et 128 bits, contra le précédent état de l'art limité aux entiers 32-bit.
- Instruction clé : compress-store sur instruction sets modernes (Arm SVE, RISC-V V, x86 AVX-512) ; émulée par permutation sur AVX2.
- Partitionnement récursif jusqu'à 256 éléments, puis tri spécialisé : le partitionnement représente l'essentiel du temps CPU.
- Résultats : 9-19x plus rapide que std::sort selon le type de données et l'instruction set.
Dans les commentaires
Discussion décalée : plusieurs commentateurs soulignent que l'article date de 2022 et que driftsort, ipnsort et glide sort représentent maintenant l'état de l'art. Le fil est peu substantiel, avec surtout des remarques sur la datation, quelques blagues et peu d'objections techniques sérieuses.
- Dépassement : les commentateurs pointent que driftsort et ipnsort, intégrés depuis dans ClickHouse, constituent désormais l'état de l'art post-2022.
- Scepticisme applicatif : un commentateur relève que seules les très grandes entreprises (« MAG 7 ») utiliseraient réellement cet algorithme en recrutement ou en production ; les startups n'en auraient pas besoin.
- Cas d'usage limité : l'algorithme ne trie que des nombres ; un commentateur questionne pourquoi ne pas utiliser radix sort à la place.
Notre lecture
Article de recherche solide datant de 2022, intéressant pour le design d'algorithmes vectorisés et la portabilité SIMD, mais sans impact immédiat pour une DSI en 2024. L'approche via Highway reste pertinente en tant que pattern d'abstraction, mais les implémentations plus récentes (driftsort, ipnsort) la dépassent sur les benchmarks. À consulter si tu optimises un path critique de tri sur données volumineuses ; ignorable sinon.