Re: XSLT compilation is slow for big XSLTs

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 comparing
> 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 the
> number of template instances in the stylesheet to compile).
> The huge number of templates in my XSLTs are just so far over the edge, that
> 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:

     https://github.com/GNOME/libxslt/blob/master/libxslt/imports.c#L375

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

     https://github.com/GNOME/libxml2/blob/master/include/libxml/hash.h

Simply add a the hash table to struct _xsltStylesheet

     https://github.com/GNOME/libxslt/blob/master/libxslt/xsltInternals.h#L1509

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 git.gnome.org <http://git.gnome.org>, the
> GNOME/libxslt on github, plus several forks which seem to be working repos.
> Can you point me please to the repo against which i should use for further
> investigation or patches?

The official repo is the one at git.gnome.org:

     https://git.gnome.org/browse/libxslt/

Nick