Présentation du concours 1BRC
- Dans le concours 1BRC, on prévoyait qu'après avoir traité les « suspects habituels », l'analyse des températures depuis le fichier CSV deviendrait le goulot d'étranglement.
- Les températures peuvent apparaître sous quatre formes :
-XX.X, -X.X, X.X, XX.X, et au départ on utilisait un appel à la bibliothèque Double.parseDouble().
- Mais des solutions sur mesure sont rapidement apparues, et l'une d'elles semblait être une méthode optimisée sans boucle avec seulement deux branches.
- Puis la solution proposée par Quân Anh Mai (@merykitty) a enflammé le hashtag #1BRC sur Twitter. Cette solution n'utilisait qu'une seule lecture de fichier, sans instruction
if.
Analyse du SWAR magique de merykitty
- Le code de merykitty se compose de seulement 18 opérations ALU et inclut un unique appel à une fonction bas niveau,
numberOfTrailingZeros().
- Le nombre
long en entrée contient 8 octets issus du CSV, et la sortie est la température sous forme entière (10 fois la température réelle).
- Cette technique est appelée « SIMD Within A Register » (SWAR) et utilise des registres CPU et des instructions standard.
- Le code passe par des étapes comme la détection d'un nombre négatif, la suppression du caractère de signe, la recherche de la position du point décimal, l'alignement du contenu sur un modèle, la conversion des caractères ASCII en valeurs numériques, la multiplication de chaque chiffre par son poids puis leur addition, et enfin l'application du signe.
- Toutes ces étapes sont réalisées uniquement à l'aide d'opérations ALU.
Conclusion
- La vraie énigme, impossible à expliquer dans un billet de blog, est de savoir comment merykitty a pu accomplir tout cela seule en quelques jours.
- QuestDB est open source et offre une insertion rapide des données ainsi que des capacités d'analyse SQL sous licence Apache 2.0.
L'avis de GN⁺
- Cet article montre la complexité et la créativité de la technique SWAR conçue pour résoudre un simple problème d'analyse de températures. Il met en lumière la puissance des opérations sur les bits et l'importance de l'optimisation en programmation.
- Cette approche peut constituer un cas particulièrement intéressant pour les ingénieurs logiciels débutants qui s'intéressent à la programmation système ou au développement d'applications sensibles aux performances.
- Pour mieux comprendre les opérations sur les bits et l'optimisation, il peut être utile de chercher des concours de programmation en ligne ou des tutoriels traitant de sujets ou de problèmes similaires.
- Des recherches complémentaires sont nécessaires pour voir comment cette technique peut être appliquée dans des environnements industriels réels, et s'il existe d'autres bases de données ou systèmes utilisant des techniques d'optimisation comparables.
- Lors de l'adoption de systèmes comme QuestDB, il faut prendre en compte non seulement les gains de performance, mais aussi d'autres facteurs comme la maintenabilité, la lisibilité du code et le support technique à long terme.
1 commentaires
Commentaires Hacker News
Résumé des commentaires Hacker News liés à l’article sur simdjson :
Interprétation du contexte du code : la solution proposée est remarquable, mais elle suppose que les données sont bien structurées. Une vérification d’erreurs efficace et des mécanismes de récupération ont une grande valeur dans les parseurs expérimentés.
Technique de parsing des nombres : multiplier les bitfields numériques par les puissances de 10 correspondantes, puis utiliser
MULpour faire les décalages/additions, est une technique connue. Voir le blog de Lemire.Explication de SWAR (SIMD Within A Register) : il existe de nombreux exemples d’implémentation efficace de routines SWAR en Java/Scala à l’aide de var handles de vues sur des tableaux d’octets.
Définition simple de SWAR : "SIMD Within A Register" consiste à effectuer des opérations SIMD à l’intérieur d’un seul registre.
Question sur le goulot d’étranglement I/O de BRC (Branchless Ray Casting) : il est difficile de comprendre pourquoi le CPU serait le goulot d’étranglement.
Retour d’expérience sur l’usage de SWAR sur 68000 : il était possible de traiter 4 octets en parallèle d’un coup, mais la gestion des débordements était délicate. L’article a beaucoup plu.
Espace d’états et superoptimiseur : question sur l’existence d’un superoptimiseur capable de produire des résultats similaires, étant donné la petite taille de l’espace d’états.
Instructions AVX et prise en charge SIMD de Java : cet algorithme pourrait être exécuté avec un parallélisme 32x via les instructions AVX, mais il est regrettable que Java ne prenne pas correctement en charge l’utilisation du SIMD du CPU, sauf dans certains cas.
Compréhension des manipulations de bits : cet article a permis de mieux comprendre les manipulations de bits que n’importe quel autre auparavant, et l’auteur est remercié pour avoir proposé une solution Java au challenge 1BRC.