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

[Luke Lonergan]

Neil,

On 12/9/05 2:59 AM, "Neil Conway" <neilc at samurai.com> wrote:

> 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 :)

Yes, though there is a precedent set already with the substitution of the
BSD qsort in for Solaris.

I liked the suggestion from the 2003 Hackers thread to implement a
"--with-qsort" option to configure.

At this point, qsortG would be a possible substitute for the NetBSD version
already in the Postgres build.
 
> 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...

Yuck.  10x slower than it should be.

> See also prior discussion here:
> 
> http://archives.postgresql.org/pgsql-general/2003-04/msg01505.php

Thanks!

- Luke