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

[Daniel Veillard <veillard redhat com>]

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

  Hi,

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

  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:
>    https://github.com/GNOME/libxslt/pull/1

  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:

  https://github.com/cceelen/libxslt/commit/f7b4c8d436d187e27ab099ac652e56bdcdca66af?diff=unified

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.

  thanks,

Daniel

> Best regards,
>
> Christian
>
> 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,
> >
> > Christian
> >
> > On Wed, Aug 19, 2015 at 1:00 PM, Nick Wellnhofer <wellnhofer aevum de>
> > wrote:
> >
> > > 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
> > >
> > > _______________________________________________
> > > xslt mailing list, project page http://xmlsoft.org/XSLT/
> > > xslt gnome org
> > > https://mail.gnome.org/mailman/listinfo/xslt

> _______________________________________________
> xslt mailing list, project page http://xmlsoft.org/XSLT/
> xslt gnome org
> https://mail.gnome.org/mailman/listinfo/xslt


-- 
Daniel Veillard      | Open Source and Standards, Red Hat
veillard redhat com  | libxml Gnome XML XSLT toolkit  http://xmlsoft.org/
http://veillard.com/ | virtualization library  http://libvirt.org/