kc3-lang/libxml2

2012-08-19T19:42:38

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. 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 >From e0f5a8261760e4f257b90410be27657e984237c8 Mon Sep 17 00:00:00 2001 From: Nick Wellnhofer <wellnhofer@aevum.de> Date: Sun, 19 Aug 2012 18:20:22 +0200 Subject: [PATCH] Optimizations for descendant-or-self::node() Currently, the function xmlXPathRewriteDOSExpression optimizes expressions of type '//child'. Instead of adding a 'rewriteType' and doing a compound traversal, the same can be achieved simply by setting the axis of the node test from 'child' to 'descendant'. There are also many other cases that can be optimized similarly. This commit augments xmlXPathRewriteDOSExpression to essentially rewrite the following subexpressions: - descendant-or-self::node()/child:: to descendant:: - descendant-or-self::node()/descendant:: to descendant:: - descendant-or-self::node()/self:: to descendant-or-self:: - descendant-or-self::node()/descendant-or-self:: to descendant-or-self:: Since the '//' shortcut in XPath is translated to '/descendant-or-self::node()/', this greatly speeds up expressions using '//' on large subtrees.