Porting my Integer Sorting Algorithms to D

"Nordlöw" per.nordlow at gmail.com
Sun Feb 23 08:28:21 PST 2014


On Sunday, 23 February 2014 at 16:16:48 UTC, Nordlöw wrote:
> 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

After having take a look at algorithm.d I guess we should use 
CTFE-logic to autoconfigure to use radix sort when ElementType 
isInteger or float or double. string and real could probably be 
sorted aswell.

To make this configuration optimal an optional pre-configuration 
benchmarking pass may be need in order to give optimal speeds. 
Such a pass should for each sort implementation figure out a 
suitable limit [low,high] for the size range being sorted.

/Per


More information about the Digitalmars-d mailing list