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
