[xml] [Patch] Optimizing '//' in XPath expressions

When investigating the libxslt performance problem reported in bug #657665, I found that '//' in XPath expressions can be very slow when working on large subtrees.

One of the reasons is the seemingly quadratic time complexity of the duplicate checks when merging result nodes. The other is a missed optimization for expressions of the form 'descendant-or-self::node()/axis::test'. Since '//' is expanded to '/descendant-or-self::node()/', this type of expression is quite common. Depending on the axis of the expression following the 'descendant-or-self' step, the following replacements can be made:

from descendant-or-self::node()/child::test
to   descendant::test

from descendant-or-self::node()/descendant::test
to   descendant::test

from descendant-or-self::node()/self::test
to   descendant-or-self::test

from descendant-or-self::node()/descendant-or-self::test
to   descendant-or-self::test

'test' can be any kind of node test.

With these replacements the possibly huge result of 'descendant-or-self::node()' doesn't have to be stored temporarily, but can be processsed in one pass. If the resulting nodeset is small, the duplicate checks aren't a problem.

I found that there already is a function called xmlXPathRewriteDOSExpression which performs this optimization for a very limited set of cases. It employs a complicated iteration scheme for rewritten expressions. AFAICS, this can be avoided by simply changing the axis of the expression like described above.

With the attached patch against libxml2 and the files from bug #657665 I got the following results.


$ time xsltproc/xsltproc --noout service-names-port-numbers.xsl service-names-port-numbers.xml
real    2m56.213s
user    2m56.123s
sys     0m0.080s


$ time xsltproc/xsltproc --noout service-names-port-numbers.xsl service-names-port-numbers.xml
real    0m3.836s
user    0m3.764s
sys     0m0.060s

I also ran the libxml2 and libxslt test suites with the patch and couldn't detect any breakage.


Attachment: Optimizations-for-descendant-or-self-node.patch
Description: Text document

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]