Re: [xml] xmlXPathNodeSetSort performance

[Stefan Behnel <stefan_ml behnel de>]

Vojtech Fried, 25.07.2012 17:45:
> Second version of Timsort patch, slightly more polished. It builds on my
> gcc, I have fixed some warnings and merged the two headers into one. I
> did not move the code to .c file though, because the sort implementation
> uses some macro magic, i.e. the functions you see in the code are really
> function "templates" and they are "instantiated" with the name and type
> you choose with the macros (basically it is a poor man's C++ template
> system :-). I could remove the macros and specialize the functions for
> libxml xmlNodePtr, but that seems quite ugly to me.

What about moving it all into a .c file, then adding a new entry point at
the end that specialises the preceding code for the exact use case in xpath.c?

Thanks for doing this, BTW, the node set sorting performance is a huge
problem. Not only for very large lists of nodes, but also for multi-step
XPath expressions, which currently result in multiple sorting and
re-sorting steps.

Note that node comparison can be very costly, so another thing to
investigate would be to add a flag to the node set struct that remembers if
it's sorted already. That would allow the sort algorithm to skip to the
merging step directly, instead of traversing the whole node list first.

Stefan