Re: [boost] [sort] pdqsort

Subject: Re: [boost] [sort] pdqsort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2017-01-13 15:36:05

On Fri, Jan 13, 2017 at 2:51 PM Francisco José Tapia <fjtapia_at_[hidden]>
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 <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
> >
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>