Porting my Integer Sorting Algorithms to D

["Nordlöw"]

On Sunday, 23 February 2014 at 15:10:36 UTC, Russel Winder wrote:
> On Sun, 2014-02-23 at 14:09 +0000, "Nordlöw" wrote:
>> I have a couple of self-implemented C++ integer sort 
>> algorithms lying around in my codebase.
>
> What is the basic sort algorithm? Radix sort is generally seen 
> as the
> best for sorting integer values currently. But that doesn't 
> mean there
> is better, just that that is the one to beat.
>
> Which requires benchmarks. Which requires a framework for 
> running
> benchmarks. As far as I am aware D hasn't got one of these as 
> yet, but
> it needs one. Such things exists in Python (I am currently 
> playing with
> benchmark) and , I am sure, other dynamic languages. It should 
> be
> relatively easy to do something with D.
> 
>> I also have a parallel merge sort on top of them that uses 
>> Intel TBB to give some
>> further speedups.
>
> std.parallelism needs some work to compete with TBB. Though I 
> am not
> sure "like" is a term I would use for the TBB API.
>
>> I have tweaked them to also work for floats and doubles, 
>> through some interesting bit-fiddling tips I found on the net.
>> 
>> Would anybody be interested in reviewing these to give 
>> suggestions on how to best port it to Phobos?
>
> I guess I just volunteered.

The non-inplace radix sort algorithm is the most interesting. I 
have a test and benchmarking suite along with it. Here's an 
extract of it using GCC 4.8.2 with -O3 settings on my Intel 
Quad-Core with 8 Hyperthreads. Results are promising. These 
benchmarks have been verfied to produce correct results:

Element Count: 1000000
Number of tries: 5
Do in place: 0
ElementType Reference(std::sort) Radix radix_sort 
descending_radix_sort parallel_radix_sort tbb_parallel_radix_sort
float    1947812us 16 4.27x 4.02x 4.87x 4.37x
double   2022670us 16 2.30x 2.09x 3.25x 2.31x
uint8_t  1673208us  8 10.4x 10.0x 9.32x 10.6x
uint16_t 1800614us 16 10.1x 9.37x 9.52x 10.1x
uint32_t 1936704us 16 5.45x 4.99x 5.77x 5.42x

Should I place the code on a Github repo or send it to you by 
email?

Thx,
Per