Re: qsort (was Re: Solaris)

On Wed, Apr 30, 2003 at 01:26:05PM +1200, Mark Kirkwood wrote:
> So for the many equal keys, BSD qsort is significantly faster.
>
> Clearly there are other test scenarios to examine, but the many equal
> keys case is important.

I just whipped up a really simply test package (attached, 3KB). Just unpack
it and run make. Anyway, on a Debian Woody machine here I get:

10^6 items, mod = 100

Value (i = index)       BSD      GLIBC (seconds)
random() * mod          1.58     2.29
i % mod                 0.52     1.69
i / (ITEMS / mod)       0.38     1.09
i ^ 0x5555555           1.18     1.67

It would seem to support the theory that the BSD qsort is faster than the
Glibc one. The results seem quite repeatable (repeats give +/- 5%).
--
Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
> "the West won the world not by the superiority of its ideas or values or
> religion but rather by its superiority in applying organized violence.
> Westerners often forget this fact, non-Westerners never do."
>   - Samuel P. Huntington