[Mono-dev] [Patch] Generic Array.Sort

Paolo Molaro lupus at ximian.com
Sat Aug 20 09:27:13 EDT 2005


On 08/19/05 Ben Maurer wrote:
> If we really wanted performance, we could do an icall here. The libc qsort
> is hyper-optimized. IMHO, 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
(-O=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

-- 
-----------------------------------------------------------------
lupus at debian.org                                     debian/rules
lupus at ximian.com                             Monkeys do it better



More information about the Mono-devel-list mailing list