Re: [xml] xmlXPathNodeSetSort performance

[Vojtech Fried <vfried opentext com>]

>  Okay, out of curiosity what's the maximum amount of nodes in the nodeset you are ever hitting ?

Well, it is hard to say. It is a moving target. Basically our users try as many nodes as they can and if they 
need too many (it takes too much time to process), they can split the input for our app and merge the results 
our app produces, but that complicates things for them. Anyway, 10k is not exceptional, 100k is probably 
maximum anyone tried to use.

> Yeah we would need more polishing. I dislike the idea of having code in a .h even though i understand that 
> as a trial approach it's easier for testing :-)

Ok, I will move the code to .c file. But I am not sure about libxml coding standards. Should I assimilate the 
code in this way or rather leave it as is, because it would be easier to track the changes made by the 
original authors?

> Err You mean that Timsort need to duplicate the nodelist somehow instead of working directly on the given 
> list, because overall I don't know data structures which are O(1) (but i would have a good business model 
> if you got one :-) . Basically doubling the list memory requirement doesn't sounds a big deal I agree.

Yes, it is a memory needed in addition to the input. My understanding is that O(n) for Timsort means doubling 
the list memory (in the same way as in Mergesort) and O(1) for Smoothsort means that it works inplace plus 
some constant sized bookkeeping. But I haven't studied it in detail.

Vojtech