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(at)svana(dot)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