Re: [boost] [sort] pdqsort

Subject: Re: [boost] [sort] pdqsort
From: Orson Peters (orsonpeters_at_[hidden])
Date: 2017-01-26 17:33:51

Hi, Orson here, I'm the original author of pdqsort.

As discussed in this long github issue (
https://github.com/boostorg/sort/issues/11), I have full copyright on the
pdqsort implementation (which is freely available under the zlib license on
https://github.com/orlp/pdqsort), and am willing to provide it to Boost
free of charge under the Boost license.

@Marc Glisse, since your 2015 experiment the code has changed, and pdqsort
now uses a technique called block quicksort. It's substantially faster for
branchless comparisons (50-80%), but it seems that on some systems it also
give significant (5-15%) slowdowns for branchful code.

I will revert pdqsort's default implementation to the old version, except
when the passed in type is built-in, and the comparison operator is
std::less / std::greater, then I will use the branchless code. I will
provide the branchless code explicitly as well, under a different function
name, for experienced users that know their comparison function is
branchless. The old implementation was never slower than std::sort in my
experiments, for the record.

If any of you have further questions, please do let me know.