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

[Luke Lonergan]

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.

I'm not sure how much this matters to us, as qsort is likely only used by
Postgres for in-memory sorts, though it might be (haven't looked) used
within the N-tape algorithm for disk sorts.

I've also included the results for the NetBSD version of qsort for
comparison, as it is the version included with Postgres.

Following are the results of the tests:

===========================================
Linux 32 bit (owl):
===========================================
owl-~/SORT_TEST> ./sort
Random set qsort, qsortBSD, qsortG 533834us, 519890us, 342757us
Reverse set qsort, qsortBSD, qsortG 366743us, 161585us, 34921us
Zero set qsort, qsortBSD, qsortG 244599us, 12845us, 189819us
NetBSD qsort results:
Random set: qsortBSD / qsort is 2.61% faster.
Reverse set: qsortBSD / qsort is 55.94% faster.
Zero set: qsortBSD / qsort is 94.75% faster.
qsortG results:
Random set: qsortG / qsort is 35.79% faster.
Reverse set: qsortG / qsort is 90.48% faster.
Zero set: qsortG / qsort is 22.40% faster.

===========================================
Linux 64 bit (stinger4):
===========================================
[llonergan at stinger4 SORT_TEST]$ ./sort
Random set qsort, qsortBSD, qsortG 679718us, 633202us, 233498us
Reverse set qsort, qsortBSD, qsortG 375535us, 210715us, 20931us
Zero set qsort, qsortBSD, qsortG 328409us, 22998us, 113902us
NetBSD qsort results:
Random set: qsortBSD / qsort is 6.84% faster.
Reverse set: qsortBSD / qsort is 43.89% faster.
Zero set: qsortBSD / qsort is 93.00% faster.
qsortG results:
Random set: qsortG / qsort is 65.65% faster.
Reverse set: qsortG / qsort is 94.43% faster.
Zero set: qsortG / qsort is 65.32% faster.

===========================================
Solaris 64 bit (stinger1):
===========================================
-bash-3.00$ ./sort
Random set qsort, qsortBSD, qsortG 235163us, 235387us, 240901us
Reverse set qsort, qsortBSD, qsortG 226373us, 177903us, 26724us
Zero set qsort, qsortBSD, qsortG 12461us, 23892us, 143019us
NetBSD qsort results:
Random set: qsortBSD / qsort is -0.10% faster.
Reverse set: qsortBSD / qsort is 21.41% faster.
Zero set: qsortBSD / qsort is -91.73% faster.
qsortG results:
Random set: qsortG / qsort is -2.44% faster.
Reverse set: qsortG / qsort is 88.19% faster.
Zero set: qsortG / qsort is -1047.73% faster.

===========================================
Mac OSX 32 bit:
===========================================
Luke-Lonergans-Computer:~/SORT_TEST lukelonergan$ ./sort
Random set qsort, qsortBSD, qsortG 556773us, 541841us, 500603us
Reverse set qsort, qsortBSD, qsortG 118568us, 117643us, 77637us
Zero set qsort, qsortBSD, qsortG 35123us, 34105us, 365932us
NetBSD qsort results:
Random set: qsortBSD / qsort is 2.68% faster.
Reverse set: qsortBSD / qsort is 0.78% faster.
Zero set: qsortBSD / qsort is 2.90% faster.
qsortG results:
Random set: qsortG / qsort is 10.09% faster.
Reverse set: qsortG / qsort is 34.52% faster.
Zero set: qsortG / qsort is -941.86% faster.



-------------- next part --------------
A non-text attachment was scrubbed...
Name: SORT_TEST.tgz
Type: application/octet-stream
Size: 8282 bytes
Desc: not available
Url : http://pgfoundry.org/pipermail/bizgres-general/attachments/20051209/75718765/SORT_TEST.obj