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