[libstdc++] pdqsort - a faster std::sort

Christopher Jefferson chris@bubblescope.net
Wed Apr 8 09:35:00 GMT 2015


I have thought for a while that std::sort could probably due with
improvements in this direction, particularly for almost-sorted data
(although std::sort is doing better than I thought it might! You still
improve by a factor of 2ish). The code is also pleasingly short.

While I don't have any sole control, I would be happy to see this
merged, under the following conditions (I reserve the right to add
more during more careful review!)


* I assume the sort works on move-only types in C++11? (I can see you
make use of move, but do you require it?).
  - There was a reason (and I can't remember what it was now!) that we
used 'iter_swap' rather than 'swap(*a,*b)' on iterators. I think it
might be required to allow sorting std::vector<bool>? Either way, it
might be worth trying it.
  - In general, try adding your code to libstdc++ (just replace
std::sort with your function), and run the test suite and see what
falls out!

* Would be nice to see benchmarks on more types (strings and deques
are two obvious candidates. Also make them reasonably long with long
equal prefixes, to make the comparison function more expensive).

Chris



On 7 April 2015 at 15:24, Orson Peters <orsonpeters@gmail.com> wrote:
> Woops, didn't intend this to be a personal reply. Forwarded email:
>
> It's not so much novel that it's hard to analyze, or anything to be
> nervous about. It's very similar
> to introsort in that it is quicksort with heuristics/optimizations
> tacked on. The combination of
> optimizations used is novel.
>
> The code with comments is only 300LOC, so even rigorous manual
> verification with pre/post conditions
> is possible.
>
> Most heuristics used are not novel, only (to my knowledge) three of
> them are, and they are trivial to
> show to be safe. I'd definitely suggest you to read the readme
> (https://github.com/orlp/pdqsort) to
> see the heuristics explained in detail.
>
> In a very brief summary, pdqsort is quicksort with the following enhancements:
>
>  - Use median of 3 pivot selection. (libstdc++ std::sort does this)
>  - Switch to insertion sort for small partitions. (libstdc++ std::sort
> does this)
>  - Put equal elements on the left unless equal to pivot, then filter.
> (qsort in glibc does this)
>  - Attempt insertion sort if partition swapped no elements. (libc++
> std::sort does this)
>  - Only attempt above insertion sort if partition was not highly
> unbalanced. (novel)
>  - Shuffle 8 elements elements on highly unbalanced partition. (novel)
>  - Only decrement counter to switch to heapsort on highly unbalanced
> partition. (novel)
>
>
>
> 2015-04-07 15:50 GMT+02:00 Jonathan Wakely <jwakely@redhat.com>:
>> On 07/04/15 15:44 +0200, Orson Peters wrote:
>>>
>>> I'd like to present pattern-defeating quicksort, a novel sorting
>>> algorithm.
>>
>>
>> I'd be nervous about switching to a novel algorithm rather than a
>> well-known one that has stood the test of time, but this isn't my area
>> of expertise so I'll leave it to others to make any more substantial
>> comments.
>>



More information about the Libstdc++ mailing list