08/19/05 Ben Maurer wrote:
If we really wanted performance, we could do an icall here. The libc qsort
is hyper-optimized. IMH, there is no way we could compete, especially for
large arrays. Feel free to benchmark and prove me wrong though.

What if, for a change, _you_ write a benchmark and get some data before
making a claim?

Hint: qsort does a call for each compare.
Hint2: qsort likely does a memcpy() or a switch on size on each swap.
Hint3: qsort doesn't support a custom swap callback as is needed in the
API.
Hint4: if a compare method is provided, handing it over to libc's qsort
means doing an unmanaged->managed transition for each compare, ouch.
Hint5: often the arrays sizes to compare are small and the transition
costs dominate the performance if you use an icall.

As a data point, for int[] sorts, the current combsort code is faster
than a pure C program that calls qsort (so avoiding a lot of overhead) up
to 100 K elements, sometimes by as much as 2 times faster. It is just as
fast up to more than 300 K elements if jit optimizations are enabled
(=all).
But, hey, the perl script I used to generate the random numbers
for testing may have generated the right optimial sequence for the
combosrt used in corlib.

lupus