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 Size 9, network: 53.98, std.algorithm.sort: 75.54, ratio network/std.algo: 0.71 Size 10, network: 46.66, std.algorithm.sort: 81.68, ratio network/std.algo: 0.57 Size 11, network: 65.06, std.algorithm.sort: 111.25, ratio network/std.algo: 0.58 Size 12, network: 66.31, std.algorithm.sort: 109.40, ratio network/std.algo: 0.61 Size 13, network: 74.84, std.algorithm.sort: 115.94, ratio network/std.algo: 0.65 Size 14, network: 90.05, std.algorithm.sort: 131.84, ratio network/std.algo: 0.68 Size 15, network: 95.23, std.algorithm.sort: 145.31, ratio network/std.algo: 0.66 Size 16, network: 104.66, std.algorithm.sort: 162.84, ratio network/std.algo: 0.64 Size 17, network: 125.30, std.algorithm.sort: 167.49, ratio network/std.algo: 0.75 Size 18, network: 133.10, std.algorithm.sort: 182.20, ratio network/std.algo: 0.73 Size 19, network: 143.92, std.algorithm.sort: 195.58, ratio network/std.algo: 0.74 Size 20, network: 155.01, std.algorithm.sort: 211.59, ratio network/std.algo: 0.73 Size 21, network: 171.43, std.algorithm.sort: 224.47, ratio network/std.algo: 0.76 Size 22, network: 177.46, std.algorithm.sort: 236.92, ratio network/std.algo: 0.75 Size 23, network: 192.22, std.algorithm.sort: 253.38, ratio network/std.algo: 0.76 Size 24, network: 205.39, std.algorithm.sort: 270.83, ratio network/std.algo: 0.76 Size 25, network: 213.25, std.algorithm.sort: 281.01, ratio network/std.algo: 0.76 Size 26, network: 233.96, std.algorithm.sort: 283.57, ratio network/std.algo: 0.83 Size 27, network: 246.73, std.algorithm.sort: 297.67, ratio network/std.algo: 0.83 Size 28, network: 260.41, std.algorithm.sort: 313.88, ratio network/std.algo: 0.83 Size 29, network: 280.06, std.algorithm.sort: 321.01, ratio network/std.algo: 0.87 Size 30, network: 298.65, std.algorithm.sort: 342.55, ratio network/std.algo: 0.87 Size 31, network: 308.09, std.algorithm.sort: 355.70, ratio network/std.algo: 0.87 Size 32, network: 323.89, std.algorithm.sort: 380.31, ratio network/std.algo: 0.85 On the computers I tested it (Windows, Linux, different machines), the cutoff is at about 35-38 elements.
