Re: [xslt] slow key lookup in libxslt-1.1.22

[Daniel Veillard <veillard redhat com>]

On Sun, Dec 23, 2007 at 05:27:42PM -0800, William M. Brack wrote:
> > About 30 times slower. The profiles (and experimenting) suggest a
> > bottleneck in a key lookup in the "abs" function, which basically
> > just
> > takes a name of a key $k (one letter code) and looks up an element
> > using
> > its number $nr: "key($k,$nr)".
> >
> > Any ideas what might be going on?
> >
> > Thanks a lot,
> > Josef Urban
> 
> I spent quite a bit of time debugging this problem, including
> low-level (gcc / gprof) profiling of both libxslt and libxml2, and I
> think I have found and fixed it.
> 
> Since libxslt-1.1.15, there were many enhancements made to libxslt
> (and libxml2), mostly aiming to increase efficiency, but also fixing
> some problems.  The version which introduced this trouble was
> libxslt-1.1.17 (released in June 2006), when it was decided to only
> initialize "keys" for a document at the time they were first used. 
> Unfortunately, there was a bug in the new code which resulted in the
> problem you encountered.  Instead of only initializing the keys
> once, with your stylesheet they were being "initialized" a very
> large number of times!
> 
> My fixes are in SVN, and I would greatly appreciate it if you could
> try them and confirm that everything is now okay.  According to my
> tests, when compared to xsltproc from 1.1.15 the SVN version has a
> 16% improvement in "real" time, 5% improvement in "system", and 19%
> in "user" :-).

  Users reported breakages in key usages for libxslt-1.1.23,
and I found 2 problems with the new code:
   - the key number computation was done after variable initialization,
     which broke global variables if they were using keys, swapping
     the 2 lines were a trivial fix
   - far harder, the code broke when key A depended on key B and 
     B was in the list after A

 for the second I modified the code to call first the new routine computing
all keys for the local document, but keeping in the transformation block
the fact we were initializing keys, and if a key table is missing then
initilize just that table (the counter is then used to count the recursion
level, making trivial to detect and abort if keys are defined recursively).
I refactored the code a bit, this is now in SVN head :-)

Daniel

-- 
Red Hat Virtualization group http://redhat.com/virtualization/
Daniel Veillard      | virtualization library  http://libvirt.org/
veillard redhat com  | libxml GNOME XML XSLT toolkit  http://xmlsoft.org/
http://veillard.com/ | Rpmfind RPM search engine  http://rpmfind.net/