Note : Cet article est une version mise à jour d'un article précédent sur le même sujet. La version originale de cet article a été écrite pour présenter quelques-uns des points principaux de la création d'un parseur haute performance, mais des critiques de lecteurs exprimaient le fait que certaines parties étaient incomplètes. L'article original a été complètement révisé avec une version plus complète du code. Nous espérons que vous apprécierez cette révision.
De temps en temps, il se peut que vous ayez besoin de mettre en œuvre votre propre parseur de données ou de langage en Java, par exemple s'il n'y a pas de standard Java ou de parseur open source pour ce format de données ou langage. Ou peut-être existe-t-il des parseurs, mais ils sont trop lents et consomment trop de mémoire, ou tout simplement ils n'ont pas les fonctionnalités dont vous avez besoin. Ou encore pourrait-il y avoir des bugs dans un parseur open source, ou le projet de parseur open source a été abandonné, etc. La raison n'est pas aussi importante que le fait bien réel que vous pourriez avoir besoin de mettre en œuvre votre propre parseur.
Lorsque vous devez développer votre propre parseur, vous voulez qu'il fonctionne bien, qu'il soit facilement modifiable, riche en fonctionnalités, facile à utiliser, et dernier point, mais non des moindres, facile à mettre en œuvre. Après tout, votre nom est dans code. Dans cet article, je vais vous expliquer une façon de mettre en œuvre des parseurs à haute performance en Java. Cette méthode n'est pas exclusive, mais elle est assez simple et permet d'obtenir des performances élevées et une conception modulaire raisonnable. Le design est inspiré par la conception de VTD-XML, le parseur XML en Java le plus rapide que j'ai vu, encore plus rapide même que les parseurs XML standard StAX et SAX Java.
Deux types de parseurs de base
Il y a plusieurs façons de classer les parseurs. Ici, je vais juste faire la distinction entre deux types de parseurs de base :
- Les parseurs à accès séquentiel
- Les parseurs à accès aléatoire (random)
Par accès séquentiel, je veux dire que le parseur analyse les données, retournant les données analysées au processeur de données une fois celles-ci analysées. Le processeur de données a seulement accès aux données analysées en cours, il ne peut pas regarder "en arrière" pour les données antérieures, et ne peut pas regarder vers l'avant. Ces parseurs sont également connus comme des parseurs "à évènements" et les parseurs SAX et StAX en sont les exemples les plus connus.
Un parseur à accès aléatoire est un parseur capable de déplacer son traitement de données d'avant en arrière (accès aléatoire) dans les données analysées. Des exemples de tels parseurs sont les parseurs XML et de DOM.
Les parseurs à accès séquentiel ne permettent d'accéder qu'à la "fenêtre" ou "évènement" qui vient d'être analysé, dans l'ordre du document, alors que l'accès aléatoire permet aux parseurs de naviguer dans les données analysées comme vous le souhaitez.
Aperçu de la conception (design)
J'explique ici la conception d'un parseur à accès aléatoire.
Les parseurs à accès aléatoire sont souvent plus lents que les parseurs à accès séquentiel, car ils constituent généralement une sorte d'arborescence d'objets à partir des données analysées, à travers laquelle le code de traitement peut accéder à ces données. La création de cette arborescence d'objets est en fait à la fois lente en temps CPU et peut consommer un peu de mémoire.
Au lieu de construire une arborescence d'objets à partir des données analysées, une approche plus performante consiste à construire un tampon d'index (indices buffer) dans la mémoire tampon des données d'origine. Les index indiquent les points de début et de fin des éléments présents dans les données analysées. Au lieu d'accéder à ces données par l'intermédiaire d'une arborescence d'objets, le traitement de données accède aux données analysées directement dans le tampon contenant les données d'origine. Voici une illustration de ces deux approches:
Faute d'un meilleur nom, j'appelle ceci un "Parseur à Superposition d'Index" (Index Overlay Parser). L'analyseur syntaxique crée une superposition d'index au-dessus des données d'origine. Ce n'est pas sans rappeler la façon dont on indexe les données de bases de données stockées sur disque. Il crée des index des données brutes d'origine pour naviguer et rechercher dans les données plus rapidement.
Comme je l'ai mentionné plus tôt, cette conception est inspirée par VTD-XML (VTD pour Virtual Token Descriptor) Ainsi, vous pouvez également appeler cela un "Virtual Token Descriptor Parser". Je préfère le nom "Index Overlay", parce que c'est ce que les Virtual Token Descriptors représentent - un index sur les données d'origine.
Conception d'un parseur
Une conception classique pour les parseurs est de séparer l'analyse en deux étapes. La première étape sépare les données en jetons (tokens) cohérents, où un jeton est une occurrence de plusieurs octets ou caractères dans les données analysées. La deuxième étape interprète les jetons et construit des éléments plus importants sur la base de ces jetons. Ces deux étapes sont illustrées ici :
Par éléments, je ne veux pas dire uniquement des éléments XML (même si les éléments XML sont également des éléments du parseur), mais plutôt des grands "éléments de données" comprenant les données analysées. Dans un document XML, ce serait des éléments XML. Dans un document JSON, ce serait des objets JSON, etc.
A titre d'exemple, la chaîne ci-dessous pourrait-être découpée en jetons de cette manière :
· <
· myelement
· >
Une fois les données découpées en jetons, il est plus facile pour le parseur de leur donner un sens et donc de déterminer les éléments plus grands que ces jetons composent. Le parseur saura alors qu'un élément XML commence par un jeton (token) < suivi par un jeton de chaîne (string) (le nom de l'élément), puis éventuellement un ensemble d'attributs, et enfin un jeton >.
Fonctionnement de l'analyse en mode "Index Overlay" (superposition d'index)
C'est une approche en deux étapes que nous allons utiliser dans notre conception d'un parseur. Les données d'entrée sont d'abord divisées en jetons (tokens) par un "tokenizer". Le parseur analyse ensuite ces jetons pour déterminer les limites plus grandes de l'élément dans les données d'entrée.
Vous pouvez également ajouter une troisième "étape de navigation dans les éléments" optionnelle au processus d'analyse. Si le parseur construit une arborescence d'objets à partir des données analysées, l'arborescence d'objets contient généralement des liens pour naviguer dans l'arbre. Lorsque nous construisons un tampon d'index de l'élément au lieu d'une arborescence d'objets, nous pouvons avoir besoin d'un composant séparé pour aider le code de traitement de données à naviguer dans le tampon d'index de l'élément.
Voici un aperçu de notre conception du parseur :
D'abord, nous lisons toutes les données dans une mémoire tampon. Afin de permettre un accès aléatoire aux données d'origine par l'intermédiaire de l'index créé pendant l'analyse (parsing), l'ensemble des données d'origine doit être disponible en mémoire.
Dans un deuxième temps, le "tokenizer" "casse" les données en jetons (tokens). L'index de départ, l'index de fin et le type des jetons sont conservés dans un tampon de jeton par le tokenizer. L'utilisation d'un tampon jeton permet de rechercher vers l'avant et vers l'arrière, quand le parseur en a besoin.
Troisièmement, le parseur examine les jetons obtenus à partir du "tokenizer", les valide dans leur contexte et détermine quels sont les éléments qu'ils représentent. L'analyseur construit ensuite l'index de l'élément ("index overlay"/la superposition d'index) sur la base des jetons reçus à partir du générateur de jetons. Le parseur obtient les jetons un par un à partir du tokenizer. Ainsi, le tokenizer n'a pas vraiment besoin de casser toutes les données en jetons immédiatement. Il a juste besoin de trouver un jeton à la fois.
Le code de traitement de données peut naviguer dans le tampon (buffer/mémoire tampon) d'éléments, et l'utiliser pour accéder aux données d'origine. En option, vous pouvez intégrer le tampon d'éléments dans un composant de navigation d'éléments, ce qui rend la navigation plus facile.
Cette conception ne construit pas une arborescence d'objets à partir des données analysées, mais il construit une structure navigable, la mémoire tampon d'éléments, constituée d'indices (tableaux d'entier (int)) dans le tampon de données contenant les données d'origine. L'utilisation de ces indices, permet de naviguer dans les données de la mémoire tampon d'origine.
La section suivante va expliquer les différentes parties de la conception en détail.
La mémoire tampon de données
La mémoire tampon de données est une mémoire tampon d'octets ou de caractères (bytes or char) contenant les données d'origine. La mémoire tampon de jetons (tokens) et la mémoire tampon d'éléments contiennent des indices de la mémoire tampon de données.
Afin de permettre un accès aléatoire aux données analysées, il est nécessaire d'avoir une sorte de représentation en mémoire de tout cela. Au lieu d'une arborescence d'objets, nous utilisons la mémoire tampon des données avec les données brutes.
Avoir toutes les données en mémoire peut consommer une grande partie de la mémoire. Si vos données contiennent des éléments qui sont indépendants les uns des autres, comme des enregistrements de logs, mettre l'intégralité du fichier de logs en mémoire pourrait être exagéré. Au lieu de cela, vous pouvez juste mettre un morceau du fichier de logs qui contient au moins un enregistrement complet d'un log. Étant donné que chaque enregistrement peut être entièrement analysé et traité indépendamment des autres enregistrements, vous n'avez pas besoin du fichier de log complet en mémoire. J'ai décrit comment parcourir un flux de données en morceaux (chunks) dans mon article Itération des flux en utilisant des tampons.
Le Tokenizer + la mémoire tampon de jetons (tokens)
Le tokenizer découpe la mémoire tampon en jetons. L'information des jetons est stockée dans la mémoire tampon des jetons, contenant :
- La position du jeton (start index)
- La longueur du jeton
- Le type du jeton (optionnel)
Les informations son stockées dans des tableaux. Voici un exemple de code :
public class IndexBuffer {
public int[] position = null;
public int[] length = null;
public byte[] type = null; /* assuming a max of 256 types (1 byte / type) */
}
Lorsque que le tokenizer trouve un jeton dans la mémoire tampon, il insère la position (start index) dans le tableau position, la longueur (taille) du jeton dans le tableau length, et le type du jeton dans le tableau type.
Si vous n'utilisez pas le tableau de types de jeton, vous pouvez encore déterminer si besoin le type d'un jeton à partir de ses données. c'est un compromis pour les performances par rapport à la consommation de mémoire.
Le Parseur
Le parseur a une nature similaire au tokenizer, sauf qu'il prend des jetons (tokens) en entrée et renvoie des indices d'éléments. Tout comme les tokens (ou jetons), un élément est marqué par sa position (index de départ), la longueur et éventuellement son type d'élément. Ces nombres sont mémorisés dans la même structure que celle utilisée pour mémoriser les jetons.
Là encore, la matrice (tableau) de types est optionnelle. Si vous pouvez déterminer le type de l'élément facilement sur la base des premiers octets ou caractères de l'élément, vous n'avez pas besoin de stocker les types.
La granularité précise des éléments marqués dans le buffer d'élément est fonction des données qui sont analysées ainsi que du code qui doit traiter les données par la suite. Par exemple, si vous implémentez un analyseur (parser) XML, vous pouvez marquer chaque balise de début, attribut et balise de fin comme "éléments de l'analyseur (parser)" distincts.
Le Tampon (buffer) d'éléments ou Index
L'analyseur produit un tampon d'éléments avec des indices des données d'origine. Les indices marquent la position (indice de départ), la longueur et le type des éléments que l'analyseur a trouvés dans les données. Vous pouvez utiliser ces indices pour naviguer dans les données d'origine.
En regardant le code ci-dessus de IndexBuffer, vous pouvez voir que la mémoire tampon de l'élément utilise neuf octets par élément, quatre octets pour la position, quatre octets pour la taille du jeton, et un octet pour le type de jeton.
Vous pouvez être en mesure de réduire la consommation mémoire de IndexBuffer. Par exemple, si vous savez ce que les éléments ne font jamais plus de 65 536 octets, vous pouvez utiliser un tableau de short au lieu de int pour la taille des jetons. Cela vous fera économiser deux octets par élément, ce qui porte la consommation de mémoire à sept octets par élément.
En outre, si vous savez que les fichiers que vous parsez ne font jamais plus de 16,777,216 octets, vous aurez seulement besoin de trois octets pour la position (indice de départ). Le quatrième octet de chaque int dans la matrice de position pourrait alors contenir le type d'élément, ce qui élimine la nécessité d'un groupement de type. Si vous avez moins de 128 types de jetons, vous pouvez utiliser sept bits pour les types de jetons au lieu de huit. Cela vous permet de passer à 25 bits sur la position, ce qui augmente la position maximale à 33,554,432. Si vous avez moins de 64 types de jetons, vous pouvez attribuer un autre morceau à la position etc.
Actuellement, VTD-XML compacte toutes ces informations dans un long pour économiser de l'espace. Vous perdez un peu de vitesse en raison de la manipulation de bits supplémentaires nécessaires pour emballer (pack) des champs distincts en un seul int ou long, mais vous économisez de la mémoire. Encore une fois, c'est un compromis.
Le "Navigateur" d'éléments
Le navigateur permet au code qui traite les données de naviguer le tampon (buffer) d'éléments. Rappelez-vous, un objet sémantique ou un élément (par exemple un élément XML) peuvent être constitués de multiples éléments du parseur. Pour faciliter la navigation, vous pouvez créer un objet navigateur pour se déplacer dans les éléments du parseur au niveau sémantique. Par exemple, un navigateur d'éléments XML peut naviguer dans le tampon d'éléments de balise de début (start tag) en balise de début.
L'utilisation d'un composant navigateur d'éléments est votre choix. Si vous implémentez un analyseur (parser) pour un usage unique dans un seul projet, vous pouvez l'ignorer. Mais si vous implémentez un parseur avec l'intention de le réutiliser dans d'autres projets, ou de le publier en open source, vous pouvez ajouter un composant de navigation d'éléments, en fonction de la complexité de la navigation dans les données analysées.
Etude de cas : un parseur JSON
Pour rendre la conception du parseur par superposition d'index (index overlay) plus concrète, j'ai mis en place un petit analyseur (parser) JSON en Java, basé sur la conception par superposition d'index (index overlay). Vous pouvez trouver le code complet sur GitHub.
JSON est l'abréviation de JavaScript Object Notation. JSON est un format de données populaire pour échanger des données entre les serveurs et navigateurs Web via AJAX, car les navigateurs web ont une prise en charge native pour analyser le JSON en objets JavaScript. À l'avenir, je vais supposer que vous êtes familier avec JSON.
Voici un simple exemple JSON :
{ "key1" : "value1" , "key2" : "value2" , [ "valueA" , "valueB" , "valueC" ] }
L'analyseur syntaxique JSON va briser cette chaîne JSON en jetons :
Les soulignements sont là pour souligner la longueur de chaque jeton.
Le marqueur sémantique détermine également les types de base de chaque jeton. Voici le même exemple JSON avec les types de jetons ajoutés :
Remarquez comment les types de jetons ne sont pas sémantiques. On ne voit que le type de jeton de base qu'ils sont et non ce qu'ils représentent réellement.
L'analyseur (parser) interprète les types de jetons de base et les remplace par des types sémantiques. Voici le même exemple JSON mais avec des types sémantiques (les éléments de l'analyseur) à la place :
Une fois que le parseur a terminé l'analyse du JSON ci-dessus, vous aurez un index (élément du buffer) constitué des positions, longueurs et types des éléments marqués ci-dessus. Vous pouvez ensuite naviguer dans l'index pour extraire les données dont vous avez besoin.
La mise en œuvre dans le référentiel GitHub contient deux analyseurs (parsers) de JSON. Celui qui divise l'analyse syntaxique entre un JsonTokenizer et un JsonParser (comme décrits plus haut dans cet article), et un JsonParser2 qui combine la création de jetons et l'analyse en une seule phase et une seule classe. Le JsonParser2 est plus rapide, mais aussi plus difficile à comprendre. Par conséquent, nous allons jeter un coup d'oeil rapide aux classes JsonTokenizer et JsonParser dans les sections suivantes, mais passer JsonParser2.
(Un lecteur de la première version de cet article a fait observer que la sortie du parseur par superposition d'index n'était pas très facile à utiliser pour extraire des données de la mémoire tampon d'origine. C'est pourquoi vous pouvez ajouter un composant de navigation d'éléments, comme mentionné plus haut. Pour montrer à quoi un tel composant de navigation pourrait ressembler, j'ai ajouté la classe JsonNavigator. Nous reviendrons rapidement à cette classe plus tard).
JsonTokenizer.parseToken()
Pour vous donner une idée de la mise en oeuvre de la création de jetons et de l'analyse, je vais vous montrer les parties principales de code de JsonTokenizer et JsonParser. Rappelez-vous, le code complet est disponible sur GitHub.
Voici la méthode JsonTokenizer.parseToken() qui analyse (parse) le jeton suivant dans la mémoire tampon de données :
public void parseToken() {
skipWhiteSpace();
this.tokenBuffer.position[this.tokenIndex] = this.dataPosition;
switch (this.dataBuffer.data[this.dataPosition]) {
case '{': {
this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_CURLY_BRACKET_LEFT;
}
break;
case '}': {
this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_CURLY_BRACKET_RIGHT;
}
break;
case '[': {
this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_SQUARE_BRACKET_LEFT;
}
break;
case ']': {
this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_SQUARE_BRACKET_RIGHT;
}
break;
case ',': {
this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_COMMA;
}
break;
case ':': {
this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_COLON;
}
break;
case '"': { parseStringToken(); } break;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9': {
parseNumberToken();
this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_NUMBER_TOKEN;
}
break;
case 'f': {
if (parseFalse()) {
this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_BOOLEAN_TOKEN;
}
}
break;
case 't': {
if (parseTrue()) {
this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_BOOLEAN_TOKEN;
}
}
break;
case 'n': {
if (parseNull()) {
this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_NULL_TOKEN;
}
}
break;
}
this.tokenBuffer.length[this.tokenIndex] = this.tokenLength;
}
Comme vous pouvez le voir, le code est assez simple. D'abord la méthode skipWhiteSpace() est appelée, ce qui saute tous les caractères d'espaces qui pourraient être présents dans les données à l'emplacement actuel. En second lieu, la position du jeton en cours (l'index dans la mémoire tampon de données) est mémorisée dans le tokenBuffer. Troisièment, le caractère suivant est examiné, et en fonction de ce caractère (ou de ce jeton), l'un des états de la commande switch case est exécuté. Enfin la longueur du jeton courant est stockée.
C'est vraiment tout ce qu'il faut pour découper en tokens (jetons) un tampon de données. Notez qu'une fois que le début d'un jeton de chaîne est trouvé, le tokenizer appelle la méthode parseStringToken(), ce qui balaie les données jusqu'à ce que la fin du jeton de chaîne soit trouvée. Cela s'exécute plus rapidement que d'essayer de traiter tous les cas à l'intérieur de la méthode parseToken(), et il est plus facile à mettre en oeuvre.
Le reste des méthodes dans JsonTokenizer sont juste là pour aider la méthode parseToken(), ou pour déplacer la position de données (index) pour le jeton suivant (première position après le jeton actuel) etc.
JsonParser.parseObject()
La principale méthode de la classe JsonParser est la méthode parseObject() qui vérifie les types des jetons obtenus à partir de la classe JsonTokenizer et tente à partir de cela de localiser des objets JSON dans les données d'entrée.
Voici la méthode parseObject() :
private void parseObject(JsonTokenizer tokenizer) {
assertHasMoreTokens(tokenizer);
tokenizer.parseToken();
assertThisTokenType(tokenizer.tokenType(), TokenTypes.JSON_CURLY_BRACKET_LEFT);
setElementData(tokenizer, ElementTypes.JSON_OBJECT_START);
tokenizer.nextToken();
tokenizer.parseToken();
byte tokenType = tokenizer.tokenType();
while (tokenType != TokenTypes.JSON_CURLY_BRACKET_RIGHT) {
assertThisTokenType(tokenType, TokenTypes.JSON_STRING_TOKEN);
setElementData(tokenizer, ElementTypes.JSON_PROPERTY_NAME);
tokenizer.nextToken();
tokenizer.parseToken();
tokenType = tokenizer.tokenType();
assertThisTokenType(tokenType, TokenTypes.JSON_COLON);
tokenizer.nextToken();
tokenizer.parseToken();
tokenType = tokenizer.tokenType();
switch (tokenType) {
case TokenTypes.JSON_STRING_TOKEN: {
setElementData(tokenizer, ElementTypes.JSON_PROPERTY_VALUE_STRING);
}
break;
case TokenTypes.JSON_STRING_ENC_TOKEN: {
setElementData(tokenizer, ElementTypes.JSON_PROPERTY_VALUE_STRING_ENC);
}
break;
case TokenTypes.JSON_NUMBER_TOKEN: {
setElementData(tokenizer, ElementTypes.JSON_PROPERTY_VALUE_NUMBER);
}
break;
case TokenTypes.JSON_BOOLEAN_TOKEN: {
setElementData(tokenizer, ElementTypes.JSON_PROPERTY_VALUE_BOOLEAN);
}
break;
case TokenTypes.JSON_NULL_TOKEN: {
setElementData(tokenizer, ElementTypes.JSON_PROPERTY_VALUE_NULL);
}
break;
case TokenTypes.JSON_CURLY_BRACKET_LEFT: {
parseObject(tokenizer);
}
break;
case TokenTypes.JSON_SQUARE_BRACKET_LEFT: {
parseArray(tokenizer);
}
break;
}
tokenizer.nextToken();
tokenizer.parseToken();
tokenType = tokenizer.tokenType();
if (tokenType == TokenTypes.JSON_COMMA) {
tokenizer.nextToken(); //skip , tokens if found here.
tokenizer.parseToken();
tokenType = tokenizer.tokenType();
}
}
setElementData(tokenizer, ElementTypes.JSON_OBJECT_END); }
}
La méthode parseObject() s'attend à voir une accolade gauche ({) suivi d'un jeton de chaîne, d'une virgule et d'un autre jeton de chaîne ou le début d'un tableau ([) ou d'un autre objet JSON. Comme JsonParser obtient ces jetons de la classe JsonTokenizer, il stocke le début, la longueur et la signification sémantique de ces jetons dans son propre elementBuffer (mémoire tampon d'éléments). Le code de traitement de données peut ensuite naviguer dans cet elementBuffer, pour extraire toutes les données nécessaires à partir des données d'entrée.
En voyant les éléments essentiels des classes JsonTokenizer et JsonParser, cela devrait donner une idée de la façon dont la "tokenisation" et le "parsing" fonctionnent. Pour bien comprendre comment le code fonctionne, vous devrez peut-être regarder l'ensemble des codes sources de JsonTokenizer et JsonParser. Ils font moins de 200 lignes de code chacun, ils sont donc raisonnablement accessibles.
JsonNavigator
Le JsonNavigator est un composant de navigation d'éléments. Il vous permet de naviguer de l'élément index créé par JsonParser et JsonParser2. Les indices produits par ces deux composants sont les mêmes, donc l'index est construit à partir de l'un ou de l'autre. Voici un exemple de code :
JsonNavigator jsonNavigator = new JsonNavigator(dataBuffer, elementBuffer);
Une fois JsonNavigator créé, vous pouvez naviguer dans les indices d'éléments en utilisant ses méthodes de navigation (next(), previous(), etc, et vous pouvez extraire des données en utilisant les méthodes asString(), asInt() et aslong(). Vous pouvez comparer les constantes de chaînes à l'élément dans la mémoire tampon de données en utilisant la méthode isEqualUnencoded(String).
L'utilisation de la classe JsonNavigator semble assez similaire à l'utilisation de l'API de streaming Gson. Regardez la méthode gsonStreamBuildObject(Reader) dans la classe AllBenchmarks, et la méthode parseJsonObject(JsonNavigator) dans la classe JsonObjectBuilder.
Elles se ressemblent beaucoup, n'est-ce pas ? Seule la méthode parseJsonObject() est capable d'utiliser une partie des optimisations (voir plus loin dans cet article) de JsonNavigator, comme compter les éléments primitifs dans un tableau, et de comparer plus rapidement les chaînes pour les champs JSON.
Benchmarks
VTD-XML a déjà fait une étude comparative approfondie de leur parseur XML versus StAX, SAX et DOM. VTD-XML gagne contre eux en performances brutes.
Afin d'établir une certaine crédibilité des performances du parseur par superposition d'index en général, j'ai étalonné mon parseur JSON par rapport à Gson. La première version de cet article ne mesurait que la vitesse d'analyse d'un fichier JSON et la construction d'un objet par réflexion avec Gson. Grâce aux commentaires des lecteurs, j'ai fait évoluer les benchmarks pour mesurer Gson selon quatre modes différents :
- Faire défiler tous les éléments du fichier JSON sans rien faire avec les données.
- Faire défiler tous les éléments du fichier JSON et en construire un
JsonObject. - Analyser le fichier JSON et en construire une
Map. - Analyser le fichier JSON et en construire un
JsonObjecten utilisant la réflexion.
Gardez à l'esprit que Gson est déjà mature et bien testé, avec une bonne gestion des signalements d'erreurs (bugtracker) etc. Mon parseur JSON est seulement à un niveau de proof-of-concept (prototype). L'analyse comparative est seulement faite pour obtenir une indication de la différence de performance. Ce ne sont pas les chiffres définitifs. N'oubliez pas de lire la discussion sur les benchmarks ci-dessous aussi.
Voici quelques détails sur la façon dont les benchmarks sont structurés :
- Afin de "chauffer" (affiner) le JIT : minimiser les temps des premiers accès (one-off overheads) etc. le parsing du JSON est effectué 10,000,000 fois pour les petits fichiers, 1,000,000 fois pour les moyens et gros fichiers.
- Les benchmarks sont répétés séparément pour trois fichiers différents pour voir comment les parseurs se comportent sur de petits, moyens et gros fichiers. Les tailles des fichiers sont 58 octets (bytes), 783 octets et 1854 octets. Cela signifie : exécuter d'abord 10,000,000 itérations sur un petit fichier et mesurer cela. Puis sur un fichier moyen, puis sur un fichier plus volumineux. Les fichiers se trouvent dans le répertoire de données dans le référentiel GitHub.
- Le fichier est chargé entièrement en mémoire avant que l'analyse et les mesures commencent. Le temps de chargement du fichier est exclut.
- Chaque mesure de 10,000,000 itérations (ou 1,000,000 itérations) s'exécute dans son propre processus. Cela signifie que chaque fichier est analysé dans des processus séparés. Un seul processus est exécuté à la fois. Chaque fichier est mesuré trois fois. Autrement dit, le processus d'analyser le fichier 10,000,000 fois est démarré et arrêté 3 fois. Les processus sont exécutés séquentiellement, et non pas en parallèle.
Voici les temps d'exécution en millisecondes :
| Benchmarks | Petit 1 | Petit 2 | Petit 3 | Moyen 1 | Moyen 2 | Moyen 3 | Gros 1 | Gros 2 | Gros 3 |
|---|---|---|---|---|---|---|---|---|---|
| JsonParser2 | 8.143 | 7.862 | 8.236 | 11.092 | 10.967 | 11.169 | 28.517 | 28.049 | 28.111 |
| JsonParser2 + Builder | 13.431 | 13.416 | 13.416 | 17.799 | 18.377 | 18.439 | 41.636 | 41.839 | 43.025 |
| JsonParser | 13.634 | 13.759 | 14.102 | 19.703 | 19.032 | 20.438 | 43.742 | 41.762 | 42.541 |
| JsonParser + Builder | 19.890 | 19.173 | 19.609 | 29.531 | 26.582 | 28.003 | 56.847 | 60.731 | 58.235 |
| Gson Stream | 44.788 | 45.006 | 44.679 | 33.727 | 34.008 | 33.821 | 69.545 | 69.111 | 68.578 |
| Gson Stream + Builder | 45.490 | 45.334 | 45.302 | 36.972 | 38.001 | 37.253 | 74.865 | 76.565 | 77.517 |
| Gson Map | 66.004 | 65.676 | 64.788 | 42.900 | 42.778 | 42.214 | 83.932 | 84.911 | 86.156 |
| Gson Reflection | 76.300 | 76.473 | 77.174 | 69.825 | 67.750 | 68.734 | 135.177 | 137.483 | 134.337 |
Voici une explication de ce que font les benchmarks :
| Description | |
|---|---|
| JsonParser2 | Analyse le fichier et localise les indices en utilisant JsonParser2. |
| JsonParser2 + Builder | Analyse le fichier et crée un JsonObject à l'aide de JsonParser2. |
| JsonParser | Analyse le fichier et localise les indices en utilisant JsonParser. |
| JsonParser + Builder | Analyse le fichier et crée un JsonObject à l'aide de JsonParser. |
| Gson Stream | Analyse le fichier et parcourt tous les jetons via l'API de streaming de Gson. |
| Gson Stream + Builder | Analyse le fichier et crée un JsonObject à l'aide de Gson. |
| Gson Map | Analyse le fichier et crée une Map à l'aide de Gson. |
| Gson Reflection | Analyse le fichier et crée un JsonObject à l'aide de Gson en utilisant la réflexion. |
Comme vous pouvez le voir, l'implémentation à base de superposition d'index (JsonParser et JsonParser2) est plus rapide que Gson. Ci-dessous, je vais discuter de certaines de mes spéculations sur les raisons de ceci.
Analyse des performances
La principale raison pour laquelle l'API de streaming de Gson n'est pas encore plus rapide, est que toutes les données sont extraites du flux lorsqu'il est parcouru, même si vous n'avez pas besoin de ces données. Chaque jeton est transformé en une String, int, double, etc, ce qui prend du temps. C'est aussi pourquoi l'analyse du fichier JSON et la construction d'un JsonOject à partir de ce fichier avec l'API de streaming de Gson est presque aussi rapide que juste en parcourant les éléments eux-mêmes. Le seul gain de temps est l'instanciation du JsonObject et des tableaux au sein du JsonObject.
L'extraction de données ne peut cependant pas à elle seule expliquer tout cela. Construire un JsonObject avec JsonParser2 est presque deux fois plus rapide que la construction d'un JsonObject avec l'API de streaming de Gson. Voici quelques-uns des avantages de performance que je vois dans l'utilisation d'un parseur avec superposition d'index par rapport à un parseur en mode "streaming" :
Tout d'abord, si vous regardez les benchmarks pour petits et grands fichiers, il semble que Gson a quelques temps d'initialisation associés à chaque analyse. Les différences de performance entre JsonParser2 + JsonParser et Gson sont plus grandes pour les petits fichiers. Cela pourrait être dû à la création de theCharArrayReader ou quelque chose de semblable. Cela pourrait aussi être quelque chose d'interne dans Gson.
Deuxièmement, un parseur à superposition d'index vous permet de choisir exactement combien de données vous voulez extraire. Cela vous donne un contrôle plus fin sur la performance du parseur.
Troisièmement, JsonParser et JsonParser2 détectent pendant la "tokenization" si un jeton de chaîne a des caractères d'échappement (par exemple "\" \ t \ n \ r ") qui doivent être convertis manuellement de UTF-8 vers UTF-16. Si un jeton de chaîne ne contient pas de caractères d'échappement, JsonNavigator peut utiliser un mécanisme de création de chaîne plus rapide.
Quatrièmement, le JsonNavigator permet des comparaisons de chaînes plus rapides par rapport aux données de la mémoire tampon. Ceci est pratique lorsque vous devez vérifier si le nom d'un champ est égal à une chaîne de caractères constante. Avec l'API de streaming de Gson, vous auriez à extraire le nom du champ dans un objet String, et à comparer la chaîne constante à l'objet String. Le JsonNavigator peut comparer la chaîne constante aux caractères dans la mémoire tampon de données directement, sans créer un objet String en premier. Cela permet d'économiser l'instanciation d'un objet String, et la copie de données provenant de la mémoire tampon de données dans un objet String qui est utilisé seulement pour la comparaison (par exemple, vérifier si le nom du champ JSON est égal à "clé" ou "nom" ou quelque chose d'autre). Voici à quoi cela ressemble avec le JsonNavigator :
if(jsonNavigator.isEqualUnencoded("fieldName")) { }
Cinquièmement, le JsonNavigator peut "regarder" vers l'avant dans son index et compter le nombre d'éléments dans les tableaux qui contiennent des valeurs primitives (chaînes, nombres, booléens, null etc, mais pas les objets ou tableaux imbriqués). Lorsque vous ne savez pas combien d'éléments un tableau contient, normalement vous extrayez les éléments et les mettez dans une liste (List). Une fois que vous rencontrez le marqueur de fin de tableau, vous convertissez la liste (List) en un tableau. Cela signifie que vous créez un objet List inutile. En outre, toutes les données extraites doivent être des objets à insérer dans une liste (List), même si le tableau contient des valeurs primitives comme des entiers ou des booléens. Cela génère de la création (instanciation) d'objets inutiles (dans tous les cas de l'auto-boxing inutile) lors de l'insertion dans la liste des valeurs extraites. Encore une fois, lors de la création du tableau de primitives, tous les objets doivent être convertis en des primitives à nouveau, et insérés dans le tableau. Voici à quoi cela ressemble en utilisant l'API de streaming de Gson :
List<Integer> elements = new ArrayList<Integer>();
reader.beginArray();
while (reader.hasNext()) {
elements.add(reader.nextInt());
}
reader.endArray();
int[] ints = new int[elements.size()];
for (int i = 0; i < ints.length; i++) {
ints[i] = elements.get(i);
}
jsonObject.numberArray = ints;
Lorsque vous connaissez le nombre d'éléments d'un tableau, vous pouvez créer le tableau Java définitif immédiatement et insérer les valeurs primitives directement dans ce tableau. Cela permet d'économiser l'instanciation de liste et la construction, l'auto-boxing de valeurs primitives, et la conversion des objets en valeurs primitives à nouveau lors de l'insertion des valeurs dans le tableau. Voici à quoi ressemble le même code en utilisant le JsonNavigator :
int[] ints = new int[jsonNavigator.countPrimitiveArrayElements()];
for (int i = 0, n = ints.length; i < n; i++) {
ints[i] = jsonNavigator.asInt();
jsonNavigator.next();
}
jsonObject.numberArray = ints;
Même lorsque vous êtes en train de construire des objets List à partir de tableaux JSON, connaître le nombre d'éléments vous permet d'instancier un ArrayList avec la bonne taille dès le début. De cette façon, vous n'êtes pas pénalisé par le redimensionnement dynamique de l'ArrayList lorsque vous atteignez la limite de sa capacité par défaut. Voici à quoi ressemble le code :
List<String> strings = new ArrayList<String>(jsonNavigator.countPrimitiveArrayElements());
jsonNavigator.next(); // skip over array start.
while (ElementTypes.JSON_ARRAY_END != jsonNavigator.type()) {
strings.add(jsonNavigator.asString());
jsonNavigator.next();
}
jsonNavigator.next(); //skip over array end.
Sixièmement, si vous avez accès à la mémoire tampon de données d'origine, vous pouvez utiliser des cordes (ropes) au lieu d'objets String à de nombreux endroits. Une corde est un objet jeton (token) de chaîne qui contient une référence à un tableau de caractères, une position de départ et une longueur. Vous pouvez faire des comparaisons de chaînes, copier la corde etc, tout comme avec une chaîne. Certaines opérations peuvent être plus rapides avec une corde qu'avec un objet String. Elles prennent également moins de mémoire parce qu'elles ne copient pas les données d'origine.
Septièmement, si vous avez besoin de faire beaucoup d'allers-retours dans les données, vous pouvez créer des indices encore plus avancés. L'index de VTD-XML contient le niveau d'indentation d'un élément, ainsi que des références à l'index de l'élément suivant au même niveau (frère (sibling) suivant), le premier élément d'un niveau d'indentation supérieur (premier ancêtre (ancestor)), etc. Ce sont tous des indices entiers (int) ajoutés à l'index d'éléments du parseur linéaire. Ces index supplémentaires peuvent rendre la navigation des données analysées extrêmement rapide.
Performances versus Rapport d'Erreurs
Si vous regardez le code de JsonParser et JsonParser2, vous verrez que si JsonParser2 est plus rapide, il a aussi le pire rapport d'erreurs par rapport à JsonParser. Lorsque la création de jetons et la phase analyse sont scindées en deux, une bonne validation des données et les rapports d'erreurs sont plus faciles à mettre en œuvre.
Normalement, cette différence devrait encourager un débat pour savoir si vous devez privilégier les performances ou les rapports d'erreurs au moment de décider de votre implémentation du parseur. Cependant, avec les analyseurs par superposition d'index, cette discussion n'est pas nécessaire.
Parce que les données d'origine sont toujours disponibles dans leur forme complète en mémoire, vous pouvez analyser ces mêmes données à la fois avec un parseur rapide ou lent. Vous pouvez commencer avec l'analyseur rapide, et si l'analyse échoue, vous pouvez utiliser un analyseur plus lent pour détecter où sont les erreurs dans les données d'entrée. Il faut juste fournir les données originales à l'analyseur le plus lent lorsque l'analyseur rapide échoue. De cette façon, vous pourrez obtenir le meilleur des deux mondes.
Discussion à propos des Benchmarks
Il ne serait pas juste de comparer un parseur qui crée une arborescence d'objets à partir de données (Gson) à un parseur qui marque juste l'index des éléments trouvés dans les données sans débattre de ce qui est comparé.
Analyser un fichier dans une application en cours d'exécution nécessite généralement les étapes suivantes :
Tout d'abord, les données sont chargées soit à partir du disque, soit à partir du réseau. Deuxièmement, les données sont décodées, par exemple, de UTF-8 en UTF-16. En troisième lieu, les données sont analysées. En quatrième lieu, les données sont traitées.
Afin de mesurer simplement la vitesse du parseur brut, j'ai préchargé les fichiers qui doivent être analysés en mémoire, le code "benchmarké" n'a, en aucune façon, traité les données. Bien que seules les vitesses d'analyses brutes soient "benchmarkées", la différence ne se traduit pas par un exact accroissement de la performance de l'application en cours d'exécution. Voici pourquoi :
Un analyseur en continu (streaming) est souvent en mesure de commencer l'analyse des données entrantes avant que toutes les données soient chargées dans la mémoire. Etant donnée l'implémentation actuelle de mon parseur JSON, il ne peut pas fonctionner de cette façon. Cela signifie que même s'il est plus rapide dans l'analyse des données brutes, dans une application de la vie réelle en cours d'exécution où mon analyseur devra attendre les données à charger, il pourra, finalement, ne pas être le plus rapide. Ceci est illustré dans le schéma ci-dessous:
Vous pourriez probablement modifier mon parseur pour qu'il puisse analyser les données pendant leur chargement, dans le but d'accélérer le temps de l'analyse totale. Mais ce serait probablement un peu au détriment des performances brutes du parseur. Bien que la vitesse totale en serait peut-être un peu améliorée.
En outre, en préchargeant les données en mémoire avant d'exécuter les "benchmarks", je saute aussi l'étape de décodage des données. Le décodage de données UTF-8 en UTF-16 n'est pas facultatif. Dans une application réelle, vous ne pouvez pas contourner cette étape. Chaque fichier à analyser devra être décodé. Ceci est cependant le cas de tous les parseurs. Un parseur en continu (streaming) peut être en mesure de décoder les données comme il les lit. Un analyseur par superposition d'index serait aussi en mesure de les décoder lors de la lecture en mémoire tampon.
VTD-XML et Jackson (un autre parseur JSON) utilisent une autre technique. Ils ne décodent pas les données brutes du tout. A la place, ils tokenizent directement sur les données brutes, quel que soit le format des données (ASCII, UTF-8, etc.). Cela permet d'économiser une étape coûteuse de décodage, au prix d'un marqueur sémantique plus complexe.
En général, la seule façon de vraiment savoir qui sera le parseur le plus rapide dans votre application, est de tous les comparer ("benchmarker") sur le travail réel que vous avez à faire avec les données que vous devez analyser.
Discussion globale à propos des parseurs par superposition d'index (index overlay)
Un argument que j'ai entendu contre les parseurs par superposition d'index est que pour être en mesure de "pointer" dans les données d'origine plutôt que de les extraire dans un arbre d'objets, il est nécessaire de garder toutes les données en mémoire lors de l'analyse. Cela peut produire un pic de consommation mémoire lors du traitement de gros fichiers.
En général, l'argument est qu'un parseur en continu (comme SAX ou Stax) peut analyser des fichiers volumineux sans jamais avoir l'intégralité du fichier en mémoire. Cependant, cela n'est vrai que si les données dans le fichier peuvent être analysées et traitées en petits morceaux (chunks), où chaque morceau peut être analysé et traité indépendamment des autres morceaux. Par exemple, un gros fichier XML contient une liste d'éléments, dont chacun peut être analysé et traité individuellement (comme une liste d'enregistrements de journal). Mais, si vos données peuvent être analysées séparément en morceaux indépendants, vous pouvez aussi mettre en œuvre un parseur à superposition d'index qui en soit capable.
Si le fichier ne peut pas être analysé en morceaux indépendants, vous aurez néanmoins besoin d'extraire les informations nécessaires dans une structure qui puisse être consultée par le code qui traite les morceaux (chunks). Mais si vous pouvez le faire avec un parseur en continu (streaming), vous pouvez aussi le faire avec un parseur à superposition d'index.
Les parseurs qui créent des arborescences d'objets à partir de données d'entrée consomment souvent beaucoup plus de grandes quantités de mémoire avec l'arborescence d'objets de la taille d'origine des données. Cela est dû à la surcharge de la mémoire associée à une instance de l'objet, ainsi qu'aux données supplémentaires nécessaires pour maintenir les références entre les objets.
En outre, dès lors que toutes les données sont en mémoire, vous devez allouer un tampon de données pour l'analyse qui soit assez grand pour contenir toutes les données. Mais que faire si vous ne savez pas quelle est la taille des fichiers quand vous commencez à les analyser ?
Imaginez que vous avez une application Web (ou un service Web ou une autre application serveur) où les utilisateurs peuvent télécharger (uploader) des fichiers. Vous ne pouvez pas connaître la taille des fichiers, alors comment pouvez-vous allouer un tampon approprié pour eux avant que l'analyse syntaxique commence ? Et bien, pour des raisons de sécurité, vous devriez toujours avoir une taille de fichier maximale autorisée. Sinon, les utilisateurs peuvent être en mesure de planter votre système en téléchargeant des fichiers très volumineux. Ou ils peuvent même écrire un programme qui fait semblant d'être un navigateur téléchargeant (uploading) un fichier, et qui ne cesserait jamais d'envoyer des données à votre serveur. Vous pouvez attribuer un tampon (buffer) de la taille de fichier maximale autorisée. De cette façon, votre tampon ne va pas manquer d'espace pour les fichiers valides. Si c'est un manque d'espace, votre utilisateur a téléchargé (uploaded) un fichier trop grand de toute façon.
A propos de l'Auteur
Jakob Jenkov est un Entrepreneur, Ecrivain et Développeur de logiciels vivant actuellement à Barcelone, Espagne. Jakob a appris Java en 1997, et travaille professionnellement "en Java" depuis 1999. Il se concentre actuellement sur la notion d'efficacité à travers une variété de domaines (logiciels, processus, entreprises, etc.). Il est titulaire d'une maîtrise de sciences en informatique de l'Université IT de Copenhague. Vous pouvez en savoir plus sur son travail sur son site Web.