Re: [boost] [sort] pdqsort

Subject: Re: [boost] [sort] pdqsort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2017-01-24 20:09:18

On Thu, Jan 19, 2017 at 11:12 AM Ion Gaztañaga <igaztanaga_at_[hidden]> wrote:

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