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]

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


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.

(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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]