Re: [boost] [sort] pdqsort

Subject: Re: [boost] [sort] pdqsort
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2017-01-19 11:11:42

On 13/01/2017 19:49, Steven Ross wrote:
> I've been reviewing a proposed addition to Boost.Sort called pdqsort.  When
> using a general-case partitioning algorithm, it performs comparably to
> std::sort in my testing (Windows and Linux).  When used as a replacement
> for the std::sort fallback in spreadsort, using a branch-reducing
> optimization it is ~20% faster on ints and floats, and ~40% slower on
> strings.  The concerning part is that any comparison operator that involves
> a branch may have a comparable slowdown to the string case.
> pdqsort is also significantly faster than std::sort on mostly-sorted data
> and some other (relatively common) special cases.  This makes little
> difference when used as a fallback by spreadsort, but does make a
> difference when used on its own.
>
> I see these possible things to do with pdqsort:
> 1) Reject it completely as too similar to std::sort, which is already
> highly optimized.
> 2) Add it as another optional library in the Boost.Sort library.
> 3) Add it to Boost.Sort, and only use it as a fallback for ints and floats.
> 4) Add it to Boost.Sort, use it as a fallback for all of spreadsort, and
> have pdqsort itself only use its branch-reduction optimization on ints and
> floats.
> 5) #4, except eliminate the branch-reduction optimization completely from
> pdqsort for simplicity.

I'd be interested in having Boost-licensed quicksort-like algorithm. In 
some containers supporting C++03 I need a move-emulation enabled 
implementation. If the general-purpose algorithm is not suitable for 
Boost.Sort, then I'd add it as an implementation detail in Boost.Move.

Is the original author proposing an implementation with a Boost license 
or someone has rewritten the algorithm based on the paper?

Best,

Ion