Testing replacement std::sort

Paolo Carlini pcarlini@suse.de
Sat May 28 09:00:00 GMT 2005


Hi Chris,

> Sorry, I should perhaps have explained :)

Thanks for the explanation!

> This is part of my continuing aim to add move symantics/rvalue
> references to <algorithm>. For almost every function doing this has
> been a case of simply looking carefully for where we copy things and
> seeing where these copies can be turned into moves, and where they are
> unnessasary. In almost all cases the basic algorithm ends up being the
> same at the end.
>
> The sole exception to this is introsort_loop, and it's calls to
> unguarded_partition.

Ok, ok...

> 3) Appears to be the most reasonable, it only produces a very small
> slowdown, which is easily swallowed if the copying you saved was any
> significant size.

[snip]

> I'm currently implementing a more careful version of 3. As a current
> rough guide, I get the following:
>
> std::sort an array length 100,000 of:
> vector<int> : 40 ticks
> vector<int>* (using a comparitor that derefences the *): 36 ticks
> vector<int> with moveable sort: 30 ticks

For now I'm skipping the (interesting) technical parts, simply because
I'm missing way too many details of the algorithm, hope to return to
that during the next days...

But I don't really understand the "small slowdown" wrt 40 ticks -> 30
ticks. Ah, maybe now I see: 40 -> 30 is the cumulative effect of the
"move semantics" trick (already well effective for arrays of vectors of
lenght 1, eh, eh!) + small slowdown of the algo itself. Good. However, I
would guess that std::sort is used *a lot* also for containers or
builtins of non-moveable things, anyway. We should really make sure that
we are not slowing down things in that case. At your ease, maybe just
when sending the final 3, please post some clear figures about such
case. Worst case, we can consider dispatching to two different
implementations.

> Note that this is only for vector<int>s of length 1. Of course the
> second and third stay quite similar as the size of the vector increases

Of course: this is *so* cool of move semantics! ;)

Another random tought I had, is that we should probably provide a
minimum of documentation about how to change a given type to make it
amenable to our simulated move-semantics, i.e., __is_moveable,
constructor, assignment operator, etc. Or, more generally, a small
design document about the whole thing. Would be really useful both for
the users and when moving to real move semantics ;) If you are willing
to draft something I can help.

Paolo.



More information about the Libstdc++ mailing list