After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 133736 - Relax NG validation sometimes takes long
Relax NG validation sometimes takes long
Status: RESOLVED OBSOLETE
Product: libxml2
Classification: Platform
Component: relaxng
2.6.5
Other Linux
: Normal enhancement
: ---
Assigned To: William M. Brack
libxml QA maintainers
Depends on:
Blocks:
 
 
Reported: 2004-02-07 15:56 UTC by Tobi
Modified: 2021-07-05 13:22 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
RELAX NG schema, with exponential time problem (1.19 KB, text/plain)
2006-07-24 18:21 UTC, Yoyo Zhou
Details
RELAX NG schema, no exponential time problem (1.33 KB, text/plain)
2006-07-24 18:23 UTC, Yoyo Zhou
Details
XML file whose validation takes too long (88 bytes, text/plain)
2006-07-24 18:26 UTC, Yoyo Zhou
Details

Description Tobi 2004-02-07 15:56:45 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 $
Comment 1 William M. Brack 2004-08-22 13:48:26 UTC
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
Comment 2 Yoyo Zhou 2006-07-24 18:18:44 UTC
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.)
Comment 3 Yoyo Zhou 2006-07-24 18:21:16 UTC
Created attachment 69514 [details]
RELAX NG schema, with exponential time problem
Comment 4 Yoyo Zhou 2006-07-24 18:23:39 UTC
Created attachment 69516 [details]
RELAX NG schema, no exponential time problem
Comment 5 Yoyo Zhou 2006-07-24 18:26:17 UTC
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>.
Comment 6 Henrik Levkowetz 2018-02-05 13:16:18 UTC
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.
Comment 7 GNOME Infrastructure Team 2021-07-05 13:22:29 UTC
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.