Re: [boost] [move][container] Review Request (new versions of Boost.Move and Boost.Container in sandbox and vault)

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>
void
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.

-Howard