On Sat, Feb 9, 2019 at 11:45 PM degski via Boost
On Sat, 9 Feb 2019 at 14:39, Francisco José Tapia via Boost < boost@lists.boost.org> wrote:
The results con ska_sort are in the attached file numbers_02.txt
Thanks for adding this [and it was worthwhile I would say], this is a great table and shows ska_sort is weak on sorted data [maybe that's fixable], but otherwise better than [Boost] Spreadsort and Fastest-Integer-Sort [sic] and overall fastest on random data.
I say you the same things as Fenil. This is an external test of the
algorithm. The internal test is other question very different ...
I don't understand why the "internal test" [unless you mean testing for bugs] has any relevance.
It looks like ska_sort is a radix sort designed mostly for the best-case, and that if you feed it the alrbreaker or binaryalrbreaker distributions it will perform poorly (though not as poorly as radix implementations with no fallback or that fallback to insertionsort). There might be some counting and swapping optimizations here to copy into spreadsort (I see block operations), though those might not work if the items being sorted are references or pointers. Mostly-sorted data is a common case to take seriously, and it took only modest tweaking of spreadsort to do well there. Based on Francisco's numbers, I should retune spreadsort to take advantage of the higher speed of pdqsort vs std::sort, at least if I want to optimize for 64-bit integer sorting on modern processors. https://www.boost.org/doc/libs/1_67_0/boost/sort/spreadsort/detail/constants... A higher log_min_split_count (especially) and log_finishing_count is probably appropriate.
degski PS: Please don't top-post, it's just so messy. -- *“If something cannot go on forever, it will stop" - Herbert Stein*
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost