Boost logo

Boost :

Subject: Re: [boost] [move][container] Review Request (new versions of Boost.Move and Boost.Container in sandbox and vault)
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2009-10-17 11:07:15

On Oct 17, 2009, at 4:39 AM, Christopher Jefferson wrote:

> On 16 Oct 2009, at 02:10, Thomas Klimpel wrote:
>> So I'm left with the impression that there might be quite some good
>> reasons not to implement move-assignment as swap, but no really
>> conclusive counter examples against it. On the other hand, as long
>> as the absence of conclusive counter examples can't be "proved",
>> ruling that move-assignment may generally be implemented as swap
>> will be risky or worse.
> Just as one point of information, which I've previously seen used in
> favour of using swap as move.
> While it is true that a move which doesn't swap on (for example)
> vector<T> is O(n) rather than O(1), due to the need to destruct all
> the elements, I found in experiments that sorting a range of
> vector<T> is actually very slightly faster when move-assignment is
> NOT implemented as swap, so performance isn't even really an
> argument in it's favour.

There's a theoretical foundation behind this empirical observation.

sort is a "resource preserving" permutation (as are many, but not all,
algorithms in <algorithm>). I.e. things just get rearranged. Nothing
need be constructed or destructed, though such constructions/
destructions may happen as implementation details.

swap is the simplest "resource preserving" permutation algorithm, and
for the purposes of this argument, is no different from sort:

template <class T>
swap(T& x, T& y)
     T t(std::move(x));
     x = std::move(y);
     y = std::move(t);

The construction of t will put x into a resource-less state. The move
assignment of x is <em>into an object with a resource-less state</
em>. I.e. here it makes no difference if T's move assignment operator
is implemented with or without clear(). There is nothing to clear().
This move assignment will put y into a resource-less state. In the
last move assignment, it is again into an object with a resource-less
state. There is nothing to clear() out of y by the time it is move-
assigned into.

This pattern: if you move assign into something, it is already
resource-less; is just as true for sort as it is for swap. And for
unique. And for stable_partition. And for stable_sort. And for
inplace_merge. Etc.

Thus the cost for clearing the lhs within a move-assignment prior to
the transfer of resources is minimal. It is usually a no-op.

So why do it? What's the benefit even if the cost is small?

Consider std::remove: This is one of the few algorithms in
<algorithm> which is not a "resource preserving" permutation.
Consider remove({a, b, c, d, e}, c). This will result in the sequence
{a, b, d, e, e'}. To achieve this result, the following move
assignments will take place:

c = move(d);
d = move(e);

The first move assignment is not into a resource-less c. If move
assignment into c doesn't "clear", when do those resources go away?
For most resources (such as memory), it doesn't really matter when.
The resources will still be owned if move-assignment doesn't
aggressively destroy them (probably by e').

But for some resources (threads, file handles, mutexes), it will
matter if they live too long. The client calling std::remove may or
may not destruct e' "soon". But the client asked std::remove to
remove c (and presumably all of c's resources). I do not think it
would be a good idea for std::remove to also say: Oh, and you better
destruct e' too just to make sure c is really gone.

This is the benefit of move assignment "clearing" potentially
significant resources aggressively. I believe this benefit outweighs
the cost.


Boost list run by bdawes at, gregod at, cpdaniel at, john at