-
Analyse 2,5 fois plus rapide que les parseurs existants grâce au jeu d’instructions SIMD
-
Sélection automatique à l’exécution du parseur optimisé selon le CPU : Haswell (AVX2) / Westmere (SSE4.2) / ARM64 / autres 64 bits
-
Prise en charge de la validation complète de JSON et d’UTF-8
-
Un seul fichier
.h+.cpp -
Utilise seulement 25 % du jeu d’instructions de RapidJSON et 50 % de celui de sajson
4 commentaires
Il existe pas mal de bindings / ports.
ZippyJSON: bindings Swift pour le projet simdjson.
libpy_simdjson: bindings Python hautes performances pour simdjson avec libpy.
pysimdjson: bindings Python pour le projet simdjson.
simdjson-rs: port Rust.
simdjson-rust: wrapper Rust (bindings).
SimdJsonSharp: version C# pour .NET Core (bindings et port complet).
simdjson_nodejs: bindings Node.js pour le projet simdjson.
simdjson_php: bindings PHP pour le projet simdjson.
simdjson_ruby: bindings Ruby pour le projet simdjson.
fast_jsonparser: bindings Ruby pour le projet simdjson.
simdjson-go: port Go utilisant l'assembleur Golang.
rcppsimdjson: bindings R.
Version Rust - https://github.com/simd-lite/simd-json
Présentation du développeur à la QCon : "Parsing JSON Really Quickly: Lessons Learned"
https://www.youtube.com/watch?v=wlvKAT7SZIQ
Transcription de la vidéo de la conférence liée :
https://www.infoq.com/presentations/simdjson-parser/
Je l’ai lue parce que je me demandais comment ils pouvaient atteindre une telle vitesse, et on peut dire que c’est un véritable concentré de magie noire. En gros, les points essentiels sont les suivants.
[Introduction]
La plupart des bibliothèques de parsing JSON sont plus lentes que la vitesse de lecture séquentielle d’un disque
Sur le disque système de moi-même (le conférencier Daniel Lemire), la lecture séquentielle de gros fichiers texte atteint 2,2 GB/s, mais les principales bibliothèques JSON n’arrivaient pas à suivre ce débit en parsing.
Comme il était rare de trouver une bibliothèque dépassant 1 GB/s en parsing, nous avons décidé d’en créer une nous-mêmes.
Le résultat a été un débit capable d’exploiter toute la bande passante du disque. En faisant le calcul, le CPU n’utilisait que 1,5 cycle par octet en entrée. Comment avons-nous obtenu cela ?
[Principes divers]
Éviter au maximum les branchements conditionnels
Par exemple, dans un code simple qui insère des nombres aléatoires dans un tableau, le simple fait d’ajouter un seul
ifpour tester si le nombre est impair le rend 5 fois plus lent. Cela vient du coût élevé des échecs de prédiction de branchement du CPU.Si l’on supprime ce
ifdu code présenté plus haut à l’aide d’opérations sur les bits, les performances reviennent presque à leur niveau initial.En répétant l’exécution du code, la précision de la prédiction de branchement peut augmenter, ce qui réduit la baisse de performances, mais comme il s’agit au fond d’un comportement non déterministe, dès que la prédiction de branchement intervient il devient difficile de prévoir ou de mesurer les performances.
Utiliser activement SIMD pour travailler sur des mots plus larges
Avec les instructions SIMD, on peut utiliser des registres plus larges que 64 bits, et donc traiter davantage de données par cycle. (Par exemple, SSE ou NEON en 128 bits, AVX en 256 bits.) Nous avons donc utilisé SIMD aussi largement que possible. C’est l’une des clés qui ont permis de se limiter à seulement 1,5 cycle par octet de données en entrée.
Pour utiliser SIMD, ils ont recouru à des fonctions intrinsèques dépendantes du processeur. Écrire directement en assembleur n’est pas recommandé.
Éviter les allocations mémoire / d’objets
Mesurer en permanence les performances
Le développement a été mené de façon benchmark-driven. Notre CI inclut des benchmarks de performance.
À noter aussi : pour toute tâche intensive côté CPU, il faut garder à l’esprit que la fréquence de fonctionnement du processeur varie en permanence.
[Cas concrets]
Exemple 1 : vérifier qu’un texte est en UTF-8 valide
Vérifier qu’un flux de données arbitraire correspond à des code points UTF-8 valides est en général une opération impliquant plusieurs branchements conditionnels.
Ils ont conçu une méthode utilisant SIMD pour valider 32 octets de données UTF-8 correctes sans branchement, en au plus 20 cycles.
Comme la valeur entière d’un octet UTF-8 ne peut pas dépasser 244, il suffit de charger les données dans un registre 256 bits avec une instruction SIMD, de soustraire l’entier 244 à chaque octet avec une opération de saturation (saturation arithmetic : opération qui borne l’intervalle des résultats), puis de vérifier qu’aucune valeur non nulle n’apparaît.
Cette méthode est plus de 20 fois plus rapide que l’approche avec branchements !
Exemple 2 : classifier les types de caractères
Pour parser du JSON, il faut classer par catégorie divers caractères comme les virgules, les deux-points, les parenthèses, les espaces, etc.
Sur x86-64 et ARM NEON, il existe des instructions permettant d’interroger d’un coup une table de lookup de 16 octets.
On découpe 1 octet en ses 4 bits de poids fort et ses 4 bits de poids faible, on applique à chacun deux tables de lookup préparées à l’avance, puis on fait un AND sur les résultats.
Le code a l’air sale, mais avec seulement 5 instructions on peut classifier 16 caractères sans branchement.
Exemple 3 : détecter les caractères d’échappement
Peut-on détecter sans branchement les caractères d’échappement, représentés en les préfixant par un antislash (
\) ? Il faut notamment gérer le cas où plusieurs antislashs se suivent afin d’échapper l’antislash lui-même.Dans ce cas, il existe une astuce : il suffit de ne regarder que les antislashs en position impaire.
En utilisant comme constantes des bitmasks représentant les positions paires et impaires, puis en appliquant des opérations bit à bit complexes, on peut filtrer les caractères d’échappement sans branchement.
Une fois les guillemets échappés éliminés, ceux qui restent sont les guillemets servant à délimiter les chaînes.
En représentant sous forme de bitmask les positions de ces guillemets, puis en répétant des opérations XOR, on peut obtenir un bitmask représentant la position des chaînes. Cette partie se traite en une seule instruction sur la plupart des processeurs.
Il existe aussi des astuces pour faire correspondre les ensembles de bits aux positions des chaînes, mais faute de temps, je passe ce point.
Exemple 4 : parser les nombres
Le parsing des nombres est une opération extrêmement coûteuse. Un benchmark sur le parsing de nombres à virgule flottante avec une fonction C bien optimisée n’atteignait que 0,09 GB/s, une vitesse désespérément basse. C’était clairement un goulot d’étranglement.
La plupart des codes de parsing de nombres travaillent généralement octet par octet. Ce n’est absolument pas rapide.
Si l’on prend 8 caractères, qu’on les transforme en un entier 64 bits, puis qu’on les injecte dans une formule particulière imaginée par le conférencier tard un samedi soir, on peut savoir si ces 8 caractères sont bien 8 chiffres consécutifs. C’est particulièrement important, car plus un nombre comporte de chiffres, plus son parsing prend du temps.
J’ai aussi vu sur Stack Overflow un snippet de code pour parser rapidement un entier de 8 chiffres. On peut encore améliorer cela avec SIMD, mais l’important est surtout l’idée de cette stratégie consistant à traiter beaucoup de données d’un coup.
[Autres points]
Runtime dispatch
Comme le code contient beaucoup de parties dépendantes du matériel, on obtient des fonctions optimisées pour chaque processeur, mais faire en sorte qu’au moment de l’exécution la bonne fonction soit appelée selon le type de processeur s’est révélé assez difficile.
On peut ne pas comprendre immédiatement où est la difficulté, mais le vrai problème était de mettre cela en œuvre avec un code portable, indépendant du compilateur. Certains compilateurs avaient des bugs, et le langage lui-même n’offre pas ce support nativement.
Ce point était important parce que simdjson est une bibliothèque open source en un seul fichier d’en-tête, facile à intégrer dans d’autres projets.
Divers
Il existe des wrappers pour plusieurs langages.
Il y a un portage Rust, des portages Go et C# sont en préparation, mais il n’existe pas de portage Java.
Les différentes formules mathématiques utilisées dans ce projet ont été conçues avec le co-auteur Geoff Langdale, et un article associé a été publié dans VLDB Journal. ( https://doi.org/10.1007/s00778-019-00578-5 )
Waouh, c’était une très bonne lecture. Merci !