Re: [boost] [sort] pdqsort

Subject: Re: [boost] [sort] pdqsort
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2017-01-13 14:50:35

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

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

2017-01-13 19:49 GMT+01:00 Steven Ross <spreadsort_at_[hidden]>:

> 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
>