On 10/7/2011 2:27 PM, Ellery Newcomer wrote:
tinkered with timsort a bit a few months ago. comparing that to your
sort, I get numbers like
xinokSort
random: 77 ascending: 0 descending: 21
timsort
random: 354 ascending: 1 descending: 4
where each are sorting a 500k element array of int, times are msecs,
compilation flags were -O -inline -release, sources are
http://personal.utulsa.edu/~ellery-newcomer/timsort.d
http://personal.utulsa.edu/~ellery-newcomer/xinokSort.d
Nice job, Xinok.
anyone want to try to optimize my timsort? :)
The benchmark for descending is no surprise since timsort explicitly
searches for runs in descending order. However, the random benchmark
isn't what I expected. My sort is a bit slower than a standard merge
sort, so I would expect Timsort to be faster.
While part of the reason may be your code is unoptimized, it may also be
the fault of a bug. I ran some more benchmarks and I found a few cases
where your code failed, specifically when the data is mostly random.
Just a guess, but your code may have a problem when the "runs" are too
small.
I also found a case when std.algorithm.sort performs poorly, under Small
Shuffle + Descending.
Numbers represent time taken; Smaller numbers are faster
An MD5 hash is generated for each sort, to verify it was sorted correctly
phoboSort is unstable std.algorithm.sort
Ascending
Is length: 16777216
xinokSort: 50722 C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 726046 C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 943475 C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 1778944 C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 3082901 C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 955285 C8B8D3A2B4D9882ABCFC31721EF27145
tim Sort: 89201 C8B8D3A2B4D9882ABCFC31721EF27145
Descending
Is length: 16777216
xinokSort: 1916452 C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 2238446 C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 1581095 C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 3390033 C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 3067271 C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 1035827 C8B8D3A2B4D9882ABCFC31721EF27145
tim Sort: 240896 C8B8D3A2B4D9882ABCFC31721EF27145
Complete Shuffle
Is length: 16777216
xinokSort: 7607511 C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 8814887 C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 5623837 C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 6704733 C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 2825567 C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 5532275 C8B8D3A2B4D9882ABCFC31721EF27145
tim Sort: 29142913 E03C4778321F69D8AD10F624E6093599
Small Shuffle (1024 pairs were picked at random and swapped)
Is length: 16777216
xinokSort: 589882 C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 3651222 C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 2655391 C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 2162840 C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 2988630 C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 963103 C8B8D3A2B4D9882ABCFC31721EF27145
tim Sort: 6523251 C8B8D3A2B4D9882ABCFC31721EF27145
Large Shuffle (1,048,576 pairs were picked at random and swapped)
Is length: 16777216
xinokSort: 1956126 C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 7617207 C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 3089674 C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 2606200 C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 2932306 C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 1619484 C8B8D3A2B4D9882ABCFC31721EF27145
tim Sort: 14883251 DE54E94D1A058459FEA3A80096FCBB18
Small Shuffle + Descending
Is length: 16777216
xinokSort: 2288869 C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 4599417 C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 2604222 C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 3457241 C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 3055080 C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 261768564 C8B8D3A2B4D9882ABCFC31721EF27145
tim Sort: 10149160 C8B8D3A2B4D9882ABCFC31721EF27145
Large Shuffle + Descending
xinokSort: 2923813 C8B8D3A2B4D9882ABCFC31721EF27145
shellSort: 7678966 C8B8D3A2B4D9882ABCFC31721EF27145
quickSort: 3833138 C8B8D3A2B4D9882ABCFC31721EF27145
mergeSort: 3971124 C8B8D3A2B4D9882ABCFC31721EF27145
radixSort: 2941206 C8B8D3A2B4D9882ABCFC31721EF27145
phoboSort: 3749512 C8B8D3A2B4D9882ABCFC31721EF27145
tim Sort: 22709918 191BD30B3D0E52C922A7E6A16E5E63A5
