[Mono-dev] Possible QuickSort optimizations for Array.Sort()

[Jeffrey Stedfast]

On 04/09/2011 04:39 PM, Jeff Stedfast wrote:
> On 04/06/2011 03:18 AM, Marek Safar wrote:
>> Hello,
>>
>> >>>
>> 	public class Sort<T>  {
>> 		public delegate int Comparison (T v0, T v1);
>>
>> You don't need yet another delegate, just use standard Func
>>
>> >>
>> 		static readonly int INSERTIONSORT_THRESHOLD = 7;
>>
>> Why not to used const int ?
>>
>> More importantly what is performance of sorting array of 10-20 
>> elements called 1000000 times ?
>>
>
> Attached is another test program with 2 newer/faster implementations 
> of QuickSort, one of which is Non-Recursive.
>
> You can run this program like so:
>
> mono ./qsort.exe [-random, -sorted, -reversed] [array size] [# loops]
>
> These 2 new implementations manage to reduce the number of comparisons 
> done by merging the Median() function from the previous set into the 
> main body of the QuickSort function and swapping those 3 elements into 
> ascending order as it compares to find the optimal pivot. This has the 
> advantage of allowing our loops to start at low+1 and high-1 (thus 
> reducing our compares by 2 for each partition).
>
> My previous implementation was able to reduce the compares by 1 by 
> starting at low+1 by moving the pivot into low, but this has the 
> negative impact of destroying performance on reverse-sorted arrays. My 
> new implementation doesn't have this problem (and therefore, we don't 
> need to fall back to that insertion-sort if we detect that 
> pathological case).
>
> Interestingly, the NonRecursiveQuickSort() implementation does not 
> noticeably improve performance over the recursive version and in fact 
> is slower than even our current implementation for sorting small 
> arrays (made evident when looped millions of times).
>
> How do you feel about replacing corlib's qsort() implementation with 
> my FasterQuickSort() implementation?
>
> Jeff

Just to be clear, I meant "how do you feel about *me* doing the work to 
replace the current QuickSort impl in corlib with mine?" :-)

I just want to make sure before I create a patch that people are interested.

That said, I forgot to include benchmark results:

[fejj at serenity sorting]$ mono ./qsort.exe -random 10 10000000
BasicQuickSort comparisons needed:     430000000
FasterQuickSort comparisons needed:    250000000
BasicQuickSort finished in:            00:00:18.8535031s
FasterQuickSort finished in:           00:00:16.4478594s

[fejj at serenity sorting]$ mono ./qsort.exe -sorted 10 10000000
BasicQuickSort comparisons needed:     330000000
FasterQuickSort comparisons needed:    180000000
BasicQuickSort finished in:            00:00:16.9532771s
FasterQuickSort finished in:           00:00:14.1202212s

[fejj at serenity sorting]$ mono ./qsort.exe -reversed 10 10000000
BasicQuickSort comparisons needed:     360000000
FasterQuickSort comparisons needed:    180000000
BasicQuickSort finished in:            00:00:17.4450895s
FasterQuickSort finished in:           00:00:15.1590930s


Jeff

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20110410/2e58b55d/attachment.html