Le SWAR magique de merykitty pour 1BRC : 8 lignes de code expliquées en 3 000 mots

 (questdb.io)
2 points par GN⁺ 2024-03-11 | 1 commentaires | Partager sur WhatsApp
  • Dans 1BRC, le principal goulot d’étranglement était le parsing extrêmement rapide d’un milliard de valeurs de température CSV, et le code SWAR de merykitty par Quân Anh Mai s’est distingué en convertissant les températures en entiers via des opérations ALU fixes, sans if
  • Ce code utilise une approche SWAR (SIMD Within A Register) qui traite d’un seul coup les 8 octets contenus dans un long, en manipulant plusieurs caractères en parallèle dans un registre CPU classique
  • Le flux de traitement enchaîne la détection du signe moins, la suppression du signe, la détection de la position du point décimal, l’alignement au format XY.Z, la conversion des chiffres ASCII, la multiplication magique, puis l’application du signe
  • Le format d’entrée se limite à quatre variantes : -XX.X, -X.X, X.X, XX.X, et les octets sont décalés selon la position du point décimal afin d’obtenir la même disposition de bits malgré les longueurs différentes
  • Au lieu de branches et de boucles, l’implémentation exploite à fond les propriétés des codes ASCII, du complément à deux, des masques de bits et des propriétés décalage-addition de la multiplication pour obtenir un parsing très performant

Le parsing des températures, goulot d’étranglement de 1BRC

  • Dans le One Billion Row Challenge (1BRC), parser des valeurs de température d’un fichier CSV le plus vite possible est devenu le principal goulot d’étranglement
  • Rien qu’avec les optimisations précédentes, un code Java parallèle idiomatique était déjà passé de 71 secondes à 1,7 seconde
  • Le format des températures est simple, mais parser un milliard de valeurs en moins d’une seconde fait fortement s’accumuler le moindre coût
    • Les formats possibles sont -XX.X, -X.X, X.X, XX.X
  • Les premiers participants utilisaient Double.parseDouble(), puis des parseurs personnalisés sans boucle sont apparus
  • Une partie de la solution de @merykitty, signée Quân Anh Mai, traitait le problème avec une seule lecture de fichier et sans if, au point de devenir un élément quasi standard des meilleures solutions 1BRC
  • Le vainqueur, Thomas Wuerthinger, cite d’ailleurs Quân Anh parmi les membres de l’équipe ayant contribué à sa solution

Ce que fait le code de merykitty

  • Le code reçoit un long contenant 8 octets d’entrée CSV et renvoie une valeur de température entière égale à dix fois la température réelle
  • L’entrée provient directement du fichier CSV mmap via une lecture de mémoire native, ce point étant traité séparément
  • Le calcul est constitué de 18 opérations ALU dans un ordre fixe
    • décalages de bits, AND, NOT, XOR
    • additions, soustractions, multiplications
    • Long.numberOfTrailingZeros()
  • numberOfTrailingZeros() utilise une instruction CPU spécialisée via un intrinsic du compilateur JDK
  • Comme il ne s’agit pas d’instructions SIMD dédiées mais de manipuler plusieurs octets avec des registres et instructions CPU ordinaires, l’approche relève bien du SWAR
  • Le code d’exemple a été légèrement adapté pour être plus lisible ; l’original se trouve dans CalculateAverage_merykitty.java

Vue d’ensemble du traitement

  • Le code parse la température selon la séquence suivante
    • vérifier si le premier caractère est - afin de détecter une valeur négative
    • si un signe est présent, mettre cet octet à 0
    • trouver la position du point décimal .
    • déplacer les bits à l’intérieur du long pour que les chiffres correspondent toujours au modèle XY.Z
    • convertir les caractères ASCII en valeurs numériques réelles
    • multiplier chaque chiffre par son poids 1x, 10x, 100x puis additionner
    • appliquer le signe à la fin
  • En apparence, c’est un problème de parsing de haut niveau, mais chaque étape est implémentée uniquement avec des opérations ALU

Étape 1 : détection du signe moins

  • La détection du signe commence avec le code suivant
long negatedInput = ~inputData;
long broadcastSign = (negatedInput << 59) >> 63;
  • En changeant l’ordre dans l’explication, on peut le voir comme ( ~(inputData << 59) ) >> 63
  • En ASCII, le signe moins - a son bit 4 à 0, alors que ce bit vaut 1 pour les caractères numériques
  • En décalant l’entrée de 59 bits vers la gauche, le bit discriminant du premier caractère est déplacé sur le bit de poids fort
  • Après inversion avec NOT, puis un décalage arithmétique à droite de 63 bits, le bit de poids fort est propagé à tout le long
  • Le résultat, broadcastSign, vaut alors tous les bits à 1 si un moins est présent, et tous les bits à 0 sinon

Étape 2 : suppression du caractère de signe

  • Comme l’information sur le signe est désormais stockée dans broadcastSign, on peut retirer le caractère de signe des données d’entrée
long maskToRemoveSign = ~(broadcastSign & 0xFF);
long withSignRemoved = inputData & maskToRemoveSign;
  • Si broadcastSign vaut tout à 1, alors broadcastSign & 0xFF laisse uniquement les 8 bits de poids faible à 1
  • En appliquant NOT, on obtient un masque dont seuls les 8 bits de poids faible valent 0
  • Le AND avec inputData supprime donc le - dans l’octet de poids faible
  • S’il n’y a pas de moins, broadcastSign vaut 0, le masque devient tout à 1 et les octets numériques sont conservés

Étape 3 : trouver la position du point décimal

  • La position du point décimal est calculée par le code suivant
int dotPos = Long.numberOfTrailingZeros(negatedInput & DOT_DETECTOR);
  • Le caractère . a lui aussi la propriété d’avoir son bit 4 à 0, comme le signe moins
  • Pour ne tester que le bit 4 aux positions possibles du point décimal, on utilise le masque DOT_DETECTOR = 0x10101000
  • Dans negatedInput, qui est l’inversion de l’entrée d’origine, ce bit devient 1 à l’endroit du point décimal
  • Long.numberOfTrailingZeros() renvoie la position de ce bit à 1
  • Dans l’exemple -10.8, le point décimal se trouve à la position de bit 28, donc dotPos = 28

Étape 4 : alignement sur un modèle fixe

  • À partir de la position du point décimal, l’entrée est décalée vers la gauche pour toujours correspondre au même modèle
long alignedToTemplate = withSignRemoved << (28 - dotPos);
  • Le modèle visé est le suivant
0 0 0 Z . Y X 0
  • Ici, X représente les dizaines, Y les unités, et Z le premier chiffre après la virgule
  • Le 0 ne désigne pas le caractère ASCII "0", mais un octet de valeur 0
  • Après suppression du signe, l’entrée peut se présenter dans l’une des quatre dispositions suivantes
    • 0 0 0 Z . Y X 0
    • 0 0 0 0 Z . Y 0
    • 0 0 0 0 Z . Y X
    • 0 0 0 0 0 Z . Y
  • Pour -10.8, on a déjà dotPos = 28, donc le décalage vaut 0
  • Pour -7.7, la position du point est 20 bits, donc on décale de 8 bits, soit un octet, vers la gauche afin de placer 0 à l’emplacement de X

Étape 5 : convertir les chiffres ASCII en valeurs

  • Une fois alignés, il ne reste plus qu’à extraire les valeurs numériques des caractères ASCII
long digits = alignedToTemplate & ASCII_TO_DIGIT_MASK;
  • Les chiffres ASCII 0 à 9 vont de 0x30 à 0x39 en hexadécimal
  • En ne gardant que les 4 bits de poids faible, le code caractère devient la vraie valeur numérique
  • On applique un masque avec F uniquement aux positions des chiffres dans le modèle
0 0 0 Z . Y X 0
000000F000F0F00
  • Pour -10.8, après application du masque, il ne reste que les valeurs correspondant à Z=8, Y=0, X=1

Étape 6 : sommer les poids des chiffres avec une multiplication magique

  • La valeur absolue finale doit être calculée comme 100 * X + 10 * Y + Z
  • En exploitant le fait qu’une multiplication peut se décomposer en décalages et additions, le calcul des poids de plusieurs chiffres est effectué d’un seul coup avec une unique multiplication
  • Si l’on commence par considérer X + Y + Z, on peut additionner des versions décalées de digits aux positions 0, 16 et 24 bits afin de regrouper les sommes dans certaines plages de bits
  • Cette combinaison décalage-addition peut se réécrire comme la multiplication suivante
0x1 + 0x10000 + 0x1000000
  • En pratique, comme les poids diffèrent selon les chiffres, MAGIC_MULTIPLIER est construit ainsi
MAGIC_MULTIPLIER = 0x1 + 10 * 0x10000 + 100 * 0x1000000;
  • Le calcul s’écrit alors
absValue = ((digits * MAGIC_MULTIPLIER) >>> 32) & 0x3FF;
  • 0x3FF est un masque destiné à extraire un résultat de largeur 10 bits
  • 100 * X peut s’étendre jusqu’à 10 bits et chevaucher des bits adjacents, mais les deux bits de droite de Y * 100 sont toujours à 0, ce qui laisse l’espace nécessaire
  • merykitty a laissé à cet endroit le commentaire // That was close :)

Étape 7 : appliquer le signe sans branchement

  • À ce stade, on dispose de la valeur absolue absValue et de l’information de signe dans broadcastSign
  • broadcastSign se comporte comme 0 pour un nombre positif et comme -1 pour un nombre négatif
  • En complément à deux, un nombre négatif s’écrit comme suit
-n = NOT(n) + 1
  • XOR peut servir de NOT conditionnel
    • n XOR -1 donne NOT(n)
    • n XOR 0 donne n
  • Le +1 optionnel est géré par -broadcastSign
temperature = (absValue ^ broadcastSign) - broadcastSign;
  • Au final, sans aucun if, les valeurs positives restent inchangées et les valeurs négatives sont converties en entier négatif en complément à deux

Bonus : calcul de la position de début de la ligne CSV suivante

  • Dans la solution 1BRC complète, il faut aussi calculer à faible coût la position de début de la ligne CSV suivante
  • Après le point décimal viennent toujours un chiffre décimal puis un saut de ligne, donc la position du point suffit à retrouver le début de la ligne suivante
  • Comme dotPos est une position en bits, on effectue un décalage de 3 bits vers la droite pour diviser par 8
nextLineStart = (dotPos >>> 3) + 3;
  • Le +3 sert à viser le premier octet après le point, le chiffre décimal et le saut de ligne

Conclusion

  • Le code SWAR de merykitty parse les quatre formats de chaîne de température à l’aide d’opérations binaires fixes uniquement
  • Les idées centrales sont les propriétés bit à bit du code ASCII, l’alignement basé sur la position du point décimal, l’extraction des chiffres par masque, la somme des poids via une multiplication, et l’application du signe via le complément à deux
  • Découpé étape par étape, le fonctionnement devient lisible, mais le fait d’avoir assemblé tout cela en quelques jours pour un challenge en ligne reste particulièrement impressionnant

À lire aussi

1 commentaires

 
GN⁺ 2024-03-11
Commentaires Hacker News
  • L’explication étape par étape est vraiment excellente
    J’avais remarqué il y a plus de deux ans que byte array view var handle se prêtait plutôt bien à la création de routines SWAR efficaces en Java/Scala
    On trouve aussi ici de nombreux exemples d’usage de SWAR, comme le parsing de chaînes Base16/64, java.time.* ou le parsing direct de valeurs numériques depuis des tableaux d’octets : https://github.com/plokhotnyuk/jsoniter-scala/blob/master/js...
  • L’article est bon et c’est une excellente solution dans le contexte du code, mais cette approche suppose que les données sont au bon format
    Une grande partie de la valeur d’un parseur éprouvé en production réside dans la détection et la récupération d’erreurs efficaces
    • Ce serait intéressant d’analyser comment une entrée invalide peut affecter la sortie
      Et je me demande aussi combien de travail serait nécessaire pour la détecter de façon à renvoyer une valeur d’erreur sentinelle, comme dans le style de code actuel
      Pas assez intéressant pour que je le fasse moi-même ;-)
  • La technique qui consiste à multiplier chaque puissance de dix d’un champ de bits numérique puis à faire les décalages/additions avec MUL est une méthode assez connue
    Voir l’article de Lemire : https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-qui...
  • D’après l’article, SWAR signifie SIMD Within A Register
  • Si ce genre de sujet vous plaît, l’article de recherche sur simdjson utilise aussi des techniques similaires, il est très bien écrit et les exemples sont bons
    Article : https://arxiv.org/abs/1902.08318
    Github : https://github.com/simdjson/simdjson
    • Ce n’est pas du SWAR, mais je vois pourquoi c’est intéressant
  • Quelqu’un peut-il expliquer pourquoi BRC n’est pas limité par les E/S ? Je ne comprends pas pourquoi le CPU serait le goulot d’étranglement
    • Sur les systèmes modernes, les E/S disque locales ne sont plus le goulot d’étranglement : https://benhoyt.com/writings/io-is-no-longer-the-bottleneck/
      En plus, le 1BRC officiel précise que les résultats sont évalués depuis un RAM disk afin d’exclure complètement la vitesse d’E/S : https://github.com/gunnarmorling/1brc?tab=readme-ov-file#eva...
      “Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant)”
    • Pour le contexte, il y a une interview avec Daniel Lemire. Il a bâti toute sa carrière sur l’observation que les E/S ne sont pas toujours le goulot d’étranglement : https://corecursive.com/frontiers-of-performance-with-daniel...
    • Je n’ai pas étudié ce problème en détail, mais on peut prendre la question à l’envers. Pourquoi pensez-vous que ce sont les E/S mémoire qui font goulot d’étranglement ?
      D’après ma compréhension limitée, on charge séquentiellement un gros fichier texte en L1 et chaque valeur est lue une fois. Sur la plupart des processeurs, on peut effectuer deux de ces lectures par cycle. La partie lente serait l’acheminement de la RAM vers le L1, mais les lectures séquentielles sont assez rapides
      Ensuite, on traite chaque lecture. À vue de nez, cela semble représenter environ 4 cycles dans une version optimisée. Puis il faut écrire le résultat quelque part, ce qui nécessitera probablement une ou deux lectures aléatoires au préalable. Est-ce cela que vous considérez comme un goulot d’étranglement d’E/S ?
      Je ne dis pas qu’il est évident que ce soit limité par le CPU, mais il ne me semble pas évident non plus que ce ne soit pas le cas
      Édit : je n’avais pas envisagé que vous vouliez peut-être dire les “E/S disque”. Comme d’autres l’ont dit, ici ce n’est en pratique pas un facteur
    • Les tests sont exécutés sur memfs. Le fichier et tout le reste sont déjà en RAM dès le départ
    • Le jeu de données est assez petit pour tenir dans le page cache du noyau Linux, et le benchmark est répété 5 fois d’affilée, donc la première exécution peut être limitée par les E/S disque, mais pas les 4 suivantes
      Autrement dit, toutes les données se retrouvent en RAM, plus précisément dans le page cache
  • Sur 68000, j’utilisais SWAR de façon assez efficace. On traitait 4 octets en parallèle avec une seule instruction
    Si je me souviens bien, la gestion des débordements était délicate. J’aime vraiment beaucoup cet article
  • Quelqu’un a dit : “Le vrai mystère, c’est qu’une seule personne travaillant seule ait pu construire tout ça en quelques jours, dans le cadre d’un défi en ligne dont la récompense est un t-shirt et un mug à café.” Pourquoi serait-ce un mystère ?
    Il existe encore des gens qui savent réellement programmer le CPU et comprennent ce qu’ils font
    Le vrai mystère, c’est plutôt que la majorité de ceux qui se disent programmeurs semblent manquer de compréhension profonde, et ne semblent même pas savoir à quel point ce manque est grave
  • En C#, il n’est pas nécessaire d’utiliser ce genre d’astuces SWAR. Le langage fournit à la place des API SIMD cross-platform de premier ordre
    Le fait que cela fonctionne bien en pratique se voit dans ce qui semble être la solution C# la plus rapide parmi les 1BRC publiés jusqu’ici : https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
  • Peut-on vectoriser ça avec SSE ? L’essentiel du traitement semble pouvoir se faire avec un vecteur de quatre entiers 32 bits
    La question est de savoir si le coût de construction du vecteur initial et d’extraction du résultat n’est pas excessif
    • Oui, et plusieurs autres implémentations de 1BRC l’ont fait aussi
      En revanche, je doute que HotSpot puisse le faire tout seul, et il y a aussi le fait que la plupart des soumissions 1BRC étaient exécutées avec Graal pour réduire le surcoût de démarrage
      Le SSE2 de base n’a pas de multiplication 32 bits ou 64 bits, donc la multiplication 32×32→64 bits pose problème, mais SSE4.1 ajoute justement pmuldq, qui fait exactement ce qu’il faut. Comme le résultat est sur 64 bits, il faut toutefois faire cette opération deux fois pour traiter un vecteur complet d’entiers 32 bits
    • Le champ de température est mêlé au champ de nom, donc il semble difficile d’obtenir un gain supplémentaire avec SSE
      De plus, le champ de température a une longueur variable, donc même avec un stockage en colonnes il est possible qu’il n’y ait pas de gain
      En revanche, SSE a été appliqué avec succès à la recherche du délimiteur entre le nom et la température
    • Ce genre de code semble pouvoir être vectorisé automatiquement, soit dès le départ, soit après que HotSpot a détecté les hotspots