On 10/17/12 3:07 PM, Philippe Sigaud wrote:
On Mon, Oct 15, 2012 at 5:52 PM, Andrei Alexandrescu
<seewebsiteforem...@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
