Re: Re: Which qsort is used

Martin,

On 12/19/05 3:37 AM, "Martijn van Oosterhout" <kleptog(at)svana(dot)org> wrote:

> I'm not sure whether we have a conclusion here, but I do have one
> question: is there a significant difference in the number of times the
> comparison routines are called? Comparisons in PostgreSQL are fairly
> expensive given the fmgr overhead and when comparing tuples it's even
> worse.

It would be interesting to note the comparison count of the different
routines.

Something that really grabbed me about the results though is that the
relative performance of the routines dramatically shifted when the indirect
references in the comparators went in. The first test I did sorted an array
of int4 - these tests that Qingqing did sorted arrays using an indirect
pointer list, at which point the same distributions performed very
differently.

I suspect that it is the number of comparisons that caused this, and further
that the indirection has disabled the compiler optimizations for memory
prefetch and other things that it could normally recognize. Given the usage
pattern in Postgres, where sorted things are a mix of strings and intrinsic
types, I'm not sure those optimizations could be done by one routine.

I haven't verified this, but it certainly seems that the NetBSD routine is
the overall winner for the type of use that Postgres has (sorting the using
a pointer list).

- Luke