Construire un parseur JSON haute performance

• La présentation de Dave Cheney à la GopherCon Singapore 2023 traite du processus de conception d’un parseur JSON en streaming en Go, avec un objectif de débit plus élevé et moins d’allocations tout en conservant une API proche de encoding/json
• JSON n’ayant pas d’indicateur de longueur, il faut lire l’entrée jusqu’au bout, et la borne basse de performance est au minimum read(N)+parse(N) ; la contrainte essentielle consiste donc à réduire les revisites d’octets et de tokens, les copies, les allocations et les appels de fonctions sur le hot path
• encoding/json.Decoder.Token renvoie les tokens sous forme d’interface{}, ce qui est pratique, mais fait s’échapper les valeurs concrètes vers le tas et entraîne des allocations proportionnelles au nombre de tokens ; même un unique token "hello" provoque 3 allocs/op
• pkg/json réduit le coût du hot path grâce à NextToken, qui renvoie un sous-slice []byte de l’entrée, à une fenêtre glissante dans byteReader, à l’inlining manuel, aux appels directs des méthodes d’état et à l’élimination des bounds checks
• Au final, pkg/json.Scanner tokenise sans allocation lorsqu’un buffer est fourni, Decoder.Token est 2 à 3 fois plus rapide que encoding/json.Decoder.Token, et Decoder.NextToken, avec bien moins d’allocations, affiche des performances 8 à 10 fois supérieures

---

Objectif et contraintes de base

• L’objectif est de montrer un cas de conception de package Go pour créer un parseur JSON haute performance
• Trois objectifs de conception sont visés
  • prendre en charge le traitement en streaming sans charger toute l’entrée en mémoire
  • rester raisonnablement compatible avec l’API haut niveau json.Decoder de encoding/json, tout en offrant un débit supérieur et moins d’allocations
  • proposer, en plus de l’API encoding/json, une API plus efficace sans allocation ou avec borne d’allocation
• Mettre toute l’entrée en mémoire avant traitement crée un risque de disponibilité quand la taille de l’entrée est inconnue ou infinie, et augmente aussi la latence avant traitement
• La lecture en streaming permet de traiter les données dès leur arrivée et de faire se chevaucher lecture et traitement

Complexité temporelle du parsing JSON

• JSON n’a pas de marqueur de longueur, donc il faut lire toute l’entrée pour savoir combien lire
• Pour parser le 1 000e élément d’un tableau JSON, il faut aussi lire et traiter les 999 éléments précédents ; on ne peut donc pas sauter le traitement de l’entrée
• La borne basse de performance est proportionnelle à la taille de l’entrée et ne se limite pas à une simple lecture : il faut aussi traverser la machine à états JSON pour trouver le début et la fin des tokens, d’où un minimum de read(N)+parse(N)
• Les critères pour réduire le coût supplémentaire sont les suivants
  • si N octets ont été lus, chaque octet doit idéalement être traité une seule fois
  • un même token ne doit être traité qu’une seule fois
  • sur le hot path de Scanner ou Decoder, le nombre d’appels de fonction doit être limité à O(tokens) plutôt qu’à O(bytes)
  • réduire les copies afin de limiter le nombre de revisites des mêmes octets
  • réduire les allocations pour diminuer les allocations sur le tas, les accès à des structures partagées, les verrous, la contention de cache et le coût du GC

Tokenisation et conception d’API

• Un décodeur JSON se décompose globalement en deux étapes
  • un scanner ou tokenizer qui transforme un flux d’octets en flux de tokens JSON
  • un unmarshaler qui applique le flux de tokens JSON à des objets Go
• encoding/json.Decoder.Token renvoie les tokens sous forme d’interface{}
  • les chaînes sont représentées par string, les nombres par float64, les booléens par bool, null par nil, et les délimiteurs par json.Delim
  • cette approche est pratique, car elle transporte à la fois la valeur du token et son type
• Cette commodité a un coût
  • Brad Fitzpatrick qualifie l’API Token de garbage factory
  • par conception de l’API Decoder.Token, les valeurs concrètes allouées pour chaque token s’échappent vers le tas
  • le nombre d’allocations est donc lié au nombre de tokens de l’entrée
• Sur un benchmark avec un unique token "hello", encoding/json affiche 355ns/op, 19.7MB/s, 37.0B/op et 3.00 allocs/op
• La conception de l’API détermine les allocations, et les allocations peuvent avoir un impact direct sur les performances

Tokens []byte et information de type implicite

• On peut connaître le type d’un token JSON à son premier caractère
  • {, } : début et fin d’objet
  • [, ] : début et fin de tableau
  • t : true
  • f : false
  • n : null
  • " : chaîne
  • -, 0~9 : nombre
• L’API Decoder.NextToken de pkg/json ne convertit pas l’entrée []byte en valeur Go ; elle renvoie directement comme token un sous-slice des octets de l’entrée
• Le premier octet du []byte renvoyé indique le type du token
• Cette API a des contraintes
  • la sortie n’est pas une copie mais un sous-slice de l’entrée, sa durée de validité est donc limitée
  • cela ressemble à l’API de bufio.Scanner
  • pour manipuler plus confortablement le type de token ou les valeurs réelles de chaîne et de nombre, une abstraction de plus haut niveau est nécessaire

Lecture efficace : byteReader

• L’approche traditionnelle io.Reader.Read copie les données du reader dans un buffer, et cette copie a elle aussi un coût
• io.Reader.Read laisse la gestion du buffer à l’appelant
  • si l’on lit un octet à la fois, il peut être nécessaire de conserver les octets déjà parcourus ou de prévoir de l’espace pour revenir en arrière
  • lire dans un grand buffer puis chercher le début et la fin d’un token impose beaucoup de gestion, de copies et d’extensions de buffer lorsque la fin du token n’est pas dans le buffer
• Comme alternative, la présentation utilise byteReader, inspiré de iopipe de Steven Schveighoffer et d’idées de Phil Pearl
• byteReader fournit une fenêtre glissante au-dessus d’un io.Reader ; il ressemble à bufio.Reader, mais avec une API plus efficace
  • window() renvoie la fenêtre actuelle des données non encore lues
  • release(n) jette les n premiers octets de la fenêtre
  • extend() lit davantage de données depuis le reader sous-jacent pour étendre la fenêtre
• Le benchmark de recherche de caractères d’espacement sert de référence minimale : il visite chaque caractère et vérifie seulement s’il s’agit d’un espace, avec environ 2.04 à 2.07GB/s sur plusieurs entrées
• Le code d’exemple du compteur d’espaces est disponible sur github.com/davecheney/whitespace

Optimisation du scanner

• Scanner.Next saute les espaces intermédiaires, détermine le token à partir du premier caractère de la fenêtre, puis lit jusqu’à la fin du token
• Les performances initiales de Scanner.Next ne représentent qu’environ 1/4 à 2/5 de la référence basée sur les espaces
  • par exemple : Scanner/canada 510MB/s, citm_catalog 677MB/s, sample 837MB/s
• La première optimisation consiste à remplacer les mises à jour du champ s.offset par une variable locale offset
  • s.offset vaut 0 à l’entrée et à la sortie de la fonction, donc ses modifications internes ne sont pas visibles de l’extérieur
  • l’usage d’une variable locale permet au compilateur d’éviter des écritures mémoire temporaires
  • citm_catalog passe de 2.52ms à 1.80ms, soit une baisse de 28.46 %, et sample de 828µs à 528µs, soit 36.24 %
• Si l’effet varie selon les entrées, c’est à cause de la différence de nombre d’espaces
  • canada ne contient que 33 espaces
  • citm en contient 1 227 563
• La deuxième optimisation consiste à inliner manuellement Scanner.token dans Scanner.Next
  • le compilateur Go ne peut pas inline automatiquement Scanner.token, parseString, parseNumber, Scanner.Next, etc., à cause des boucles for et de la complexité des fonctions
  • Scanner.Next et Scanner.token étant appelés à chaque token de l’entrée, cela représente le coût de deux appels de fonction par token
• Après inlining manuel, le débit progresse de 9 à 24 %
  • canada passe de 512MB/s à 642MB/s, soit +24.50 %
  • citm_catalog passe de 960MB/s à 1105MB/s, soit +15.16 %
  • sample passe de 1.33GB/s à 1.46GB/s, soit +9.11 %
• On peut résumer l’effet des optimisations en deux points
  • réduire les mises à jour de s.offset d’une fois par octet à une fois par token
  • éviter les appels de fonction sur le hot path peut améliorer les performances

Validation et Decoder.NextToken

• Le scanner seul permet de découper les tokens, mais un traitement JSON complet nécessite une validation d’état
• JSON est une machine à états, et le token autorisé ensuite dépend du token courant
  • par exemple, après avoir lu { puis "username", seul : est valide
• Decoder.NextToken ajoute une logique d’état au-dessus de Scanner.Next pour vérifier que la séquence de tokens est valide
• Les états incluent la valeur, la chaîne clé d’objet, les deux-points d’objet, la valeur d’objet, la virgule d’objet, la valeur de tableau, la virgule de tableau, l’état de fin, etc.
• Même dans l’implémentation initiale de validation, pkg/json est 8 à 10 fois plus rapide que encoding/json
  • canada : pkg/json 399MB/s, encoding/json 34.6MB/s
  • citm_catalog : pkg/json 713MB/s, encoding/json 87.1MB/s
  • sample : pkg/json 1.23GB/s, encoding/json 216MB/s

Optimisation des transitions d’état

• Un switch est au cœur de Decoder.NextToken
• Un switch classique peut être implémenté comme une série de if, ce qui allonge la chaîne de branchements dans le flux d’instructions et sollicite davantage le prédicteur de branchement du CPU
• Il est possible d’utiliser une table pour retrouver la méthode d’état à partir de la valeur d’état, mais l’implémentation d’exemple ne compile pas à cause d’une boucle d’initialisation
• À la place, la présentation utilise les method expressions de Go pour stocker directement une méthode dans d.state au lieu d’une valeur d’énumération d’état
  • Decoder.NextToken appelle alors directement l’état courant via return d.state(d, tok)
• Cette approche de type computed goto n’apporte pas à elle seule de gros gains
  • certaines entrées ne changent presque pas, et twitter, code, example deviennent même légèrement plus lentes
  • sample gagne 1.15 %
• En revanche, ce changement rend possible l’optimisation suivante : l’outlining

Outlining et élimination des bounds checks

• Après outlining, Decoder.NextToken ne fait plus que return d.state(d), et chaque méthode d’état appelle directement d.scanner.Next()
• Comme tok n’est plus passé comme argument aux méthodes d’état, on économise 3 words sur la pile d’appel
• Le test len(tok) < 1 et le switch tok[0] se retrouvent dans la même fonction, ce qui permet l’élimination des bounds checks
  • auparavant, la vérification len(tok) se trouvait dans Decoder.NextToken, et les méthodes d’état étaient appelées via des method expressions, donc non inlinées
  • par conséquent, l’accès tok[0] dans les méthodes d’état nécessitait un bounds check
  • en effectuant le contrôle de longueur dans la même fonction, le compilateur peut prouver que tok a une longueur d’au moins 1
• Decoder.NextToken devient lui-même plus simple et peut être inliné
  • l’appelant, au lieu de voir dec.NextToken(), voit en pratique un appel direct à la méthode d’état courante
  • le coût de l’appel de fonction disparaît

Résultats finaux des benchmarks

• Le composant le plus bas niveau, pkg/json.Scanner, effectue une tokenisation en streaming sans allocation lorsqu’on lui fournit quelques Ko de buffer
  • canada : 638.78MB/s, 0 B/op, 0 allocs/op
  • citm_catalog : 1110.51MB/s, 0 B/op, 0 allocs/op
  • sample : 1471.01MB/s, 0 B/op, 0 allocs/op
• pkg/json.Decoder.Token est 2 à 3 fois plus rapide que encoding/json.Decoder.Token
  • canada : 101.98MB/s vs 33.19MB/s
  • citm_catalog : 333.23MB/s vs 82.71MB/s
  • sample : 788.59MB/s vs 209.12MB/s
• pkg/json.Decoder.NextToken réalise bien moins d’allocations et va 8 à 10 fois plus vite
  • canada : 466.52MB/s, 136 B/op, 3 allocs/op vs 34.42MB/s, 17,740,399 B/op, 889,106 allocs/op
  • citm_catalog : 798.58MB/s, 136 B/op, 3 allocs/op vs 86.08MB/s, 5,661,597 B/op, 324,692 allocs/op
  • sample : 1346.85MB/s, 1144 B/op, 9 allocs/op vs 217.44MB/s, 723,781 B/op, 26,095 allocs/op
• Au niveau d’API le plus élevé, pkg/json peut aussi faire l’unmarshal vers des objets Go de la même manière que encoding/json
  • canada : 82.08MB/s vs 58.70MB/s
  • citm_catalog : 215.66MB/s vs 104.00MB/s
  • sample : 615.99MB/s vs 128.04MB/s
• Le lien vers la présentation est dave.cheney.net/paste/gophercon-sg-2023.html, et le code est disponible sur github.com/pkg/json

Enseignements de conception

• Les allocations ont un impact sur les performances

  • même si le GC alloue vite et collecte efficacement, ne pas allouer reste toujours plus rapide
  • la conception de l’API peut supprimer les allocations
  • l’essentiel du gain de vitesse de ce package vient de la réduction des allocations
  • le temps non dépensé dans le chemin d’allocation sur le tas et dans les cycles de GC est réinvesti dans le scan
  • l’API encoding/json.Decoder impose des allocations parce qu’elle renvoie les valeurs primitives sous forme d’interface{}
  • les valeurs s’échappent vers le tas et deviennent en pratique des pointeurs vers des valeurs
  • dans le traitement de données, les allocations peuvent être le coût de performance le plus important d’un algorithme
  • la seconde plus grande source de gain consiste à réduire avec soin le coût par octet et le coût par token
  • il est essentiel de remplacer les appels de fonction par octet par des appels de fonction par token
  • le point de départ était l’hypothèse que encoding/json est plus lent à cause de son API ; si l’on accepte une API différente, on peut obtenir des gains de 2 à 3 fois sur certains chemins d’unmarshal et de 8 à 10 fois sur la tokenisation

[GN⁺]

Avis sur Hacker News

• Ça a l’air plutôt bien. Au cours de ma carrière, j’ai déjà écrit beaucoup trop de parseurs JSON, mais c’est vraiment appréciable d’avoir une référence qui montre étape par étape comment concevoir un parseur JSON raisonnable et rapide.
  Cela dit, JSON n’a pas absolument besoin d’un tokenizer explicite. On peut supprimer la notion de token et fusionner complètement parsing et tokenisation. C’est généralement ce qu’on fait, et l’ensemble devient plus simple.
  Dans des langages comme ECMAScript, c’est bien plus difficile : certaines constructions ressemblent à un sous-ensemble de la syntaxe d’expressions entre parenthèses, comme les fonctions fléchées, puis ne sont tranchées qu’en fonction de l’apparition ou non de =>, ce qui peut nécessiter un lookahead arbitrairement long.

  • Je me demande quel genre de travail il faut avoir fait pour pouvoir dire qu’on a « écrit beaucoup trop de parseurs JSON » au cours de sa carrière.

• C’est un bon article à suivre, et il donne une trajectoire claire pour le faire soi-même.
  Si l’on vise les performances brutes en production, le projet de Daniel Lemire, https://github.com/simdjson/simdjson, vaut aussi le coup d’œil. Il existe aussi un port Go par MinIO : https://github.com/minio/simdjson-go.

  • Si la forme du JSON est toujours la même, on peut même faire mieux qu’un parseur JSON généraliste.
  • Quand j’avais comparé les performances de plusieurs parseurs JSON, les parseurs basés sur SIMD m’avaient semblé décevamment lents par rapport à mes attentes.
  • La bibliothèque JSON la plus rapide en Go est faite par l’entreprise derrière TikTok.
  • simdjson n’est plus le plus rapide depuis très longtemps.

• Ce que j’ai appris en écrivant des parseurs JSON rapides dépend beaucoup des spécificités de chaque langage, mais on peut généraliser ainsi :
  Lors de la tokenisation, il faut éviter les allocations sur le tas. Le tokenizer devrait plutôt renvoyer une structure allouée sur la pile, ou être une fonction qui renvoie un token int64 empaquetant la position de début, la longueur, le type de token, etc.
  Pour le parsing aussi, il faut éviter les allocations sur le tas, et l’on peut proposer une interface du type getString(key String) pour les clients qui veulent découper le buffer.
  Lors de la désérialisation vers un objet dont les champs sont connus à la compilation, on génère généralement un switch sur la longueur de la clé avant de comparer les valeurs de chaînes.
  Dans des pipelines de données qui traitent beaucoup de JSON, le simple choix de la bibliothèque JSON pouvait entraîner un écart de performance de 3 à 10×, et les principaux parseurs ont généralement tendance à allouer des objets.
  Si les classes à sérialiser et désérialiser sont connues à la compilation, Jackson en Java s’en sort plutôt bien, mais avec du code soigneux et du profiling on peut encore gagner environ un facteur 2.
  À l’inverse, si l’on traite du JSON arbitraire, les parseurs grand public cherchent à faire beaucoup d’allocations ; un parseur plus intrusif écrit sur mesure peut les éviter, avec des gains de performance très importants quand on traite de quelques milliers à des millions d’objets par seconde.

• J’ai créé un tokenizer et un parseur GraphQL avec une approche similaire ; lui aussi ne fait pas d’allocation mémoire et il est assez rapide. Si le code vous intéresse, voyez https://github.com/wundergraph/graphql-go-tools.

  • Mon propre monstre peut aussi valoir le détour : https://github.com/graph-guard/gqlscan
    J’ai aussi fait une présentation sur le sujet, mais malheureusement elle n’a pas été enregistrée. J’ai failli devenir fou à essayer d’extraire le maximum de Go :D
  • Je me demande à quel point c’est vraiment un gros problème pour un serveur GQL basé sur une liste d’autorisation, où toutes les requêtes sont connues à l’avance. On peut mettre en cache ou mémoriser le résultat du parsing de l’AST, donc j’imagine que ce n’est un problème de performance que pendant les quelques minutes qui suivent le démarrage du conteneur.
    Ou alors je me demande si cela a aussi un impact d’une autre manière.

• Dans n2[1], j’avais besoin d’un tokenizer rapide et j’ai rencontré le même problème de générateur de déchets. En gros, le problème venait du mélange entre un ensemble de tokens constants comme json.Delim et des chaînes qui provoquent des allocations.
  Une solution que je trouve assez bonne consiste à rendre le tokenizer générique sur un certain T, et à lui passer une fonction qui transforme une tranche d’octets en T, afin d’utiliser T au lieu d’une chaîne.
  Ainsi, si l’appelant dispose d’une représentation plus efficace, par exemple avec moins d’allocations, il peut la fournir ; en même temps, dans les tests unitaires, on peut facilement tester le tokenizer en utilisant la fonction identité.
  D’une certaine façon, cela ressemble à une fusion du tokenizer et du parseur au moment du build, mais grâce aux génériques, on peut préserver la séparation en couches sans que le tokenizer connaisse la représentation du parseur.
  [1] https://github.com/evmar/n2

• On peut améliorer les choses par rapport à la bibliothèque standard avec une meilleure conception d’API, mais il est en pratique difficile de construire un parseur entièrement streaming qui ne remplisse pas à moitié une structure avant de découvrir une erreur et de sortir au milieu. La bibliothèque standard semble avoir fait de cela une contrainte de conception explicite.

• J’ai peut-être raté quelque chose, mais l’auteur répète qu’il a créé un parseur « streaming » sans expliquer ce que cela signifie réellement.
  En particulier, il n’explique pas comment il gère les clés répétées dans une « table de hachage ». Je me demande si, lorsqu’une clé répétée apparaît, le code sink est appelé deux fois, ou s’il attend d’avoir lu toute la « table de hachage » avant d’appeler le code sink.
  À mon avis, JSON est hiérarchique, sa longueur n’est pas connue à l’avance, et surtout il permet les clés répétées, ce qui le rend intrinsèquement peu adapté au streaming.
  On peut rendre certains sous-ensembles de JSON plus favorables au streaming, mais dans ce cas, pourquoi s’embêter à corriger JSON ? Si la solution consiste à modifier JSON, je pense qu’un autre format que JSON serait tout simplement meilleur.

• Content de voir Phil Pearl mentionné.
  https://github.com/bytedance/sonic vaut aussi le coup d’œil.

• Je suis surpris qu’il n’existe pas de moyen de dire « vraiment, inline cette fonction » pour une fonction trop grosse pour être inlinée.
  Les opérations de base de comptage et de recherche des caractères d’espacement semblent pouvoir devenir beaucoup plus rapides si elles sont vectorisées avec SIMD, mais je comprends que ce soit hors du périmètre de l’auteur.

  • Bien sûr qu’on peut forcer l’inlining.

• Dire qu’« il est irréaliste de s’attendre à pouvoir garder toute l’entrée en mémoire » est faux pour la plupart des applications.

  • La plupart des applications lisent du JSON depuis le réseau, et c’est un flux. Même si le JSON est relativement petit, bufferiser toute la requête en mémoire et la manipuler augmente fortement la latence.
  • C’est vrai, mais pour les applications qui doivent faire des transformations de type ETL sur de gros jeux de données, le streaming est une stratégie extrêmement utile.
    On pourrait dire que Go n’est pas le bon outil pour ce travail, mais avec ce genre d’optimisations, je ne vois pas pourquoi ce serait impossible.
  • Si l’on crée une bibliothèque, il faut soit expliciter ses limites, soit prendre en charge le streaming.
    Ayant déjà dû injecter des données JSON de l’ordre du gigaoctet, j’apprécie les parseurs streaming. Et le fait de prendre en charge le streaming signale aussi que l’auteur connaît plusieurs cas d’usage et fait un meilleur travail d’ingénierie.
    La mémoire n’est bon marché et presque gratuite qu’en théorie ; dans la réalité, ce n’est pas le cas.
  • Si l’on peut se satisfaire du fait que « ça tient sur disque », mmap() n’est-il pas aussi une option possible ? Les cas où l’on a vraiment besoin de streaming, par exemple lorsqu’il faut traiter tôt les données du début d’un même fichier JSON comme un flux de transactions ou de tâches, sont à part.
  • Le corps d’une requête HTTP est-il aussi considéré comme faisant partie de l’entrée ?