Le traitement des chaînes dans serde_json accéléré de 20 %

 (purplesyringa.moe)
2 points par GN⁺ 2024-08-25 | 1 commentaires | Partager sur WhatsApp
  • serde_json, utilisé comme le parseur JSON de référence dans l’écosystème Rust, a gagné 10 %, 23 % et 32 % de performances dans des benchmarks riches en chaînes grâce à de petites optimisations internes
  • Le calcul de la position des erreurs ne parcourt plus directement le début de la chaîne : il utilise désormais memchr pour trouver le nombre de lignes et le dernier retour à la ligne, réduisant l’écart d’un chemin d’erreur qui était plus de deux fois plus lent que le chemin de succès
  • La boucle centrale de parsing des chaînes n’identifie plus séparément \, " et les caractères de contrôle : elle les vérifie en une fois avec SWAR, ce qui offre une faible latence sur les chaînes courtes sans véritable SIMD
  • Le décodage des escapes \u réduit les coûts de branchement et de shift grâce à une LUT, des entiers signés et une table de décalage préalable ; le parsing du JSON de War and Peace en russe passe de 284 MB/s à 344 MB/s
  • L’encodage UTF-8, devenu ensuite le goulot d’étranglement, est traité par une génération UTF-8 manuelle évitant les coûts d’initialisation et de copie de char::encode_utf8 et Vec::extend_from_slice, portant le même benchmark à 374 MB/s

Pourquoi l’optimisation de serde_json produit un effet important

  • serde est le principal framework de sérialisation et de désérialisation de Rust, et serde_json est largement utilisé comme combinaison officielle pour traiter JSON
  • Au moment de la publication, serde_json comptait 26 916 dépendances inverses, contre 66 pour simd-json
  • Avec un tel niveau d’utilisation, même de petites améliorations internes de serde_json peuvent avoir un effet cumulé dans tout l’écosystème Rust
  • Dans un contexte où beaucoup d’utilisateurs ne changent pas facilement de parseur JSON, des optimisations à faible risque dans la bibliothèque existante sont pratiques

Calcul de la position des erreurs : d’une boucle simple à memchr

  • Dans le benchmark du chemin d’erreur, serde_json était plus de deux fois plus lent que le chemin de succès sur les mêmes données
    • Sur les jeux de données canada, citm_catalog et twitter, le chemin d’erreur était 48 % à 77 % plus lent que le chemin de succès
  • Le goulot d’étranglement était la fonction position_of_index(), qui convertit un index en line/column pour formater le message d’erreur
    • L’ancienne implémentation parcourait self.slice[..i] octet par octet et mettait à jour line et column à chaque \n
  • En divisant le calcul en deux étapes, on peut appliquer memchr
    • Compter le nombre de \n dans self.slice[..i] pour obtenir le numéro de ligne en base 0
    • Trouver la position du dernier \n et la soustraire de i pour obtenir le numéro de colonne
  • memchr fournit une implémentation optimisée pour rechercher un seul caractère et compter ses occurrences, en utilisant SIMD en interne
  • Après la fusion de la PR #1160, les performances du chemin d’erreur se sont nettement améliorées
    • Sur canada en DOM, le chemin d’erreur est passé de 122 MB/s à 216 MB/s
    • Sur citm_catalog en struct, il est passé de 195 MB/s à 736 MB/s
    • Le chemin d’erreur restait plus lent que le chemin de succès, mais l’écart s’est réduit

Recherche des escapes dans les chaînes : trouver trois conditions en une seule fois

  • L’ancienne boucle centrale du parsing des chaînes parcourait les octets non échappés à l’aide d’une table ESCAPE
    • Dans une chaîne JSON, les éléments à traiter comme escapes sont \, " et les caractères de contrôle ASCII inférieurs ou égaux à 0x1F
    • Selon la spécification JSON, les codes de contrôle ne sont pas autorisés dans les chaînes
  • La première tentative utilisait memchr2 pour trouver d’abord \ ou ", puis vérifiait séparément les caractères de contrôle
    • Cela revenait à parcourir la chaîne deux fois, une fois rapidement et une fois lentement, ce qui était plus lent que l’existant
    • Vectoriser seulement une moitié simple et laisser le reste en scalaire ne débouchait pas sur une amélioration globale
  • La deuxième tentative combinait memchr2 avec du SIMD manuel pour vérifier l’absence de caractères de contrôle
    • Sur les chaînes courtes, le coût de l’appel de fonction avec sélection à l’exécution devenait significatif
    • Sur les chaînes longues, le problème de lire la mémoire deux fois subsistait
  • L’implémentation finale a été organisée pour trouver \, " et les caractères de contrôle en un seul passage

Implémenter un traitement proche du SIMD avec SWAR

  • Pour éviter d’ajouter du code SIMD propre à chaque plateforme, la technique SWAR (SIMD Within A Register) a été utilisée
    • Au lieu de SIMD 128 bits, un mot de 64 bits est traité comme 8 octets
    • Des opérations bit à bit vérifient simultanément si chaque octet satisfait la condition
  • Le test des caractères de contrôle transforme la condition c >= 0 && c < 0x20 en opérations bit à bit
    • Sur des blocs de 8 octets, cela se vérifie avec un masque de la forme !c & (c - 0x2020202020202020) & 0x8080808080808080
    • L’emprunt d’une soustraction 64 bits peut se propager à l’octet supérieur, mais cela ne pose pas de problème quand l’objectif est de trouver le caractère de contrôle le plus bas
  • \ et " sont vérifiés de façon similaire et combinés en une seule expression
    • L’expression complète se compose de 9 opérations bit à bit
    • En SIMD x86, 7 opérations seraient nécessaires, donc le débit est inférieur, mais la latence compte davantage pour les chaînes courtes
  • Dans json-benchmark, ce code SWAR s’est révélé plus efficace que du vrai code SIMD
  • Sur les chaînes très courtes, SWAR peut être plus lent que le code scalaire
    • Une régression apparaît autour des chaînes d’environ 5 caractères
    • Pour protéger des motifs fréquents comme la chaîne vide "" et les escapes consécutifs \r\n, \uD801\uDC37, le premier caractère est vérifié avant d’entrer dans la boucle SWAR
  • Les résultats de l’optimisation de la recherche dans les chaînes varient selon les jeux de données
    • twitter struct passe de 638 MB/s à 785 MB/s, soit +23 %
    • twitter DOM passe de 305 MB/s à 335 MB/s, soit +10 %
    • citm_catalog struct passe de 865 MB/s à 905 MB/s, soit +5 %
    • Les chaînes vides restent jusqu’à 2 % plus lentes dans certains microbenchmarks

Optimisation du décodage des escapes Unicode

  • serde_json traite à la fois les chaînes Unicode brutes et les escapes \u
    • Par exemple : "🥺" et "\ud83e\udd7a"
  • L’ancien décodage hexadécimal utilisait une LUT de 256 entrées pour associer chaque caractère à une valeur de 0 à 15
    • Il gérait '0'..='9', 'A'..='F' et 'a'..='f'
    • Les caractères invalides étaient marqués par une valeur sentinelle
  • Un escape \u lit 4 chiffres hexadécimaux ; l’ancienne méthode effectuait donc à chaque itération shift, addition, comparaison et branchement conditionnel
  • La nouvelle implémentation ne renvoie pas d’erreur à chaque itération : elle traite les 4 caractères, puis vérifie leur validité
  • L’implémentation finale utilise une LUT [i8; 256] où les chiffres invalides valent -1, et calcule avec un entier 32 bits
    • En cas de succès, le résultat n’est pas négatif ; en cas d’échec, il l’est
    • Sur x86, le chargement mémoire et l’extension de signe peuvent être combinés en movsx
  • Deux tables sont utilisées pour réduire la latence des shifts
    • HEX0 : la valeur originale
    • HEX1 : une table où la valeur est déjà décalée de 4 bits vers la gauche
  • Le tout est structuré en une implémentation decode_four_hex_digits() avec un unroll explicite de la boucle
  • Grâce à cette optimisation, les performances de parsing de War and Peace en russe sous forme JSON-encoded passent de 284 MB/s à 344 MB/s, soit +21 %

Goulot d’étranglement de l’encodage UTF-8 et génération manuelle

  • Après le décodage des escapes Unicode, le goulot d’étranglement s’est déplacé vers l’encodage UTF-8
  • UTF-8 encode les codepoints sur 1 à 4 octets selon leur longueur
    • 1 octet : 0xxxxxxx
    • 2 octets : 110xxxxx 10xxxxxx
    • 3 octets : 1110xxxx 10xxxxxx 10xxxxxx
    • 4 octets : 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
  • char::encode_utf8, dans la bibliothèque standard Rust, écrit dans un buffer &mut [u8], qui doit donc déjà contenir des valeurs u8 valides
    • Il ne peut pas écrire directement dans un buffer non initialisé
    • Comme UTF-8 est un encodage de longueur variable, LLVM a du mal à supprimer la zeroization inutile
  • serde_json utilisait une approche du type scratch.extend_from_slice(c.encode_utf8(&mut [0u8; 4]).as_bytes())
    • En théorie, l’utilisation d’un buffer local [0u8; 4] pourrait aider l’analyse d’alias
    • En pratique, à cause de la copie de longueur variable de 1 à 4 octets, LLVM génère un appel à memcpy
  • Pour éviter les appels à memset et memcpy, UTF-8 est généré directement
    • L’algorithme lui-même est simple, mais nécessite unsafe
    • Avec quelques petits changements supplémentaires, le benchmark War and Peace s’améliore encore de 344 MB/s à 374 MB/s, soit +9 %

Résultat final

  • Dans les benchmarks JSON riches en chaînes, les performances de serde_json progressent respectivement de 10 %, 23 % et 32 %
  • Comme beaucoup de données JSON contiennent de nombreuses chaînes, cette optimisation peut avoir un impact sur une large part du code Rust utilisant serde_json
  • Les améliorations ont été obtenues en éliminant successivement différents goulots d’étranglement : calcul de la position des erreurs, recherche d’escapes dans les chaînes, décodage des escapes Unicode et encodage UTF-8

À lire aussi

1 commentaires

 
GN⁺ 2024-08-25
Avis sur Hacker News

  • Les astuces UTF-8 me mettent assez mal à l’aise, tant j’ai vu d’attaques jouant sur la confusion des parseurs
    J’utilise plutôt serde pour son exactitude que pour sa vitesse, donc j’espère qu’ils ont fuzzé ça jusqu’au bout avec plein de chaînes UTF-8 invalides

    • Heureusement, la structure d’UTF-8 est très simple par rapport à celle d’un parseur moyen
      Ça ne veut pas dire qu’il n’y a pas de bugs, mais l’état interne du parseur devrait rester limité, et des tests exhaustifs semblent possibles
    • C’est précisément le genre de domaine où j’aimerais voir les résultats d’un fuzzer
    • Tu aurais un exemple qui te vient immédiatement en tête pour ce type de bug ?

  • C’est sympa de voir serde évoluer aussi vite
    Je regardais justement simdutf8 et j’ai découvert que la PR pour le parsing UTF-8 avec prise en charge SIMD traîne depuis presque 5 ans
    https://github.com/rust-lang/rust/issues/68455

  • J’ai pris plaisir à lire ce blog, il dégage une forte impression de jart
    Le passage « il va falloir réinventer la roue, mais quand on y pense c’est plutôt chouette » : je ne sais pas si c’est sincère ou ironique
    En le lisant, j’ai commencé à rire en me moquant de l’auteur, mais le reste de la page semble assez chargé en autodérision

    • Je pense que cette phrase veut dire que ce n’est pas le fait de devoir réinventer la roue qui est chouette, mais l’approche
    • Ça veut dire quoi, jart ?

  • « Enseigner comment penser est aussi important qu’enseigner à coder, mais cela se fait rarement »
    J’y sens l’arrogance de quelqu’un qui considère que les autres ne pensent pas

    • Je ne vois pas d’arrogance dans cette phrase
      Elle ne suppose pas que les autres ne pensent pas ; c’est plutôt le constat que la plupart des articles de blog et des guides montrent seulement le résultat final, sans forcément montrer les étapes pour y arriver
    • Ce n’est pas ce que l’auteur affirme
      Enseigner comment penser signifie qu’il faut enquêter et qu’on ne peut pas sauter cette étape ; et le fait d’avoir enquêté ne vous décharge pas non plus de la responsabilité de tirer vos propres conclusions
      Il est facile de sauter l’une ou l’autre de ces deux étapes, mais c’est une mauvaise méthode

  • serde_json occupe 3 Go de dépendances si l’on fait une build debug et une build release
    Utilisez serde dans quelques projets actifs et vous n’aurez plus d’espace disque
    Je ne vois pas pourquoi parser du JSON nécessite 3 Go de dépendances ; je suis pour la réutilisation de code, mais les dépendances côté JSON de serde ont l’air assez brouillonnes
    Qu’un exploit apparaisse dans l’une de ces dépendances et la moitié de l’écosystème Rust devient vulnérable
    Rust devrait intégrer JSON en natif

    • Il n’y a que 5 dépendances, dont une optionnelle et une autre qui est serde lui-même : https://github.com/serde-rs/json/blob/master/Cargo.toml
      indexmap = { version = "2.2.3", optional = true }
      itoa = "1.0"
      memchr = { version = "2", default-features = false }
      ryu = "1.0"
      serde = { version = "1.0.194", default-features = false }
      Quand tu parles de 3 Go de dépendances, il est très probable que ce ne soit pas ce que tu as réellement mesuré
      Je ne peux pas en être sûr, puisque tu l’énonces comme un fait sans preuve, mais je suppose que tu utilises beaucoup #[derive(Serialize, Deserialize)], ce qui génère une grosse quantité de code, puis que tu mesures la taille totale du répertoire target
      Une build simple donne, comme l’ont montré d’autres commentaires, quelque chose de l’ordre de quelques dizaines de Mo
    • Je ne pense pas qu’intégrer JSON à Rust soit une approche raisonnable
      Ce ne serait qu’une manière d’introduire de la bloat, et la bibliothèque standard n’a pas d’avantage particulier par rapport aux autres crates, hormis ses garanties de stabilité
      Au final, cela ne ferait que lier le cycle de publication de la bibliothèque à celui du compilateur
      En pratique, rustc-serialize était autrefois presque intégré, et Rust a déjà essayé cette voie
      Et serde_json, dans sa configuration par défaut, n’est pas gros
      Ni serde_json ni serde ne sont gros, et tous deux maintiennent une MSRV très basse, que les autres crates prennent rarement bien en charge, ce qui les empêche de toute façon d’avoir beaucoup de dépendances
    • La bloat des dépendances est un problème général de Rust
      L’arbre de dépendances d’un projet Rust d’une certaine taille devient vite assez effrayant, auditer toutes ces dépendances est irréaliste, et le niveau de confiance dans beaucoup d’entre elles est faible
      Après avoir travaillé avec Rust pendant quelques années, je ne pense pas y revenir avant que l’écosystème soit beaucoup plus mature
      Cette maturité viendra avec une adoption massive par les grandes entreprises ; sinon, je ne l’utiliserais que pour des projets no-std, no-deps, destinés à remplacer du C pur
      Cela dit, une fois Zig stabilisé, il pourrait aussi déloger Rust pour cet usage
    • Rust génère une quantité anormale d’informations de debug
      C’est tellement grotesquement volumineux que je suppose que c’est tout simplement un bug
      Quoi que vous compiliez, le dossier target accumule des gigaoctets, mais ce n’est pas représentatif de l’artefact final une fois les informations de debug supprimées, ou au moins avec des réglages moins détaillés
    • Sur un projet d’une certaine taille, j’ai l’impression que le dossier target fait littéralement toujours au moins quelques Go