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

[Christopher Jefferson <chris at bubblescope dot net>]

Hi,

Sorry, I've been very busy and not had time to look at this. I plan to
do so this week.

One final request (sorry!) Have you tried benchmarking this against
std::sort with -std=c++03, and with a more expensive type (I recommend
making some vectors of length... 100,000? Make some easy to compare
(make first element different) and some expensive to compare (make
only last elements different).

Chris


On 12 April 2015 at 07:11, Orson Peters <orsonpeters@gmail.com> wrote:
> 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