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: Christopher Jefferson <chris at bubblescope dot net>
- To: Orson Peters <orsonpeters at gmail dot com>
- Cc: "libstdc++" <libstdc++ at gcc dot gnu dot org>, FranÃois Dumont <frs dot dumont at gmail dot com>
- Date: Tue, 21 Apr 2015 15:38:22 +0100
- 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>
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