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

[Nick Wellnhofer <wellnhofer aevum de>]

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.

Before:

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

After:

$ 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.

Nick

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