Complejidad algorítmica de los analizadores/validadores XML

Question

Necesito saber cómo el rendimiento de las diferentes herramientas XML (analizadores, validadores, evaluadores de expresiones XPath, etc.) se ve afectado por el tamaño y la complejidad del documento de entrada. ¿Existen recursos que documentan cómo el tiempo de CPU y el uso de la memoria se ven afectados por ... bueno, qué? ¿Tamaño del documento en bytes? Número de nodos? ¿Y la relación es lineal, polinómica o peor?

actualización

En un artículo publicado en la revista IEEE Computer, vol 41 n ° 9, sept 2008, los autores encuesta de cuatro modelos de análisis de XML populares (DOM, SAX, Stax y VTD). Ejecutan algunas pruebas de rendimiento muy básicas que muestran que un analizador DOM tendrá su rendimiento reducido a la mitad cuando el tamaño del archivo de entrada aumente de 1 a 15 KB a 1 a 15 MB o aproximadamente 1000 veces más. El rendimiento de los otros modelos no se ve significativamente afectado.

Desafortunadamente no realizaron estudios más detallados, como el uso de rendimiento/memoria en función del número de nodos/tamaño.

El artículo es here.

actualización

he podido encontrar ningún tratamiento formal de este problema. Por lo que vale, he realizado algunos experimentos para medir la cantidad de nodos en un documento XML en función del tamaño del documento en bytes. Estoy trabajando en un sistema de gestión de almacenes y los documentos XML son documentos de almacén típicos, p. aviso de envío avanzado, etc.

El siguiente gráfico muestra la relación entre el tamaño en bytes y el número de nodos (que debe ser proporcional a la huella de memoria del documento en un modelo DOM). Los diferentes colores corresponden a diferentes tipos de documentos. La escala es log/log. La línea negra es la que mejor se ajusta a los puntos azules. Es interesante observar que para todo tipo de documentos, la relación entre el tamaño del byte y el tamaño del nodo es lineal, pero que el coeficiente de proporcionalidad puede ser muy diferente.

Answer 1

Si me encontré con ese problema y no pude encontrar nada en Google que probablemente probaría a hacerlo a mi auto.

Algunas cosas de "retroceso de un sobre" para tener una idea de hacia dónde se dirige. Pero me necesitaría tener una idea de cómo hacer un analizador xml. Para los puntos de referencia no algorítmicas echar un vistazo aquí:

• 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

creo que hay demasiadas variables involucradas para llegar a una complejidad métrica simple a menos que haga muchas suposiciones.

Un analizador de estilo SAX simple debe ser lineal en términos de tamaño del documento y plano para la memoria.

Algo como XPath sería imposible de describir en términos de solo el documento de entrada ya que la complejidad de la expresión XPath juega un papel muy importante.

Del mismo modo para la validación de esquema, un esquema grande pero simple puede ser lineal, mientras que un esquema más pequeño que tiene una estructura mucho más compleja mostraría un peor rendimiento en tiempo de ejecución.

Al igual que con la mayoría de las preguntas de rendimiento, la única manera de obtener respuestas precisas es medirlo y ver qué pasa.

Answer 3

Rob Walker tiene razón: el problema no se especifica con suficiente detalle. Teniendo en cuenta solo los analizadores (e ignorando la cuestión de si realizan la validación), hay dos sabores principales: DOM basado en árboles y streaming/basado en eventos, piense en SAX (push) y StAX (pull). Hablando en grandes generalidades, los enfoques basados ​​en árbol consumen más memoria y son más lentos (porque es necesario terminar de analizar todo el documento), mientras que los enfoques de transmisión/eventos consumen menos memoria y son más rápidos. Los analizadores basados ​​en árboles generalmente se consideran más fáciles de usar, aunque StAX ha sido anunciado como una gran mejora (en facilidad de uso) con respecto a SAX.

Answer 4

Estaba planeando cargar archivos XML extremadamente grandes en mi aplicación. Hice la pregunta aquí en Stack Overflow: Fastest Possible XML handling for very large documents.

Y sí, fue la parte de análisis, ese fue el cuello de botella.

Terminé sin utilizar analizadores XML en absoluto. En cambio, analicé los caracteres uno por uno de la manera más eficiente posible optimizando la velocidad. Esto dio como resultado velocidades de 40 MB por segundo en una PC con Windows de 3 GHz para la lectura, el análisis y la carga de la estructura de datos interna.

Me interesaría mucho escuchar cómo los diferentes modos de análisis XML se comparan con esto.