This is the mail archive of the
`libstdc++@gcc.gnu.org`
mailing list for the libstdc++ project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: Christopher Jefferson <chris at bubblescope dot net>*To*: "libstdc++" <libstdc++ at gcc dot gnu dot org>, Orson Peters <orsonpeters at gmail dot com>*Date*: Tue, 13 Oct 2015 20:28:21 +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> <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> <CA+jCFLui81gO+Qn9rGu19ArntUHT83pQYKcihQYJAeFSwWeH8Q at mail dot gmail dot com> <alpine dot DEB dot 2 dot 20 dot 1510131808030 dot 2213 at laptop-mg dot saclay dot inria dot fr>

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

**Follow-Ups**:**Re: [libstdc++] pdqsort - a faster std::sort***From:*Orson Peters

**References**:**Re: [libstdc++] pdqsort - a faster std::sort***From:*Marc Glisse

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |