Re: [xslt] XSLT compilation is slow for big XSLTs

On Thu, Aug 20, 2015 at 07:21:50PM +0200, Christian Ceelen wrote:


 sorry for the delay, I'm just having much other stuff to do <grin/>

Ok. I think i found the answer by trial and error myself. I was not able to
look up the named templates in the hash table for the (pre-) compiled

  Compilation time have so far not been something people complained about
but indeed that's quadratic behaviour there !

So i followed Nick's suggest and came up with this first draft:

  That looks mostly fine, but how do one download an unified patch from github
without having to clone the whole damn thing ? There is nothing in the UI
to download from the patch:

Did I missed it ?
Please provide the patch as an attachment to the mail, that's the simplest.

I tested locally and didn't get any surprises. I also created a simple test
with 2 named templates that have the same name to test for collision
detection. The new code behaves in that case as the previous one. But so
far I have no idea yet where and how to add it to the tests in the test
suite as this is a test for failure detection.

Looking at a second glance at the imports.c and xsltFindTemplate i think it
would be worthwhile to add the new function i created for lookup in the
hash table in the file imports.c and try to encapsulate the behavior there.
Do you think i should refactor the code in that direction?

  Don't think it's needed at this point.



Best regards,


On Thu, Aug 20, 2015 at 10:28 AM, Christian Ceelen <
christian ceelen gmail com> wrote:

Hi Nick,

Thank you very much for the answer. That sounds like a very good idea. Yet
would the validation still be correct, if the hashtable is local to the
stylesheet in which the template was defined? I was wondering what would
happen if the same template name is defined in two files, where one of the
files then imports or includes the other. Concerning the imports i think
the standard is clear, the defined template has lower preference, so having
two with the same name sounds legit to me. But what happens when the file
is included?
My current understanding is that real validation requires to walk the
include tree for each template name. Would that be correctly replicating
the existing behavior?

Btw. In xsltInernals.h:L1514 i found in struct _xsltStylesheet:
void *templatesHash;
Is this table already containing what we want?

Best regards,


On Wed, Aug 19, 2015 at 1:00 PM, Nick Wellnhofer <wellnhofer aevum de>

On 19/08/2015 10:47, Christian Ceelen wrote:

At the moment i do not have a deep understanding of the libXSLT code. My
current guess is, that this point at which the template name is
validated to
be unique in the stylesheet. The current algorithm seems to be walking
linearly through the list of all already created templates and is
the name with each. Given that the compilation process is walking
through all
templates this loop means that we have an O(n^2) algorithm (with n being
number of template instances in the stylesheet to compile).
The huge number of templates in my XSLTs are just so far over the edge,
the compilation takes 35s. I ran a test in which i skipped the loop. This
reduced the compilation time to below 2.5 s.

Would anyone let me know if i have understood the code? What can i do to
improve the code that would get easily accepted and released? I am open
to any
kind of suggestions on what to do to speed this validation step up with
a data
structure or mechanism already existing ?

Yes, template names are verified by searching a linked list which is
O(n^2). Template lookup by name uses the same list:

It shouldn't be too hard to change the code to use an xmlHashTable:

Simply add a the hash table to struct _xsltStylesheet

add some initialization and cleanup, then use xmlHashAddEntry2 and
xmlHashLookup2 with the template's name and namespace URI. This should make
name verification O(n) overall and lookup of a single template by name O(1).

What is now the developer or working repository for libxslt?
I found the git repository on <>, the
GNOME/libxslt on github, plus several forks which seem to be working
Can you point me please to the repo against which i should use for
investigation or patches?

The official repo is the one at


xslt mailing list, project page
xslt gnome org

xslt mailing list, project page
xslt gnome org

Daniel Veillard      | Open Source and Standards, Red Hat
veillard redhat com  | libxml Gnome XML XSLT toolkit | virtualization library

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