jsongrep, plus rapide que jq

• Outil CLI Rust pour parcourir des documents JSON par chemin, avec une vitesse de recherche supérieure à celle de jq, jmespath, jsonpath-rust et jql
• Les requêtes sont exprimées comme un langage régulier et compilées en DFA, puis l’arbre JSON est parcouru en un seul passage, pour un traitement en temps O(n)
• S’appuie sur serde_json_borrow, qui prend en charge le parsing zero-copy, afin de minimiser les allocations mémoire, et a été conçu en s’inspirant de la philosophie de performance de ripgrep
• Selon les benchmarks, il offre les meilleures performances end-to-end, y compris sur de gros JSON, avec un langage de requête simple centré sur la recherche
• Publié sous licence MIT, avec un moteur de requête basé sur DFA réutilisable comme bibliothèque Rust

---

Présentation de jsongrep

• jsongrep est un outil CLI en Rust qui recherche des valeurs dans des documents JSON à partir de chemins, avec l’objectif d’être plus rapide que jq, jmespath, jsonpath-rust et jql
• Il considère un document JSON comme un arbre, exprime les chemins (path) comme un langage régulier (regular language), les compile en DFA (Deterministic Finite Automaton), puis effectue l’exploration en un seul passage
• Le langage de requête est simple, conçu autour de la recherche, sans fonctions de transformation ni de calcul
• Le parsing zero-copy via serde_json_borrow minimise les allocations mémoire
• Son développement s’inspire de la philosophie de conception et de l’approche performance de ripgrep

Exemples d’utilisation de jsongrep

• La commande jg prend une requête et une entrée JSON, puis affiche toutes les valeurs dont le chemin correspond à la requête
• Accès aux champs imbriqués avec la notation par points (dot path)
  • jg 'roommates[0].name' → "Alice"
• Les wildcards (*, [*]) permettent de faire correspondre toutes les clés ou tous les index
• L’alternation (|) permet de choisir l’un de plusieurs chemins
• La recherche récursive ((* | [*])*) permet de trouver des champs à profondeur arbitraire
• L’optional (?) permet une correspondance en 0 ou 1 occurrence
• L’option -F permet de rechercher rapidement un nom de champ spécifique
• Lors de l’utilisation de pipes (| less, | sort), l’affichage du chemin est automatiquement omis ; on peut forcer son affichage avec --with-path

Concepts clés de jsongrep

• Un JSON est une structure arborescente, où les clés d’objet et les index de tableau jouent le rôle d’arêtes (edges)
• Une requête définit un ensemble de chemins entre la racine et certains nœuds
• Le langage de requête est conçu comme un langage régulier, ce qui permet sa conversion en DFA
• Le DFA ne lit l’entrée qu’une seule fois et explore en temps O(n), sans backtracking
• Les outils existants (jq, jmespath, etc.) interprètent les requêtes et explorent récursivement, tandis que jsongrep s’appuie sur un DFA précompilé pour une exploration en un seul passage

Architecture du moteur de requête basé sur DFA

• Le pipeline se compose de 5 étapes
  1. Parsing du JSON en arbre avec serde_json_borrow
  2. Parsing de la requête en AST
  3. Construction d’un NFA avec l’algorithme de Glushkov
  4. Conversion en DFA par Subset Construction
  5. Exploration de l’arbre JSON en un seul DFS en suivant les transitions du DFA

• Parsing des requêtes

  • Une grammaire PEG (avec la bibliothèque pest) convertit la requête en AST Query
  • Principaux éléments syntaxiques : Field, Index, Range, FieldWildcard, ArrayWildcard, Optional, KleeneStar, Disjunction, Sequence
  • Exemple : roommates[*].name → Sequence(Field("roommates"), ArrayWildcard, Field("name"))

• Modèle d’arbre JSON

  • Les clés d’objet et les index de tableau sont des arêtes, les valeurs sont des nœuds
  • Exemple : roommates[*].name parcourt le chemin roommates → [0] → name

• Construction du NFA (algorithme de Glushkov)

  • Génère un NFA sans transition ε
  • Étapes
    1. Attribution d’un numéro de position aux symboles de la requête
    2. Calcul des ensembles First/Last/Follows
    3. Construction des transitions entre positions
  • Pour la requête roommates[*].name, le NFA obtenu est une structure linéaire simple de 4 états

• Conversion en DFA (Subset Construction)

  • Génère un DFA déterministe à partir d’ensembles d’états du NFA
  • Chaque état correspond à un ensemble d’états du NFA
  • Ajoute un symbole Other pour ignorer efficacement les clés non pertinentes
  • Pour les requêtes simples, on obtient un DFA de structure identique à celle du NFA

• Exploration basée sur DFS

  • En partant de la racine, les transitions du DFA sont suivies le long de chaque arête
  • S’il n’y a pas de transition, le sous-arbre correspondant est élagué (prune)
  • Quand l’état du DFA est accepting, le chemin et la valeur sont enregistrés
  • Chaque nœud est visité au plus une fois, donc l’exploration complète reste en O(n)
  • serde_json_borrow permet de référencer le buffer d’origine sans recopier les chaînes

Méthodologie des benchmarks

• Benchmarks statistiques réalisés avec Criterion.rs

• Jeux de données

  • simple.json (106B), kubernetes-definitions.json (~992KB), kestra-0.19.0.json (~7.6MB), citylots.json (~190MB)

• Outils comparés

  • jsongrep, jsonpath-rust, jmespath, jaq, jql

• Groupes de benchmarks

  1. document_parse : vitesse de parsing JSON
  2. query_compile : temps de compilation des requêtes
  3. query_search : recherche seule
  4. end_to_end : pipeline complet

• Considérations d’équité

  • L’avantage du parsing zero-copy est mesuré séparément
  • Le coût de compilation du DFA est mesuré à part
  • Les outils sans fonctionnalité correspondante sont exclus des tests concernés
  • Le coût de duplication des données est traité séparément

Résultats des benchmarks

• Temps de parsing du document : serde_json_borrow est le plus rapide
• Temps de compilation des requêtes : jsongrep a le coût le plus élevé en raison de la génération du DFA ; jmespath est bien plus rapide
• Temps de recherche : jsongrep est le plus rapide de tous les outils comparés
• Performances end-to-end : même sur le jeu de données de 190MB, il est nettement plus rapide que jq, jmespath, jsonpath-rust et jql
• Tous les résultats sont disponibles sur le site de benchmark en direct

Licence et usages

• Logiciel open source sous licence MIT
• Disponible sur GitHub, Crates.io et Docs.rs
• Le moteur de requête basé sur DFA est réutilisable sous forme de bibliothèque, directement intégrable dans des projets Rust

Références

• Glushkov, V. M. (1961), The Abstract Theory of Automata
• Rabin, M. O., & Scott, D. (1959), Finite Automata and Their Decision Problems

[roxie]

C’est sympa.

[lamanus]

| Pourquoi le caractère pipe s’affiche-t-il différemment dans le corps du texte ? C’est curieux..

[GN⁺]

Commentaires sur Hacker News

• La syntaxe de jq est trop obscure, au point que je dois faire une recherche chaque fois que je veux simplement récupérer une valeur JSON

  • Intéressant. Moi, je trouve la syntaxe de jq intuitive, et j’ai l’habitude d’utiliser seulement des points, des pipes et des crochets, comme dans un pipeline shell
    J’écris surtout des filtres à usage unique, donc je passe plus de temps à les écrire qu’à les relire
    Mon cas d’usage est sans doute simple, ou alors jq correspond bien à ma façon de penser
    Je rêve d’un monde où tous les outils CLI lisent et produisent du JSON et s’enchaînent avec jq, mais ça ressemblerait sans doute à un cauchemar pour vous
  • Je n’utilise pas jq assez souvent, donc c’est un outil qui reste dans la « vallée de l’apprentissage »
    À chaque fois que je m’en sers, j’ai l’impression de devoir le réapprendre, donc ça ne me paraît pas intuitif
    Même si sed est Turing-complet, la plupart des gens s’en servent seulement pour des substitutions par regex
  • Je recommande celq, que j’ai créé
    J’aime jq, mais il m’est déjà arrivé de ne plus comprendre des requêtes que j’avais écrites moi-même
    celq utilise le langage CEL, plus familier
  • Pour des raisons similaires, j’ai aussi créé moi-même un outil appelé dq
    Il permet simplement de manipuler du JSON en JavaScript, et il est étonnamment plus rapide que jq
    Je l’utilise par exemple comme ça : $ cat package.json | dq 'Object.keys(data).slice(0, 5)'
  • Le JSON lui-même contient beaucoup de bruit syntaxique inutile, ce qui est pénible
    Depuis que j’ai appris Clojure, j’utilise désormais EDN à la place du JSON
    C’est plus concis, plus lisible et plus facile à manipuler structurellement
    En ce moment, j’utilise borkdude/jet ou babashka pour manipuler les données, et djblue/portal pour les visualiser
    Je ne comprends pas pourquoi jq s’obstine avec des opérateurs aussi complexes

• J’accorde de l’importance aux performances, mais les comparaisons à la nanoseconde me donnent l’impression d’une performance de démonstration
  Dans la plupart des cas, l’outil qu’on utilise déjà suffit largement
  Par exemple, je n’utilise rg à la place de grep que sur de gros fichiers

  • Si vous pensez ça, dites-vous simplement : « je ne suis pas l’utilisateur cible »
    La différence entre 2 ms et 0,2 ms peut sembler négligeable, mais elle compte pour ceux qui traitent des flux de données à l’échelle du téraoctet
  • Mais si tout le monde raisonne ainsi, de petites inefficacités s’accumulent et finissent par ralentir l’ensemble
    Le matériel est devenu plus rapide, mais les logiciels sont en réalité devenus plus lents
  • Pour que jq se distingue, il lui faudrait une syntaxe intuitive et davantage d’exemples concrets
  • L’expression « suffisamment rapide » me gêne toujours
    Refuser l’optimisation donne l’impression de paresse et de manque d’imagination
    Se rassurer en disant que c’est plus rapide que la latence réseau ressemble à une excuse
  • Moi aussi, j’accorde plus d’importance à l’ergonomie et aux fonctionnalités qu’à la vitesse
    Si le JSON est vraiment trop volumineux, il vaut mieux utiliser un format binaire
    Et s’il faut construire des pipelines complexes en CLI, je pense qu’il vaut mieux écrire directement un programme

• Beaucoup de nouveaux outils CLI mettent en avant le fait d’être « plus rapides », mais en pratique j’ai rarement eu l’impression que jq était lent

  • Je manipule des fichiers ndjson de plusieurs téraoctets
    Même pour une opération simple comme renommer un champ avec jq, c’est bien trop lent, donc je le traite moi-même avec des scripts Node ou Rust
  • Quand on travaille sur des fichiers de logs gigantesques, jq peut effectivement sembler lent
    Dans des environnements d’hyperscalers, on télécharge et analyse directement plusieurs To de logs
  • Nous analysons des réponses JSON provenant de milliers de nœuds
    Selon la résolution de monitoring, la différence de performance peut devenir perceptible
  • À chaque nouvel outil, on retrouve le même schéma : « une version plus rapide réécrite en Rust »
    Qui n’implémente qu’une partie des fonctionnalités et revendique la victoire sur la base de benchmarks
    Ce projet aussi semble s’inscrire dans cette tendance du « sous-ensemble plus rapide »
  • On ne se rend compte qu’un outil est lent qu’au moment où il commence réellement à ralentir
    À partir de là, tout paraît lent
    Comme avec ripgrep, une fois qu’on a goûté à un outil rapide, il est difficile de revenir en arrière

• J’ai utilisé à la fois jq et yq, mais yq est bien plus lent sans que cela m’ait jamais dérangé
  S’il existe un outil plus rapide que jq, tant mieux, mais cela ne concerne qu’un certain type d’utilisateurs
  Cela dit, en tant que personne qui aime l’optimisation, j’ai du respect pour cette démarche

  • Je me demande de quel yq il s’agit — la version Go ou la version Python ?
  • Dans un environnement d’intégration serveur, les performances sont importantes, mais en CLI c’est généralement largement suffisant
  • Je traite avec jq des GeoJSON de plusieurs Go exportés depuis ArcGIS
    Cela prend pas mal de temps à l’étape ETL
  • Tout le monde n’utilise pas les outils de la même manière

• À la première ouverture de la page, il y avait un problème de couleurs en mode clair
  En passant en mode sombre puis en revenant, le problème se corrigeait

  • Le site donne aussi l’impression d’avoir été codé à l’instinct comme l’outil
  • C’est moi l’auteur ; comme je n’utilise pas le mode clair, j’ai oublié de le tester, je vais corriger ça tout de suite
  • C’était un problème de styles du mode sombre qui débordaient dans le CSS
  • Sur Firefox Android, ça allait, mais l’échelle des graphiques variait d’un cas à l’autre, ce qui rendait la comparaison difficile
  • C’est corrigé maintenant

• Je suis passé à Jaq pour des raisons de justesse
  On dit aussi que ses performances sont meilleures que celles de jq

  • Merci pour la recommandation. jaq semble avoir évolué dans une direction plus pertinente que jsongrep
  • En revanche, jaq 3.0 est plus rapide que le jq fourni par les distributions, mais un jq compilé manuellement est plus rapide
    La réputation de lenteur de jq semble venir d’un problème de packaging des distributions

• Dans mon travail, je manipule souvent du JSON délimité par des retours à la ligne (jsonl)
  Chaque ligne est un objet JSON complet, et je me demande si les principaux outils CLI prennent en charge ce format

• J’ai utilisé divers outils CLI de traitement de données comme jq, mlr, htmlq, xsv, yq, etc.,
  mais depuis que j’ai découvert Nushell, ils ont tous été remplacés
  Le fait de pouvoir traiter tous les formats avec une seule syntaxe a été une expérience rafraîchissante

  • Moi aussi, j’utilise Nushell comme shell principal depuis mi-2023
    Je continue à utiliser jq, yq et mlr seulement quand je collabore avec des collègues
  • Moi aussi, Nushell a remplacé la plupart de mes outils
    J’ai quelques petites frustrations avec la configuration de l’autocomplétion et la découvrabilité des commandes, mais c’est bien meilleur que oh-my-zsh
    S’il impose les annotations de type, permet de compiler des binaires statiques et se dote d’une bibliothèque TUI, je l’utiliserais même pour écrire de petites applications
  • Je suis d’accord. Grâce à sa syntaxe intuitive et cohérente, Nushell rend l’automatisation bien plus simple

• Super outil ! En revanche, la visualisation des benchmarks laisse un peu à désirer
  Tous les outils ont la même couleur, donc il est difficile de repérer jsongrep
  jq lui-même n’apparaissait pas dans le graphique, ce qui prêtait à confusion
  Un fichier xLarge à 190 MiB reste assez petit ; moi, je manipule souvent des JSON de 400 MiB à 1 GiB

  • L’auteur répond : pour l’instant, la plage couverte par les benchmarks va de 106 B à 190 MB
    S’il existe des documents JSON publics plus volumineux, n’hésitez pas à me les signaler

• La visualisation des benchmarks paraît assez brute
  Il serait bien d’exprimer davantage de dimensions avec les couleurs ou les formes
  Le fait de devoir lire directement les chemins de fichiers pour comprendre les résultats n’est pas très pratique