Faster sort?

[Andrea Fontana via Digitalmars-d]

On Wednesday, 6 April 2016 at 18:54:08 UTC, tsbockman wrote:
> On Wednesday, 6 April 2016 at 08:15:39 UTC, Andrea Fontana 
> wrote:
>> Using ldmd2 -O -release -noboundscheck -inline sort.d && ./sort
>>  instead:
>>
>> 2 inputs:
>> Faster: 0 hnsecs
>> Phobos: 33 μs and 5 hnsecs
>>
>> ...
>>
>> 65536 inputs:
>> Faster: 0 hnsecs (???)
>> Phobos: 7 secs, 865 ms, 450 μs, and 6 hnsecs
>
> Can you share the benchmark code?
>
> "0 hnsecs" results generally mean that your test was too simple 
> and/or didn't have any obvious side effects, and so the 
> optimizer just removed it completely.

A simple test just written:

    Duration total;

    foreach(_; 0..10000)
    {
       auto arr = generate!( () => uniform(0,2)).map!(x => 
cast(bool)x).take(65536).array;
       StopWatch sw;
       sw.start;
       boolSort(arr);
       total += sw.peek.to!Duration;
       sw.stop;

    }


andrea at ububocs:/tmp$ ./sort
0 hnsecs

I don't think compiler can remove a random generated array...
I think times are too small to be measured with a good accuracy, 
using start() stop() to resume stopwatch seems to add a (fixed) 
overhead (some microsecs over the 10000 cycles) that doesn't 
depend on size of array tested.
Anyway, it doesn't matter if it is 0 hnsec or some microsecs, in 
my opinion. It's still faster and faster than original sort (of 
course it's n vs n*log(n)). Here the same code with "sort(arr)" 
instead of "boolSort(arr)":

andrea at ububocs:/tmp$ ./sort
10 secs, 620 ms, 414 μs, and 2 hnsecs

Andrea