Re: [boost] [sort] Re: [review] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 19

Subject: Re: [boost] [sort] Re: [review] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 19
From: Steven Ross (spreadsort_at_[hidden])
Date: 2014-11-12 00:02:45

Jeremy,

On Mon Nov 10 2014 at 9:02:57 AM Jeremy Murphy <
jeremy.william.murphy_at_[hidden]> wrote:

> You could always compare against my implementation of LSD radix sort:
>
> https://github.com/jeremy-murphy/algorithm/tree/speed_test
>
> It's very 'by the book'.
>
> I haven't really looked at yours or my code for a while but I just posted
> my raw speed test results for the purpose of this discussion -- the
> formatting didn't work out too well but I hope you'll be able to follow
> it.  Hope it is of some use.
>
> That's a nice and fast lsd radix sort (faster on some distributions than
my integer_sort, slower on others).  I instantiated it like this in my
sample.cpp:
else if (lsd) {
      vector<DATA_TYPE> B(array);
      stable_radix_sort(B.begin(), B.end(), array.begin());
}

Some notes:
When I feed std::sort and integer_sort 800MB of integers generated by the
randomgen example program, they use 800MB of RAM.  When I feed that same
list of integers into your stable_radix_sort, it uses 3GB!  Before that I
tried 2GB of integers, and my 8GB Ubuntu system started swapping and hung.
I understand using 2X the RAM because it's keeping a copy, but I don't
understand why an LSD radix sort should need any more than 2X the RAM.

My proposed library would probably run faster if I used a full copy of the
RAM too, and copied the data directly instead of using a complex swap loop
(I could also make it stable at some cost in speed).  The downside is the
increased RAM usage.

As another note, it appears that your function only supports unsigned
sorting.  You may want to support signed sorting.

As stated in the documentation, I think an LSD radix sort is a reasonable
addition to the library, though I'm not sure it's a necessity.