[boost] [sort] pdqsort

Subject: [boost] [sort] pdqsort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2017-01-13 13:49:22

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.

Does anyone have a strong preference, advice, or comments on how they use
Boost.Sort?

Should I run a mini-review for pdqsort?