This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [libstdc++] pdqsort - a faster std::sort
- From: Orson Peters <orsonpeters at gmail dot com>
- To: Christopher Jefferson <chris at bubblescope dot net>
- Cc: "libstdc++" <libstdc++ at gcc dot gnu dot org>, FranÃois Dumont <frs dot dumont at gmail dot com>
- Date: Tue, 21 Apr 2015 17:22:48 +0200
- Subject: Re: [libstdc++] pdqsort - a faster std::sort
- Authentication-results: sourceware.org; auth=none
- References: <CAJxLxMXy4gqAWfXj_p1tyyUSj4PqFp3ASzdxFtyDk2W1F_PdsQ at mail dot gmail dot com> <20150407135025 dot GF9755 at redhat dot com> <CAJxLxMVEW-+bSFyDs7sWytEMKVrhMpcQxk-9QetWem8ZtSeSxg at mail dot gmail dot com> <CAJxLxMWkj7kKteFh7YWHv5gr+Fge_2VeN6QdJ_TFqW2nUtin=w at mail dot gmail dot com> <CA+jCFLvDjSjPSF+dKDVuKWW-hsSK_LC3c=VwiFEhhx0EOyiqAA at mail dot gmail dot com> <CAJxLxMU_3vV1cozS1MnfSo5NNodW1J_1zZWuimdpCguO1cO-0w at mail dot gmail dot com> <CA+jCFLubcMg1OxspBjpcKjur6Vi6PJ=Ce_oSkA_b7OqcZR1UwQ at mail dot gmail dot com> <CAJxLxMX6CyVGxPgrZvvJ+Y62RN_86CQ8H0gFdUOHZde0UFJ2dA at mail dot gmail dot com> <CA+jCFLvUxRdmw71_H08ruDCf8QFmXcriE+G2_Cam4t5wQP-1gQ at mail dot gmail dot com> <CAJxLxMXfZ-GoTPO9uQ2Y9QyQJ_ep_+Ls4Di5q5A0B849Y32chg at mail dot gmail dot com> <CA+jCFLvtfsq6+0_r-iXAjE6JSBrxkDuaFu6FMguVhCghOdc0bw at mail dot gmail dot com> <CAJxLxMVhpu8rechANs8q+C4yxKA+587VCZsDqz0UiScMJBEXNA at mail dot gmail dot com> <alpine dot DEB dot 2 dot 11 dot 1504090019010 dot 1608 at laptop-mg dot saclay dot inria dot fr> <5528D498 dot 1040906 at gmail dot com> <alpine dot DEB dot 2 dot 11 dot 1504111021130 dot 1616 at laptop-mg dot saclay dot inria dot fr> <CAJxLxMWTji4hR1w7DphqG+b+uD5iba3beSZ3YRB5jNr3Auq=iQ at mail dot gmail dot com> <CA+jCFLui81gO+Qn9rGu19ArntUHT83pQYKcihQYJAeFSwWeH8Q at mail dot gmail dot com>
Not yet, I might be able to do so today.
You suggest 100,000 element arrays as value type, that's fine.
How many of these expensive elements should I attempt to sort? 1000
(that's ~400MB if using 32 bit int elements)?
On Tue, Apr 21, 2015 at 4:38 PM, Christopher Jefferson
<chris@bubblescope.net> 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