GNOME Bugzilla – Bug 665710
xmllint RNG validation time increases exponentially with number of attributes on a node
Last modified: 2021-07-05 13:21:09 UTC
Created attachment 202956 [details] schemas/dtd, test documents and timing scripts OVERVIEW Validation time increases exponentially with the number of attributes on a to-be-validated element. I created a very simple DTD with only one element that has up to 20 attributes, created XSD and RNG versions. I created a number of test documents with 10 to 20 attributes on the root node and timed how long it takes xmllint to validated those using the different schemas. STEPS TO REPRODUCE 1. Unzip attachment 2 [details]. Run scripts time_xmllint_dtd.sh, time_xmllint_xsd.sh and time_xmllint_rng.sh 3. Compare output ACTUAL RESULTS The scripts were run on an otherwise idle machine ./time_xmllint_dtd.sh real 0m0.081s user 0m0.000s sys 0m0.000s real 0m0.004s user 0m0.000s sys 0m0.000s real 0m0.004s user 0m0.000s sys 0m0.004s real 0m0.004s user 0m0.000s sys 0m0.000s real 0m0.013s user 0m0.000s sys 0m0.000s real 0m0.004s user 0m0.000s sys 0m0.000s real 0m0.004s user 0m0.000s sys 0m0.004s real 0m0.004s user 0m0.000s sys 0m0.000s real 0m0.004s user 0m0.000s sys 0m0.000s real 0m0.005s user 0m0.000s sys 0m0.000s real 0m0.005s user 0m0.000s sys 0m0.004s =========================== ./time_xmllint_xsd.sh 10attributes.xml validates real 0m0.050s user 0m0.000s sys 0m0.004s 11attributes.xml validates real 0m0.005s user 0m0.000s sys 0m0.004s 12attributes.xml validates real 0m0.005s user 0m0.000s sys 0m0.008s 13attributes.xml validates real 0m0.011s user 0m0.000s sys 0m0.004s 14attributes.xml validates real 0m0.005s user 0m0.000s sys 0m0.004s 15attributes.xml validates real 0m0.005s user 0m0.000s sys 0m0.004s 16attributes.xml validates real 0m0.005s user 0m0.004s sys 0m0.000s 17attributes.xml validates real 0m0.005s user 0m0.008s sys 0m0.000s 18attributes.xml validates real 0m0.005s user 0m0.000s sys 0m0.004s 19attributes.xml validates real 0m0.005s user 0m0.004s sys 0m0.000s 20attributes.xml validates real 0m0.005s user 0m0.000s sys 0m0.000s =========================== $ ./time_xmllint_rng.sh 10attributes.xml validates real 0m0.030s user 0m0.024s sys 0m0.004s 11attributes.xml validates real 0m0.041s user 0m0.040s sys 0m0.000s 12attributes.xml validates real 0m0.159s user 0m0.156s sys 0m0.004s 13attributes.xml validates real 0m0.970s user 0m0.968s sys 0m0.000s 14attributes.xml validates real 0m5.184s user 0m5.176s sys 0m0.004s 15attributes.xml validates real 0m22.703s user 0m22.657s sys 0m0.040s 16attributes.xml validates real 1m39.272s user 1m39.242s sys 0m0.028s 17attributes.xml validates real 6m37.241s user 6m35.489s sys 0m1.704s 18attributes.xml validates real 27m3.121s user 26m57.529s sys 0m5.400s ^C real 2m21.173s user 2m20.469s sys 0m0.684s =========================== Test was aborted at this point because execution times of several hours were to be expected. EXPECTED RESULTS Execution times of RNG validation should be on a scale that's at least remotely comparable to DTD and XSD validation. Exponential growth is unexpected. BUILD DATE AND PLATFORM Compiled on Ubuntu Oneiric, December 6th, from git checkout $ xmllint --version xmllint: using libxml version 20708 compiled with: Threads Tree Output Push Reader Patterns Writer SAXv1 FTP HTTP DTDValid HTML Legacy C14N Catalog XPath XPointer XInclude Iconv ISO8859X Unicode Regexps Automata Expr Schemas Schematron Modules Debug Zlib
Sorry, compiled on Ubuntu Natty, 32bit (not Oneiric)
GNOME is going to shut down bugzilla.gnome.org in favor of gitlab.gnome.org. As part of that, we are mass-closing older open tickets in bugzilla.gnome.org which have not seen updates for a longer time (resources are unfortunately quite limited so not every ticket can get handled). If you can still reproduce the situation described in this ticket in a recent and supported software version, then please follow https://wiki.gnome.org/GettingInTouch/BugReportingGuidelines and create a new ticket at https://gitlab.gnome.org/GNOME/libxml2/-/issues/ Thank you for your understanding and your help.