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

[Orson Peters]

>  - 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?).

If C++11 is enabled, the implementation only moves or swaps. All moves
or swaps are done using ADL-lookup unqualified swap or
PDQSORT_PREFER_MOVE which becomes std::move on C++11.

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

I noticed this when I was studying libstdc++s implementation, and I
couldn't figure out why. The implementation of pdqsort does not
currently do this, and for a good reason: it's faster to move the
pivot into a local variable for speed.

The compiler can't prove that *begin (where the pivot is kept during
the partition operation) does not get changed during the partition
operation, and thus has to load the memory for every comparison. This
will always hit cache after the first few iterations, so it doesn't
matter that much, but it's not nothing.

The difference becomes bigger in insertion sort, where you only need
to do 2 moves when using a local variable, but if you use iter_swap it
has to do 3 moves per iteration.

It wouldn't be hard at all to change pdqsorts implementation to only
use iter_swap, but if possible I'd like to avoid 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!

I don't have time today or tomorrow, but I'll make an attempt the day
after tomorrow.

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

I'll see what I can do.

2015-04-08 11:35 GMT+02:00 Christopher Jefferson <chris@bubblescope.net>:
> 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.
>>>