Re: [boost] [sort] pdqsort

On Fri, Jan 13, 2017 at 2:51 PM Francisco José Tapia wrote:

Do you have any description of the algorithm ? Where can find an implementation of it ?

Library with Boost license: https://gist.github.com/orlp/2c417ab76391b126e1d58bac4bf4af0f Repository: https://github.com/orlp/pdqsort Paper: https://drive.google.com/file/d/0B1-vl-dPgKm_T0Fxeno1a0lGT0E/view

I will examine, and say my opinion as soon as possible

2017-01-13 19:49 GMT+01:00 Steven Ross :

...

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?

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost