Sorting algorithms

[Andrei Alexandrescu]

On 10/17/12 3:07 PM, Philippe Sigaud wrote:
> On Mon, Oct 15, 2012 at 5:52 PM, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org>  wrote:
>
>> I wanted to investigate small sorts using sorting networks for ages, but
>> never got around to it. That's important for quicksort because it produces
>> many small arrays that need sorting.
>>
>> Could you also test for very small sizes (2 to 4) and essentially test for
>> 1-increment speed up to, say, 30 elements? I assume that's where the major
>> wins come. I think we could use CT-generated sorting networks for arrays
>> below a specific size. The converse risk is growth of generated code.
>
> Here:
>
> http://dpaste.dzfl.pl/42fac981
>
> I don't know if the benchmarking code is OK. I substract a reference
> because randomly shuffling an array takes some time.
>
> Results for my computer (smaller ratio means faster network sort
> compared to std.algorithm.sort)
>
> Size 1, network: 2.10, std.algorithm.sort: 15.86, ratio network/std.algo: 0.13
> Size 2, network: 2.23, std.algorithm.sort: 14.26, ratio network/std.algo: 0.16
> Size 3, network: 6.22, std.algorithm.sort: 20.75, ratio network/std.algo: 0.30
> Size 4, network: 8.25, std.algorithm.sort: 28.36, ratio network/std.algo: 0.29
> Size 5, network: 18.54, std.algorithm.sort: 39.02, ratio network/std.algo: 0.48
> Size 6, network: 20.12, std.algorithm.sort: 45.58, ratio network/std.algo: 0.44
> Size 7, network: 27.49, std.algorithm.sort: 55.53, ratio network/std.algo: 0.50
> Size 8, network: 33.91, std.algorithm.sort: 66.02, ratio network/std.algo: 0.51
[snip]

Looking great, thanks. I'm on the road with little time and 
connectivity, but I want to encourage you with integrating this with 
std.sort. There seems to be a big gain drop off at size 9, so we could 
use sorting networks for size <= 8. (I'm also worried about generated 
code size.) So next step would be to integrate the sorting network 
within std.sort and see how it works there.

Please don't let this good work go to waste!


Andrei