Re: [boost] Integer sorting

Subject: Re: [boost] Integer sorting
From: Steven Ross (spreadsort_at_[hidden])
Date: 2019-02-12 03:50:20

On Sat, Feb 9, 2019 at 11:45 PM degski via Boost <boost_at_[hidden]> wrote:
>
> On Sat, 9 Feb 2019 at 14:39, Francisco José Tapia via Boost <
> boost_at_[hidden]> 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.hpp
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