[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

Re: [xsl] Processing milestoned XML leads to many preceding:: calls and horrible performance

Subject: Re: [xsl] Processing milestoned XML leads to many preceding:: calls and horrible performance
From: Michael Kay <mike@xxxxxxxxxxxx>
Date: Tue, 21 Feb 2012 10:28:05 +0000

On 21/02/2012 09:07, MatDj Cepl wrote:

The problem is (I think) in both <vers/> (that's "verse" in Czech) and <kap/> (that's an abbreviation of "chapter") are just milestones, so I have to go through all verses in whole book all the time (yes, this is http://www.joelonsoftware.com/articles/fog0000000319.html all over again).

Any ideas? Would some other XSLT processors other than xsltproc (libxml 20706, libxslt 10126 and libexslt 815) I am using be able to optimize this somehow?

Thanks a lot,


There are quite a few things that can be done to improve your XSLT code, as Andrew has pointed out; especially if you move to an XSLT 2.0 processor. But the problem is not a superficial coding problem, it's the basic algorithmic design. Looking at that horrendous XPath expression

select="count(./preceding::kap[1]/following::*[not(count(preceding-sibling::vers|current()) = count(preceding-sibling::vers))])"

XSLT 2.0 allows you to simplify the predicate to [not(preceding-sibling::vers intersect current())], but that isn't going to solve the problem for you: no processor I can think of will improve preceding::x/following::x so that it isn't quadratic in the size of the document, and you are doing this once for each verse, so that makes it cubic.

I think the right way to tackle this is to do a 2-phase transformation. The first should convert your milestoned XML into normal hierarchic XML, and the second should process the hierarchic XML to do whatever you want to do with it.

The first phase will typically use sibling recursion if you use XSLT 1.0, or positional grouping if you use XSLT 2.0. Either way, it should have linear performance (though with XSLT 1.0 you may hit stack overflow problems if the recursion goes too deep).

Michael Kay

Current Thread