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

[Christopher Jefferson <chris at bubblescope dot net>]

On 13 October 2015 at 17:13, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hi Chris,
>
> did you ever get a chance to look at it? I was reminded of it because I have
> an application here where one call to sort is about 1/3 of the total running
> time. Using sort takes 3.46s, while using stable_sort takes 3.08s (yes, it
> is faster...) and pdqsort is only 2.85s.


Hi Marc,

I didn't go back and look again, but I will.

Orson: Are you happy with the branch as it currently exists?

Chris

>
> (I didn't look at the implementation myself)
>
>
> On Tue, 21 Apr 2015, Christopher Jefferson wrote:
>
>> 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
>>
>>
>
> --
> Marc Glisse