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

[Orson Peters]

All right, I've put in the work and made the pdqsort source libstdc++
compatible. I've created a seperate branch on Github where I published all my
changes - you can look at the commit history to see exactly how I got from my
original code to the libstdc++ compatible code.

https://github.com/orlp/pdqsort/blob/libstdc%2B%2B-merge/pdqsort.h

While testing I found one minor bug in pdqsort. In the insertion sort routine I
decremented (but not dereferenced) an iterator before 'begin', which is not
allowed. The fix was trivial (move decrement after range check instead of
before).

After fixing the above bug pdqsort passes all libstdc++ tests. You can confirm
this yourself by inserting the above linked code into bits/stl_algo.h, renaming
sort to stdsort (or anything else) and pdqsort to sort.

A couple of notes that maybe should be addressed before merging the code:

 - I have attempted to follow the style guide where possible, but it's very
   likely I've made a mistake here and there due to unfamiliarity.

 - My insertion sort routines (__pdq_insertion_sort and
   __pdq_unguarded_insertion_sort) are different than those found in
   libstdc++. To my knowledge __pdq_insertion_sort is strictly better than
   __insertion_sort, because I only move an element if it's out of place -
   __insertion_sort always moves an element twice, even if already placed
   correctly. __pdq_unguarded_insertion_sort is a trade-off vs
   __unguarded_insertion_sort. The pdq version compares iterators on every
   iteration, the libstdc++ version does an initial check against the first
   element in the array. For pointers I'm almost certain my implementation is
   faster (the comparison is virtually free), but it's not a clear cut in the
   general case.

   I'm convinced my insertion sort can replace libstdc++s without issue, but I'm
   not sure about the unguarded version.

 - I have marked all functions inline for now - I don't know which ones we'd
   really want to mark inline and which ones we don't.



On Sat, Apr 11, 2015 at 10:50 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Sat, 11 Apr 2015, François Dumont wrote:
>
>>    I think comparator is taken by copy simply because the Standard
>> signature is taking it by copy. We expect gcc to do a good job to optimize
>> away the intermediate copy.
>
>
> While this is true, I don't think it is a reason to force extra copies
> internally when it is just as easy to avoid them (as long as someone is
> willing to write and test the patch). For iterators in particular, passing
> by value is useful to force the decay from array to pointer, but there is no
> need to decay an already decayed type.
>
> https://gcc.gnu.org/ml/libstdc++/2013-09/msg00220.html
>
> (I didn't feel strongly enough to write the patch myself, and still don't)
>
> --
> Marc Glisse