Jeremy, On Mon Nov 10 2014 at 9:02:57 AM Jeremy Murphy < jeremy.william.murphy@gmail.com> 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
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.