Complexité algorithmique des analyseurs/validateurs XML

Question

J'ai besoin de savoir comment les performances des différents outils XML (analyseurs, validateurs, évaluateurs d'expressions XPath, etc.) sont affectées par la taille et la complexité du document d'entrée.Existe-t-il des ressources qui documentent comment le temps CPU et l'utilisation de la mémoire sont affectés par...eh bien, quoi ?Taille du document en octets ?Nombre de nœuds ?Et la relation est-elle linéaire, polynomiale ou pire ?

Mise à jour

Dans un article paru dans IEEE Computer Magazine, vol 41 nr 9, septembre 2008, les auteurs étudient quatre modèles d'analyse XML populaires (DOM, SAX, StAX et VTD).Ils exécutent des tests de performances très basiques qui montrent qu'un analyseur DOM verra son débit réduit de moitié lorsque la taille du fichier d'entrée passe de 1 à 15 Ko à 1 à 15 Mo, soit environ 1 000 fois plus grande.Le débit des autres modèles n’est pas significativement affecté.

Malheureusement, ils n’ont pas réalisé d’études plus détaillées, notamment sur l’utilisation du débit/mémoire en fonction du nombre de nœuds/taille.

L'article est ici.

Mise à jour

Je n'ai trouvé aucun traitement formel de ce problème.Pour ce que ça vaut, j'ai fait quelques expériences mesurant le nombre de nœuds dans un document XML en fonction de la taille du document en octets.Je travaille sur un système de gestion d'entrepôt et les documents XML sont des documents d'entrepôt typiques, par ex.préavis d'expédition, etc.

Le graphique ci-dessous montre la relation entre la taille en octets et le nombre de nœuds (qui doit être proportionnel à l'empreinte mémoire du document dans un modèle DOM).Les différentes couleurs correspondent à différents types de documents.L'échelle est log/log.La ligne noire correspond le mieux aux points bleus.Il est intéressant de noter que pour tous types de documents, la relation entre la taille des octets et la taille des nœuds est linéaire, mais que le coefficient de proportionnalité peut être très différent.

Answer 1

Si j'étais confronté à ce problème et que je ne trouvais rien sur Google, j'essaierais probablement de le faire moi-même.

Quelques trucs "à l'arrière-plan" pour avoir une idée de là où ça va.Mais il faudrait que j'aie une idée de comment faire un analyseur XML.Pour les benchmarks non algorithmiques, jetez un oeil ici :

• http://www.xml.com/pub/a/Benchmark/exec.html
• http://www.devx.com/xml/Article/16922
• http://xerces.apache.org/xerces2-j/faq-performance.html

Answer 2

Je pense qu'il y a trop de variables impliquées pour arriver à une mesure de complexité simple, à moins que vous ne fassiez beaucoup d'hypothèses.

Un analyseur simple de style SAX doit être linéaire en termes de taille de document et plat pour la mémoire.

Quelque chose comme XPath serait impossible à décrire uniquement en termes de document d'entrée puisque la complexité de l'expression XPath joue un rôle énorme.

De même pour la validation de schéma, un schéma volumineux mais simple peut très bien être linéaire, alors qu'un schéma plus petit ayant une structure beaucoup plus complexe afficherait de moins bonnes performances d'exécution.

Comme pour la plupart des questions de performances, la seule façon d’obtenir des réponses précises est de les mesurer et de voir ce qui se passe !

Answer 3

Rob Walker a raison :le problème n'est pas spécifié de manière suffisamment détaillée.En considérant uniquement les analyseurs (et en ignorant la question de savoir s'ils effectuent la validation), il existe deux versions principales :basé sur l'arborescence - pensez DOM - et basé sur le streaming / les événements - pensez SAXO (appuyer) et StAX (tirer).En termes généraux, les approches basées sur les arbres consomment plus de mémoire et sont plus lentes (car vous devez terminer l'analyse de l'ensemble du document), tandis que les approches basées sur le streaming/événements consomment moins de mémoire et sont plus rapides.Les analyseurs basés sur des arbres sont généralement considérés comme plus faciles à utiliser, bien que StAX ait été présenté comme une énorme amélioration (en termes de facilité d'utilisation) par rapport à SAX.

Answer 4

J'avais l'intention de charger des fichiers XML extrêmement volumineux dans mon application.J'ai posé la question ici sur Stack Overflow : Gestion XML la plus rapide possible pour les très gros documents.

Et oui, c'était la partie analyse, c'était le goulot d'étranglement.

J'ai fini par ne plus utiliser d'analyseurs XML.Au lieu de cela, j'ai analysé les caractères un par un aussi efficacement que possible en optimisant la vitesse.Cela a abouti à des vitesses de 40 Mo par seconde sur un PC Windows 3 GHz pour la lecture, l'analyse et le chargement de la structure de données interne.

Je serais très intéressé de savoir comment les différents modes d'analyse XML se comparent à cela.