Boost logo

Boost :

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.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk