[Bizgres-general] Slow glibc qsort, two versions that are much faster

[Neil Conway]

On Fri, 2005-12-09 at 00:10 -0800, Luke Lonergan wrote:
> I found the routine "qsortG" here:
>   http://homepage.ntlworld.com/g.mccaughan/software/qsort.c-1.12
> 
> In my tests (attached, and results below), the qsortG routine outperforms
> the Linux/qlibc qsort routine by as much as 94% (10 times).  It's different
> on Mac OSX and Solaris where the zero set seems to have a fast
> implementation.

If we're not exploiting domain-specific knowledge about the data we're
sorting, I think we (Postgres, at least) should be reluctant to
second-guess the vendor's qsort(3) implementation. The libc
implementation *should* be as fast as a general-purpose sort can be, and
has the potential to take advantage of hardware and platform-specific
optimizations that we wouldn't want to implement or maintain ourselves.
If your vendor's libc implementation sucks, complain to your vendor :)

As for glibc's qsort(3), it seems to actually be implemented via merge
sort, so the performance difference doesn't surprise me. I do find it a
surprising that glibc are using merge sort, though...

See also prior discussion here:

http://archives.postgresql.org/pgsql-general/2003-04/msg01505.php

-Neil