GNOME Bugzilla – Bug 133736
Relax NG validation sometimes takes long
Last modified: 2021-07-05 13:22:29 UTC
It takes xmllint 1.5 minutes to validate the SVG doc (while it takes Jing 3 seconds including the JVM startup, AFAICS). Perhaps it could be optimized in this respect? Here's the screen, I hope you can reproduce it: tobi ~/del/compare $ wget -q http://www.w3.org/Graphics/SVG/1.1/rng/rng.zip tobi ~/del/compare $ unzip -q rng.zip tobi ~/del/compare $ ruby -ni.bak -e 'print if not /^<!DOCTYPE/' *.rng tobi ~/del/compare $ wget -q http://www.pinkjuice.com/howto/vimxml/pics/cos_pattern.svg tobi ~/del/compare $ time jing svg11.rng cos_pattern.svg real 0m5.092s user 0m2.236s sys 0m0.084s tobi ~/del/compare $ time jing svg11.rng cos_pattern.svg real 0m3.230s user 0m2.223s sys 0m0.062s tobi ~/del/compare $ time xmllint --noout --relaxng svg11.rng cos_pattern.svg cos_pattern.svg validates real 1m31.982s user 1m21.625s sys 0m0.428s tobi ~/del/compare $ time xmllint_cvs --noout --relaxng svg11.rng cos_pattern.svg cos_pattern.svg validates real 1m27.662s user 1m20.474s sys 0m0.457s tobi ~/del/compare $ xmllint --version /home/tobi/bulk/run/libxml/2.6.5/bin/xmllint: using libxml version 20605 compiled with: DTDValid FTP HTTP HTML C14N Catalog XPath XPointer XInclude Iconv Unicode Regexps Automata Schemas tobi ~/del/compare $ xmllint_cvs --version /home/tobi/bulk/run/libxml/cvs/bin/xmllint: using libxml version 20605 compiled with: DTDValid FTP HTTP HTML C14N Catalog XPath XPointer XInclude Iconv Unicode Regexps Automata Schemas tobi ~/del/compare $
Just a note to mention that we are still looking at this. It's not an easy problem to solve, but it hasn't been forgotten :-) Bill
I've found what seems to be an exponential runtime when doing RELAX NG validation when the schema contains lots of <optional><attribute> blocks attached to a single element *and* many of these attributes are specified in the XML to be validated. The runtime is approximately O((4.5)^n), where n is the number of such attributes that are specified. (However, I only begin to really notice the slowness when n gets to around 14.) I can provide a simple testcase of a single element with 16 optional attributes, all specified, and I get a runtime of: real 1m42.427s user 1m41.964s sys 0m0.037s $ xmllint --version xmllint: using libxml version 20616 compiled with: DTDValid FTP HTTP HTML C14N Catalog XPath XPointer XInclude Iconv Unicode Regexps Automata Schemas When I enclosed the <optional><attribute> blocks all in a single <interleave>, however, the runtime didn't show this behavior at all: real 0m0.009s user 0m0.001s sys 0m0.003s Likewise, optional elements and interleaved elements didn't have this slowness problem. (I've only taken a cursory look at the rng supplied by the bug reporter, but it does seem to contain many <optional><attribute> blocks.)
Created attachment 69514 [details] RELAX NG schema, with exponential time problem
Created attachment 69516 [details] RELAX NG schema, no exponential time problem
Created attachment 69517 [details] XML file whose validation takes too long The time to validate this file with the "schema with exponential time problem" is exponential in the number of attributes specified in <root>.
I just ran into this, and spent quite a while reducing it till I could identify it as a very unfortunate validation time dependency on the number of attributes on <root>. In other words, this is still an issue. The versions I've tested this with are: Debian: libxml2:amd64/jessie 2.9.1+dfsg1-5+deb8u6 Darwin: libxml2 @2.9.7 (macports) Some timing info, using --timing, with varying number of <root> attributes. --timing's 'Validation' figures in the validation column. This is on Linux: #attr validation 13 34 ms 14 116 ms 15 434 ms 16 1679 ms 17 6655 ms 18 65540 ms 19 377141 ms These times confirm the ~O( 4.5^n ) behaviour reported by the OP. The numbers are different on Darwin, but the progression seems equivalent. I'm not attaching additional schema and file to validate as the OP poster's should be fine; just posting to confirm the issue and behaviour.
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.