On Thu, Jan 19, 2017 at 11:12 AM Ion Gaztañaga
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?
It's Orson Peters, so I think he's the author.
Best,
Ion
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost