[shared_ptr] dangerous implementation of move constructor
I see that rvalue reference support has just been added to the shared_ptr template, and I think that there's a subtle bug in the implementation. It is implemented as follows: shared_ptr( shared_ptr && r ): px( r.px ), pn() // never throws { pn.swap( r.pn ); } The problem is that after the move constructor has been called the moved -from shared_ptr, r, is in a dangerously inconsistent state. Its has an empty shared count, but it contains a non-null pointer. Usually it should be either destructed or assigned to shortly after the move constructor is called, in which case all will be well. However, if it remains unchanged then there is the danger that someone might try to dereference it after r.px has been deleted. This, of course, could result in a hard-to-track access violation. To see what I mean, consider the following rather silly code: shared_ptr<int> r(new int(1)); shared_ptr<int> s(std::move(r)); s.reset(); if (r) { //r.get() != 0, so this returns true cout << *r; // Uh-oh } The solution to this problem is simple: just add one more line of code to set r.px to NULL. shared_ptr( shared_ptr && r ): px( r.px ), pn() // never throws { r.px = 0; pn.swap( r.pn ); } Now r will be an empty shared_ptr and the danger will be averted. Joe Gottman
Joe Gottman wrote:
I see that rvalue reference support has just been added to the shared_ptr template, and I think that there's a subtle bug in the implementation. It is implemented as follows:
shared_ptr( shared_ptr && r ): px( r.px ), pn() // never throws { pn.swap( r.pn ); }
The problem is that after the move constructor has been called the moved -from shared_ptr, r, is in a dangerously inconsistent state. Its has an empty shared count, but it contains a non-null pointer. Usually it should be either destructed or assigned to shortly after the move constructor is called, in which case all will be well. However, if it remains unchanged then there is the danger that someone might try to dereference it after r.px has been deleted. This, of course, could result in a hard-to-track access violation. To see what I mean, consider the following rather silly code:
shared_ptr<int> r(new int(1)); shared_ptr<int> s(std::move(r)); s.reset(); if (r) { //r.get() != 0, so this returns true cout << *r; // Uh-oh }
The problem with the above code does indeed exist, but it is not a bug in the implementation (let alone a subtle one) - in the sense that the implementation is deliberately written in the way it's written, to not provide a guarantee about the consistency of r after the move. You are right that we can clear r.px easily for shared_ptr, but it's more important to think about the general case: is the user allowed to assume anything about the state of an object after it has been moved from? void f( T t1 ) { T t2( std::move( t1 ) ); // What happens if I use t1 here? } Using t1 after the move looks like a programming error to me.
On Apr 14, 2007, at 1:28 PM, Peter Dimov wrote:
Joe Gottman wrote:
I see that rvalue reference support has just been added to the shared_ptr template, and I think that there's a subtle bug in the implementation. It is implemented as follows:
shared_ptr( shared_ptr && r ): px( r.px ), pn() // never throws { pn.swap( r.pn ); }
The problem is that after the move constructor has been called the moved -from shared_ptr, r, is in a dangerously inconsistent state. Its has an empty shared count, but it contains a non-null pointer. Usually it should be either destructed or assigned to shortly after the move constructor is called, in which case all will be well. However, if it remains unchanged then there is the danger that someone might try to dereference it after r.px has been deleted. This, of course, could result in a hard-to-track access violation. To see what I mean, consider the following rather silly code:
shared_ptr<int> r(new int(1)); shared_ptr<int> s(std::move(r)); s.reset(); if (r) { //r.get() != 0, so this returns true cout << *r; // Uh-oh }
The problem with the above code does indeed exist, but it is not a bug in the implementation (let alone a subtle one) - in the sense that the implementation is deliberately written in the way it's written, to not provide a guarantee about the consistency of r after the move. You are right that we can clear r.px easily for shared_ptr, but it's more important to think about the general case: is the user allowed to assume anything about the state of an object after it has been moved from?
void f( T t1 ) { T t2( std::move( t1 ) ); // What happens if I use t1 here? }
Using t1 after the move looks like a programming error to me.
Fwiw Peter asked me to look at this. Imho after a move from an object it should be in a self-consistent state. All internal invariants should hold. This answer is purposefully vague, and could be used to support either outcome. A very reasonable invariant for a shared_ptr r would be that if (r) then *r is safe. Another very reasonable invariant for a shared_ptr r would be that after a move, if (r) does not imply that you can *r. There is nothing in the rvalue ref proposals that really nails this down. It is up to each class to define its behavior after a move. At the very least it should support assignment and destruction in order to work with generic code. Beyond that I'd say the class should be free to implement whatever semantics / interface it feels best. In this particular case, I think it might be worth the extra assignment to null r.px just to make the class invariant simpler. However that statement falls well short of saying that the standard should require such behavior, or even that this behavior isn't ok with respect to putting this shared_ptr into std::containers or using with std::algorithms. Furthermore I'm anxious to see what "best practices" in this area are born out by field experience. And boost is a great place to have such experiments! :-) -Howard
Howard Hinnant wrote:
On Apr 14, 2007, at 1:28 PM, Peter Dimov wrote:
Joe Gottman wrote:
I see that rvalue reference support has just been added to the shared_ptr template, and I think that there's a subtle bug in the implementation. It is implemented as follows:
shared_ptr( shared_ptr && r ): px( r.px ), pn() // never throws { pn.swap( r.pn ); }
The problem is that after the move constructor has been called the moved -from shared_ptr, r, is in a dangerously inconsistent state. Its has an empty shared count, but it contains a non-null pointer.
[...]
In this particular case, I think it might be worth the extra assignment to null r.px just to make the class invariant simpler.
I don't mind clearing r.px in the Boost implementation of the move constructors, but I'm not sure whether the specification ought to mandate it. The current implementation is a reformulation of shared_ptr( shared_ptr && r ): px( move(r.px) ), pn( move(r.pn) ) { } I'm not sure that we want to prohibit it. If we decide to clear r.px, there's also the matter of the move assignments. One obvious implementation of shared_ptr& operator=( shared_ptr && r ); is to just call swap( r ). I'm not positive that we want to prohibit that, either. We can enforce a postcondition of "r is empty" for the assignments too by using shared_ptr( r ).swap( *this ) as usual, but this strikes me as overspecification. FWIW, shared_ptr by itself does not have an invariant that ties the pointer (px) and the ownership group (pn) together, although it's pretty common for the surrounding code to enforce or assume such an invariant. So I could go either way on that one.
I think that clearing px after a move isn't a good idea. It is true that we need more experience with move semantics to see what works best, but in my opinion anything beyond destruction and assignment on an object that has been "moved" should -- in principle -- be undefined behavior.
From certain point of view this complicates the invariant a bit, but it's very simple to say that after you move an object you can only assign it a new value, or destroy it.
It's also worth mentioning that (much like a raw pointer) there are other ways to end up with a shared_ptr object such that *p is undefined behavior despite that "if(p)" is true. Emil Dotchevski ----- Original Message ----- From: "Howard Hinnant" <howard.hinnant@gmail.com> To: <boost@lists.boost.org> Sent: Saturday, April 14, 2007 4:12 PM Subject: Re: [boost] [shared_ptr] dangerous implementation ofmove constructor
On Apr 14, 2007, at 1:28 PM, Peter Dimov wrote:
Joe Gottman wrote:
I see that rvalue reference support has just been added to the shared_ptr template, and I think that there's a subtle bug in the implementation. It is implemented as follows:
shared_ptr( shared_ptr && r ): px( r.px ), pn() // never throws { pn.swap( r.pn ); }
The problem is that after the move constructor has been called the moved -from shared_ptr, r, is in a dangerously inconsistent state. Its has an empty shared count, but it contains a non-null pointer. Usually it should be either destructed or assigned to shortly after the move constructor is called, in which case all will be well. However, if it remains unchanged then there is the danger that someone might try to dereference it after r.px has been deleted. This, of course, could result in a hard-to-track access violation. To see what I mean, consider the following rather silly code:
shared_ptr<int> r(new int(1)); shared_ptr<int> s(std::move(r)); s.reset(); if (r) { //r.get() != 0, so this returns true cout << *r; // Uh-oh }
The problem with the above code does indeed exist, but it is not a bug in the implementation (let alone a subtle one) - in the sense that the implementation is deliberately written in the way it's written, to not provide a guarantee about the consistency of r after the move. You are right that we can clear r.px easily for shared_ptr, but it's more important to think about the general case: is the user allowed to assume anything about the state of an object after it has been moved from?
void f( T t1 ) { T t2( std::move( t1 ) ); // What happens if I use t1 here? }
Using t1 after the move looks like a programming error to me.
Fwiw Peter asked me to look at this. Imho after a move from an object it should be in a self-consistent state. All internal invariants should hold. This answer is purposefully vague, and could be used to support either outcome.
A very reasonable invariant for a shared_ptr r would be that if (r) then *r is safe.
Another very reasonable invariant for a shared_ptr r would be that after a move, if (r) does not imply that you can *r.
There is nothing in the rvalue ref proposals that really nails this down. It is up to each class to define its behavior after a move. At the very least it should support assignment and destruction in order to work with generic code. Beyond that I'd say the class should be free to implement whatever semantics / interface it feels best.
In this particular case, I think it might be worth the extra assignment to null r.px just to make the class invariant simpler. However that statement falls well short of saying that the standard should require such behavior, or even that this behavior isn't ok with respect to putting this shared_ptr into std::containers or using with std::algorithms. Furthermore I'm anxious to see what "best practices" in this area are born out by field experience. And boost is a great place to have such experiments! :-)
-Howard
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
What is expected to happen here: { shared_ptr<T> t(something()); shared_ptr<T> t1(std::move(t)); } // t1 destructor called, t destructor called? If t gets its destructor called, then it must obviously be in some self-consistent state. For shared_ptr I think this would mean that upon destruction, it deletes 0. If the move constructor proposal doesn't say anything about being in a minimally destructible state after being moved, I think it should. Unless of course the destructor for t doesn't get called (which would imply some runtime checks - always). -----Original Message----- From: boost-bounces@lists.boost.org on behalf of Howard Hinnant Sent: Sat 4/14/2007 4:12 PM To: boost@lists.boost.org Subject: Re: [boost] [shared_ptr] dangerous implementation ofmove constructor Fwiw Peter asked me to look at this. Imho after a move from an object it should be in a self-consistent state. All internal invariants should hold. This answer is purposefully vague, and could be used to support either outcome.
Howard Hinnant wrote:
[snip]
There is nothing in the rvalue ref proposals that really nails this down. It is up to each class to define its behavior after a move. At the very least it should support assignment and destruction in order to work with generic code. Beyond that I'd say the class should be free to implement whatever semantics / interface it feels best.
I respectfully disagree ;-) If the object is still there and can be used it should be usable. If we had destructive move-semantics, I would agree that the state of the objects should be undefined (or even better, destroyed), but in that case I would expect compiler help to detect uses of move-destructed variables after the move-destruction. std::vector<T> myvect(...); //myvect's destructor is called, the object is not longer usable std::vector<T> myvect2(std::destructive_move(myvect)); myvect.resize(1000); <-- COMPILATION ERROR In my opinion, the standard should clearly say what happens with an standard component. An example: what's the state of an STL container after being moved? std::vector<T> myvect(...); std::vector<T> myvect2(std::move(myvect)); myvect.resize(1000); <-- is this correct? If myvect is allowed to be in a non-usable state, the allocator might be moved from myvect to myvect2. If myvect should be usable, the allocator should be copied --> corollary: If we want non-throwing move constructors and assignments (which is surely required for objects we want to place in STL containers, like std::list<std::vector<T> >) allocator copying shouldn't throw. If the standard does not specify anything, implementors of allocators must always support the worst case (copying shouldn't throw) but they can't use the advantages (the vector is NOT reusable). Users also get the worst of both worlds. Since current move semantics are non-destructive the state of the object should be usable. For objects that have a default-constructor (like shared_ptr or vector) the moved state could be equal to default-constructed (which is consistent *and* usable). And no-throw guarantee should be required for such move operations This might complicate a bit the implementation of allocators, but it's perfectly possible to achieve this with containers. For shared_ptr, I don't know if the state should be default-constructed, but I would like to reuse that object via reset(). For objects that have no such default-state, and have no resource reassignment functions (like reset() or similar) there is no problem because there is no interface to reuse the object. For objects that don't have default-constructor but have resource reassignment functions, the state might be undefined, but I would require object reuse capability. In any case, you need to internally maintain the "moved" state so that the destructor does not crash the program. Since we have to pay some price (the zombie state, if you want to call it), let's take something in return. My 2 cents, Ion
On 4/16/07, Ion Gaztañaga <igaztanaga@gmail.com> wrote:
[snip Ion arguments]
Hi Ion,
For objects that have no such default-state, and have no resource reassignment functions (like reset() or similar) there is no problem because there is no interface to reuse the object. For objects that don't have default-constructor but have resource reassignment functions, the state might be undefined, but I would require object reuse capability. In any case, you need to internally maintain the "moved" state so that the destructor does not crash the program. Since we have to pay some price (the zombie state, if you want to call it), let's take something in return.
You seem to have arguments for both sides, undefined and usable object. I believe for most we want that move-constructors imply in almost-zero overhead, after all which is the benefit of moving a temporary if it has significant overhead? You have written a lot of allocators for the shmem library, and you probably had to workaround the many copies that the standard allows. Wouldnt it be better to have: std::list<std::vector<...> > foo(); Have almost 0 overhead instead of guaranteed usability of moved objects? IMHO, have assignment and destruction guaranteed to work on a moved object is guarantee enough. You seem to be proposing creating a new move-constructor, which I believe is now too late and a little bit more complex than needed. A simple moving + assignment is enough to have the object usable again. I would support, though, better assertions inside shared_ptr for using a moved shared_ptr. That way we have the better of two worlds.
My 2 cents,
Ion
Best regards, -- Felipe Magno de Almeida
Felipe Magno de Almeida wrote:
You seem to have arguments for both sides, undefined and usable object.
I'm terrible explaining my points. My main argument is that for objects that have default-constructor (like shared_ptr), little overhead is needed to implement full reusability. The same happens with containers (except for maybe allocator copying, but stateful allocators are, well..., not very well supported).
I believe for most we want that move-constructors imply in almost-zero overhead, after all which is the benefit of moving a temporary if it has significant overhead?
The problem is that you might move objects that are not temporaries. See my other post about std::vector
You have written a lot of allocators for the shmem library, and you probably had to workaround the many copies that the standard allows. Wouldnt it be better to have:
std::list<std::vector<...> > foo();
Have almost 0 overhead instead of guaranteed usability of moved objects?
I think both can be achieved.
IMHO, have assignment and destruction guaranteed to work on a moved object is guarantee enough.
Ok. I will add move constructor and move assignment. But that means they are reusable. And that's my point.
You seem to be proposing creating a new move-constructor, which I believe is now too late and a little bit more complex than needed. A simple moving + assignment is enough to have the object usable again.
I might have missed the assignment requirement in the discussion, sorry. I thought that no guarantee was offered for a moved object. Regards, Ion
Ion Gaztañaga wrote:
For objects that have no such default-state, and have no resource reassignment functions (like reset() or similar) there is no problem because there is no interface to reuse the object.
I think I was with you until this point. It seems to me that the exact opposite is true; objects that have no "empty" or "default" state cannot implement a move, at least not easily, whereas reusing a moved-from object via assignment or reset is no problem at all. FWIW, I've changed the shared_ptr move constructors and assignment operators to leave the source empty, but this doesn't mean that I'm convinced that the general case needs to be constrained in such a way. In particular, T& operator=( T && r ) { swap( r ); return *this; } seems a very reasonable implementation of move assignment, and has a slight performance advantage (one call to ~T instead of two in a typical use case) over T& operator=( T && r ) { T( move( r ) ).swap( *this ); return *this; } which is what is needed for r to be left empty.
Peter Dimov wrote:
Ion Gaztañaga wrote:
For objects that have no such default-state, and have no resource reassignment functions (like reset() or similar) there is no problem because there is no interface to reuse the object.
I think I was with you until this point. It seems to me that the exact opposite is true; objects that have no "empty" or "default" state cannot implement a move, at least not easily, whereas reusing a moved-from object via assignment or reset is no problem at all.
Ok. So if such objects can't be moved, there is no problem to offer reusability for other objects that can be moved ;-)
FWIW, I've changed the shared_ptr move constructors and assignment operators to leave the source empty, but this doesn't mean that I'm convinced that the general case needs to be constrained in such a way. In particular,
T& operator=( T && r ) { swap( r ); return *this; }
seems a very reasonable implementation of move assignment, and has a slight performance advantage (one call to ~T instead of two in a typical use case) over
T& operator=( T && r ) { T( move( r ) ).swap( *this ); return *this; }
which is what is needed for r to be left empty.
Ok. Forget about the default constructed state. I don't want you to deallocate the heap allocated reference count (you know I'm the leader of the anti-allocate religion). Just tell me if move in terms of swapping can lead to reusability. Does it make any sense? If it does not, can you find a way so that you get swap semantics *and* reusability is possible? The default-constructed state was just a possibility, not the goal. My goal is to left the objects in a consistent, usable state. If resources from the previous move target have been stolen so that we can reuse them, even better. Regards, Ion
Ion Gaztañaga wrote:
Ok. So if such objects can't be moved, there is no problem to offer reusability for other objects that can be moved ;-)
Reusability was never questioned. Usability after move is the problem. The question is whether the user may legitimately do something with an moved-from object with predictable results _except_ destroying or reusing it via assignment or reset.
Peter Dimov wrote:
Ion Gaztañaga wrote:
Ok. So if such objects can't be moved, there is no problem to offer reusability for other objects that can be moved ;-)
Reusability was never questioned. Usability after move is the problem. The question is whether the user may legitimately do something with an moved-from object with predictable results _except_ destroying or reusing it via assignment or reset.
There are many more ways to reuse an object than assignment and reset. For instance, I would be extremely disappointed if the following code didn't work: vector<double> foo; vector<double> bar = move(foo); foo.resize(10); for (size_t n = 0; n < 10; ++n) { foo[n] = n + 7; } Joe Gottman
Joe Gottman wrote:
There are many more ways to reuse an object than assignment and reset. For instance, I would be extremely disappointed if the following code didn't work:
vector<double> foo; vector<double> bar = move(foo); foo.resize(10); for (size_t n = 0; n < 10; ++n) { foo[n] = n + 7; }
The code will work under any implementation of the move constructor, IMO. The more interesing question is, given: bar = move(foo); would you be extremely disappointed if foo doesn't retain its allocator instance but gets bar's after the move? I, personally, don't intend to ever do something with a moved-from object except destroy it. :-)
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Peter Dimov
I, personally, don't intend to ever do something with a moved-from object except destroy it. :-)
If Scott Meyers comes out with a new "Effective C++" book after C++0x, I'd imagine this would be one of the items!
Peter Dimov wrote:
Joe Gottman wrote:
There are many more ways to reuse an object than assignment and reset. For instance, I would be extremely disappointed if the following code didn't work:
vector<double> foo; vector<double> bar = move(foo); foo.resize(10); for (size_t n = 0; n < 10; ++n) { foo[n] = n + 7; }
The code will work under any implementation of the move constructor, IMO. The more interesing question is, given:
bar = move(foo);
would you be extremely disappointed if foo doesn't retain its allocator instance but gets bar's after the move?
No, but I would expect foo.get_allocator() to return some valid allocator and not cause a segmentation fault. In general, I don't want functions that previously were always safe to be unsafe after a move. Joe Gottman
Joe Gottman wrote:
No, but I would expect foo.get_allocator() to return some valid allocator and not cause a segmentation fault. In general, I don't want functions that previously were always safe to be unsafe after a move.
To get back to shared_ptr, given p and q of type shared_ptr, would you be extremely disappointed if after: p = move( q ); q holds the old value of p instead of being empty? (Note that p may have had a value that you could consider "unsafe" in the context of the valid values of q.)
Peter Dimov wrote:
To get back to shared_ptr, given p and q of type shared_ptr, would you be extremely disappointed if after:
p = move( q );
q holds the old value of p instead of being empty?
(Note that p may have had a value that you could consider "unsafe" in the context of the valid values of q.)
Not extremely disappointed. I do think that move semantics would be very useful for shared_ptr's, and I know that there are classes where it would be prohibitively expensive to clear the source after a move assignment. But note that it is possible to efficiently make q hold a null pointer after a move assignment: shared_ptr & operator=( shared_ptr && r ) // never throws { pn.swap(r.pn); px = r.px; r.px = 0; return *this; } template <class Y> shared_ptr &operator=(shared_ptr<Y> &&r) //never throws { pn.swap(r.pn); px = r.px; r.px = 0; return *this; } This is actually fractionally more efficient than calling swap(pn, r.pn); swap(px, r.px); since swap(px, r.px) involves one copy constructor and two assignments and the implementation I gave just involves two assignments. Also, in the case of the template assignment operator it is not required that px be convertible to Y*. Joe Gottman
Joe Gottman wrote:
But note that it is possible to efficiently make q hold a null pointer after a move assignment:
shared_ptr & operator=( shared_ptr && r ) // never throws { pn.swap(r.pn); px = r.px; r.px = 0; return *this; }
Yes, I know. This still leaves r half-empty, except that now it is the other half. If we're going to the trouble to clear r, I'd rather have it in a completely specified state.
Peter Dimov wrote:
To get back to shared_ptr, given p and q of type shared_ptr, would you be extremely disappointed if after:
p = move( q );
q holds the old value of p instead of being empty?
(Note that p may have had a value that you could consider "unsafe" in the context of the valid values of q.)
Thinking it twice. Wouldn't simple swap lead to the false impression that the reference count for the object p was pointing was dropped? If p was the last reference to that value, wouldn't the user be surprised if value is not destroyed (with its side effects) just when p is move-assigned? If the user does not destroy q, the value is staying there. OTOH, this could make move-assignment more expensive because it might destroy objects. Just a thought, Ion
Ion Gaztañaga wrote:
Peter Dimov wrote:
To get back to shared_ptr, given p and q of type shared_ptr, would you be extremely disappointed if after:
p = move( q );
q holds the old value of p instead of being empty?
(Note that p may have had a value that you could consider "unsafe" in the context of the valid values of q.)
Thinking it twice. Wouldn't simple swap lead to the false impression that the reference count for the object p was pointing was dropped? If p was the last reference to that value, wouldn't the user be surprised if value is not destroyed (with its side effects) just when p is move-assigned? If the user does not destroy q, the value is staying there. OTOH, this could make move-assignment more expensive because it might destroy objects.
This is the essence of the discussion. :-) I think that efficiency is more important in a move primitive than leaving the source in a predictable state, Joe argues the other way.
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Peter Dimov Sent: Tuesday, April 17, 2007 5:59 AM To: boost@lists.boost.org Subject: Re: [boost] [shared_ptr] dangerous implementation of moveconstructor
This is the essence of the discussion. :-) I think that efficiency is more important in a move primitive than leaving the source in a predictable state, Joe argues the other way.
[Joe] Tossing in my own $.02, this Joe tends to agree somewhat with the other Joe. :) If I wanted to swap p and q, I can do that today without the move. On the other hand, if I move a value from q to p, I expect p's contents to be gone, not to be transferred to q. Now, I could see leaving q with old contents and flagged so it's destruction doesn't cause a delete or some such. I think the semantics of the English word 'move' would make it very surprising to any user to have it do a swap instead. Just my opinion. joe
Greer, Joe wrote:
[Joe] Tossing in my own $.02, this Joe tends to agree somewhat with the other Joe. :) If I wanted to swap p and q, I can do that today without the move.
Not in a generic way, though. Move is about performance. For some types, swap is slower than copy. There is also the use case of a = f(); where you automatically get the move assignment if f() returns an rvalue, and an ordinary copy otherwise.
On the other hand, if I move a value from q to p, I expect p's contents to be gone, not to be transferred to q.
In 99.4% of the use cases for move, q is a temporary and you don't care what it holds, since it will be destroyed anyway at the end of the expression. Decreasing the performance for the majority to appease a minority which would like to move from lvalues and have them in a predictable state afterwards seems like a questionable tradeoff to me. Not necessarily wrong, just questionable. :-)
Peter Dimov wrote:
Thinking it twice. Wouldn't simple swap lead to the false impression that the reference count for the object p was pointing was dropped? If p was the last reference to that value, wouldn't the user be surprised if value is not destroyed (with its side effects) just when p is move-assigned? If the user does not destroy q, the value is staying there. OTOH, this could make move-assignment more expensive because it might destroy objects.
This is the essence of the discussion. :-) I think that efficiency is more important in a move primitive than leaving the source in a predictable state, Joe argues the other way.
Sorry, my radar was activated when containers entered in the discussion ;-) I agree with you that efficiency is important for nearly all objects. Containers might also hold resources that would be liberated with the destructors, but I wouldn't want to implement the move assignment as something like clear() + swap(). Implementing move assignments as swap sounds good and I've implemented pseudo-move semantics (based on library emulation) for Interprocess containers using swap for move assignments (see CVS code). My point is that the standard should explicitly say it: "move assignment for this container is the same as swap()". At least we would know what is really happening. If we left that undefined the complexity of a move operation could be terribly varying depending on the implementation, and by consequence, unusable. In a container, for example, operation complexity refers to search and copy, but in node containers destroying values is orders of magnitude slower than doing a search. Information is power. Ion
On 4/17/07, Ion Gaztañaga <igaztanaga@gmail.com> wrote:
[snip]
If we left that undefined the complexity of a move operation could be terribly varying depending on the implementation, and by consequence, unusable. In a container, for example, operation complexity refers to search and copy, but in node containers destroying values is orders of magnitude slower than doing a search. Information is power.
That's what the complexity guarantees are for. There could be a guarantee of O(1) for move-constructors and then the implementation chooses how to implement it. Seems very reasonable to me and seems to be usual approach in standardization, wrt. containers.
Ion _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Felipe Magno de Almeida
Felipe Magno de Almeida wrote:
On 4/17/07, Ion Gaztañaga <igaztanaga@gmail.com> wrote: That's what the complexity guarantees are for. There could be a guarantee of O(1) for move-constructors and then the implementation chooses how to implement it. Seems very reasonable to me and seems to be usual approach in standardization, wrt. containers.
Yes. "erase" for a list is but O(1) there is call to allocator::deallocate that does not count in that complexity. allocator::deallocate can have linear complexity. But I agree that specifying O(1) would lead to "swap". That would be really nice. Regards, Ion
If we left that undefined the complexity of a move operation could be terribly varying depending on the implementation, and by consequence, unusable. In a container, for example, operation complexity refers to search and copy, but in node containers destroying values is orders of magnitude slower than doing a search. Information is power.
Information is power, but limiting the specification of an interface often makes better, more optimal implementations possible.
No, but I would expect foo.get_allocator() to return some valid allocator and not cause a segmentation fault. In general, I don't want functions that previously were always safe to be unsafe after a move.
If I read you correctly, you want the moved-from object to have exactly the same state as an empty one. I don't think this is reasonable requirement in general, because a given class may not have an empty state (e.g. it has no default constructor) yet it can define proper move semantics (that is, it defines "moved from" state even though it does not define "empty" state.) Specifically for shared_ptr, it does have empty state, and it is perhaps reasonable to require that moved-from shared_ptr<T> should behave just like an empty one. The main motivation for this requirement seem to be that code like: shared_ptr<T> p( new T ); shared_ptr<T> q( move(p) ); if( p ) p->foo(); is still valid, e.g. after p has been moved, if(p) would be false. However, the invariant of shared_ptr is somewhat independent of the semantics of T *. The expression "if(p)", as well as dereferencing p, have to do with the T * semantics, not with the shared_ptr<T> invariant. This basically means that (in general), with or without move semantics being considered, for a given shared_ptr<T> p, you can't assume that: if( p ) p->foo(); is legal (someone correct me if I'm wrong.) Therefore, I see no point in requiring that moved-from shared_ptr's state is the same as the empty state. Emil Dotchevski
Peter Dimov wrote:
Joe Gottman wrote:
There are many more ways to reuse an object than assignment and reset. For instance, I would be extremely disappointed if the following code didn't work:
vector<double> foo; vector<double> bar = move(foo); foo.resize(10); for (size_t n = 0; n < 10; ++n) { foo[n] = n + 7; }
The code will work under any implementation of the move constructor, IMO.
Well, some argue that only a move assignment or destructor should work after an object is being moved. I think the container should continue to work. I would be really disappointed if Joe's code does not work.
The more interesing question is, given: bar = move(foo);
would you be extremely disappointed if foo doesn't retain its allocator instance but gets bar's after the move?
If you want to left bar usable there is no other chance than swapping allocators. I would like to differentiate two cases with containers: Move assignment: It can easily implemented in terms of swap. Allocators are also swapped if they are not equal (or just swapped without any question). Allocators must go with the moved values. Move constructor: This is really tricky. If we want to left the moved object usable, we need to copy the allocator. Something like: Container(Container &&moved_container) : allocator_(moved_container_.allocator_) //Note, copy constructed { //Default initialization // .... //and now swap this->swap(moved_container); } Metrowerks/Freescale implementation implemented something like this, so moved containers were left perfectly usable. Since in Interprocess I wanted to maintain containers usable after being moved I've chosen the same option. The problem is that the allocator must be copy constructed and then swapped. This means that if we want a no-throw move constructor, allocator copying can't throw. In practice, I haven't seen an allocator (stateless or stateful= with a throwing copy-constructor, even shared memory ones. And if they need to acquire resources, they could delay the exception launch until the allocation function. The dynamic allocation of the "end" node in some containers (some implementation just embed them in the container so there is no problem) might also throw. But nothing that can't be delayed until an insertion is requested. The standard might easily mandate non-throwing copy constructors for allocators without breaking code and limiting current allocators. To sum up: Leaving the moved container fully usable and having no-throw guarantee for move constructors needs some tweaks, but in practice I think it's perfectly achievable and offers big advantages. Regards, Ion
There are many more ways to reuse an object than assignment and reset. For instance, I would be extremely disappointed if the following code didn't work:
vector<double> foo; vector<double> bar = move(foo); foo.resize(10); for (size_t n = 0; n < 10; ++n) { foo[n] = n + 7; }
I don't understand why would you do anything with foo after you moved it? If you wanted to reuse foo for some reason, you could have said: vector<double> foo; ... vector<double> bar; bar.swap(foo); foo.resize(10); ... Emil Dotchevski
Ion Gaztañaga wrote:
Since current move semantics are non-destructive the state of the object should be usable. For objects that have a default-constructor (like shared_ptr or vector) the moved state could be equal to default-constructed (which is consistent *and* usable).
I want to correct this. Default-constructed "could" be ok, but no optimal. For example: std::vector<T> myvect(...); std::vector<T> myvect2(std::move(myvect)); The move operation could be implemented as "swap" so myvect could hold memory previously hold by myvect. This opens the possibility to reuse existing resources. Take for example the implementation of vector with move semantics: This is the old buffer class vector { // ... T *buf_; size_type length_; size_type capacity_; }; Let's insert an object in the beginning. The vector has enough capacity we just need to move the objects and assign the new one in the first slot. Now if moved objects can be reused (code not compiled and it might have flaws). //Suppose length_ > 0... if(length_ > 0){ allocator.construct(buf_+length_, move(buf_[length-1])); ++length_; //Move values one position //Reuse of stl algorithms with a simple iterator wrapper //that moves objects. Don't worry about the moved //value since it can be reused std::copy_backwards ( move_iterator(buf_) , move_iterator(buf_ + length_ - 2) , move_iterator(buf_ + 1)); buf[0] = value; //or if value was catched as a rvalue reference buf[0] = move(value); } else{ allocator.construct(buf_, move(value)); ++length_; } move_iterator is described here: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1771.html, search "24 - Iterators library" to find it. Simple, efficient and easy. And exception safe (when coded correctly, which might not be my case ;-) ). If moved objects can't be reused, want can I do with buf[0]? Should I start doing placement destruction, and do a placement new after that? What if the second step throws? God! So one important point is that reusing objects leads to easier code in many cases. Transition from a usual std::vector to a move-capable vector is really easy if we have an iterator move-wrapper (whose operator *() returns a rvalue-reference instead of an lvalue one) and if moved objects can be reused. The implementation just needs to wrap the copy operations between objects that were already in the container with move_iterator. The same happens if we have two arrays of strings in our application std::string str_array[SIZE]; //.. strings are filled std::string str_other_strings[SIZE * 2]; std::copy(move_iterator(&str_array[0] ,move_iterator(&str_array[SIZE] ,move_iterator(&str_other_strings[0]); //if move is implemented as swap(), str_array //strings still have memory //other operations... //This can lead to ZERO allocations if previous //strings had memory taken from the move-target for(int i = 0; i < SIZE; ++i){ str_array[0] += "prefix_"; str_array[0] += boost::lexical_cast(i); } So my points are: * reusing moved objects leads to easier code. * reusing moved objects might improve performance. * reusing has no impact with temporaries because they are going to be destroyed anyway. * the user can explicitly request resource liberation for moved objects or destroy them if he wants to be sure that resources were liberated and about bloat (it has no guarantee if the state of the moved objects is something like "destructor will be safely called"). Regards, Ion
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Ion Gaztañaga Sent: Monday, April 16, 2007 10:33 AM To: boost@lists.boost.org Subject: Re: [boost] [shared_ptr] dangerous implementation of moveconstructor
std::vector<T> myvect(...); //myvect's destructor is called, the object is not longer usable std::vector<T> myvect2(std::destructive_move(myvect)); myvect.resize(1000); <-- COMPILATION ERROR
That pretty much goes against normal C++ scoping rules (theyre not related here but from a readability pov, they are) and would be very confusing. In this code here: if(some_runtime_condition) { ...std::destructive_move(myvect)... } ... if(!some_runtime_condition && some_other_runtime_condition) { use_myvect(myvect); } It isn't easy for the compiler to help you. Well defined and standard-mandated semantics are better in the long run, even if its possible for the case you had above not be an error (should be a warning though!). The rule should be simple: After moving, the moved object (i.e., the argument to std::move) should be destructible. I don't think being assignable makes sense because that implies that a default constructor is sensible for T. I can imagine this is more intuitive C++ and is easier for compilers to implement. Thanks for listening (and discussing this very important topic!) Sohail
From: Sohail Somani
The rule should be simple:
After moving, the moved object (i.e., the argument to std::move) should be destructible.
Agreed so far.
I don't think being assignable makes sense because that implies that a default constructor is sensible for T.
If T supports operator =, I think it should be possible to assign TO an object of type T that has been moved from. I don't see how this is related to a default constructor.
Thanks for listening (and discussing this very important topic!)
Agreed. -- Martin Bonner Project Leader PI SHURLOK LTD Telephone: +44 1223 441434 / 203894 (direct) Fax: +44 1223 203999 Email: martin.bonner@pi-shurlok.com www.pi-shurlok.com
[mailto:boost-bounces@lists.boost.org] On Behalf Of Martin Bonner
From: Sohail Somani
The rule should be simple:
After moving, the moved object (i.e., the argument to std::move) should be destructible.
Agreed so far.
I don't think being assignable makes sense because that implies that a default constructor is sensible for T.
If T supports operator =, I think it should be possible to assign TO an object of type T that has been moved from.
I don't see how this is related to a default constructor.
Well if you do this: T a(std::move(some_other_T)); some_other_T = yet_another_T; Even if operator= is supported, some_other_T must(?) then be in some usable (but empty) state if you expect to assign to it. If its possible for T to be in a usable empty state, then conceivably, a default constructor should be possible. There is probably some rule of thumb here, just not sure what it is yet. Still, for generic code, I don't think you should expect to be able to reuse a moved object except for destructing it. Specific classes, maybe, but not as a general rule. Even still, I can't think of a case off-hand where assignment requires some previous state so maybe this is a moot point. Maybe for some really crazy overloading of operator=. Sohail
From Sohail Somani:
[mailto:boost-bounces@lists.boost.org] On Behalf Of Martin Bonner
From: Sohail Somani
The rule should be simple:
After moving, the moved object (i.e., the argument to std::move) should be destructible.
Agreed so far.
I don't think being assignable makes sense because that implies that a default constructor is sensible for T.
If T supports operator =, I think it should be possible to assign TO an object of type T that has been moved from.
I don't see how this is related to a default constructor.
Well if you do this:
T a(std::move(some_other_T)); some_other_T = yet_another_T;
Even if operator= is supported, some_other_T must(?) then be in some usable (but empty) state if you expect to assign to it. Usable in strictly limited ways. I wouldn't expect to be able to call any methods on it. (Unlike Ion and Joe.)
Empty? If you can only delete it, or assign to it, then whether it is "empty" or not is somewhat meaningless.
If its possible for T to be in a usable empty state, then conceivably, a default constructor should be possible. There is probably some rule of thumb here, just not sure what it is yet.
Hmm. I sort of see what you mean. It is often reasonable that the state of a moved from object is the same as the state of a default constructed object - but not always, and if I don't have a use-case for a
Still, for generic code, I don't think you should expect to be able to reuse a moved object except for destructing it. Specific classes, maybe, but not as a general rule. Quite.
Even still, I can't think of a case off-hand where assignment requires some previous state so maybe this is a moot point. Maybe for some really crazy overloading of operator=.
Oh that's easy! For example, smart pointers: if (this->p != null) { delete this->p; } The comparison with null is undefined behaviour if the pointer has been previously deleted, and if the memory has been subsequently reallocated it can have seriously bad effects. (Note, I am **NOT** saying that will happen with a moved from object - I am just giving an example where the behaviour of the assignment operator depends upon the state of the assigned to object). -- Martin Bonner Project Leader PI SHURLOK LTD Telephone: +44 1223 441434 / 203894 (direct) Fax: +44 1223 203999 Email: martin.bonner@pi-shurlok.com www.pi-shurlok.com
Sohail Somani wrote:
Still, for generic code, I don't think you should expect to be able to reuse a moved object except for destructing it. Specific classes, maybe, but not as a general rule.
Even still, I can't think of a case off-hand where assignment requires some previous state so maybe this is a moot point. Maybe for some really crazy overloading of operator=.
At a bare minimum you need to be able to destruct or assign to a moved object. For example, consider the code for inserting a value into the middle of an vector. If the vector doesn't need to be reallocated you would use the following algorithm: 1) Use the move constructor to move the last element of the vector to where end() currently points to. Note that this leaves a "hole" in the vector in what is now the second-to-last position. 2) Iterating backward, use move assignment to move the element immediately in front of the hole to the position of the hole, thus moving the hole back one. Continue doing this until the hole is in the position where you want to do your insertion. 3) Assign your new value to the position of the hole, thus filling the hole. Assuming no exceptions were thrown every element of the vector now has a determined value. Note that steps 2 and 3 above required assigning to an element that had previously been moved from. Joe Gottman
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Joe Gottman
Sohail Somani wrote:
Still, for generic code, I don't think you should expect to be able to reuse a moved object except for destructing it. Specific classes, maybe, but not as a general rule.
Even still, I can't think of a case off-hand where assignment requires some previous state so maybe this is a moot point. Maybe for some really crazy overloading of operator=.
At a bare minimum you need to be able to destruct or assign to a moved object. For example, consider the code for inserting a value into the middle of an vector. If the vector doesn't need to be reallocated you would use the following algorithm:
Good example. I think that's the canonical use of this feature. [A slight tangent follows] If the rule should then be: Moved objects should be destructible and move(?) assignable. How do you handle classes that have reference members? I was hoping that the compilers might be able to generate default move constructors like they are able to do for the other *structors but now I'm not sure what will happen in the context of references. It would be killer if I could upgrade to a C++0x compiler and all of a sudden my reallocations don't do deep copies. Apologies if its covered elsewhere. Sohail
My apologies. It was not my intent to start a mini-firestorm and then leave town for the next 10 days. ;-) On Apr 16, 2007, at 4:32 PM, Ion Gaztañaga wrote:
I'm terrible explaining my points.
I can relate. :-) There exists a small gap between what was voted into the WP last week regarding move semantics, and what my intent is. Below I attempt to explain my intent, and where that differs from what is in the WP, I will attempt to fix with defect reports. --- In general, std::types, when dealing with rvalue references which are overloaded with lvalue references, the std::code is allowed to assume that it is dealing with an actual temporary, and not a moved-from lvalue. Reference: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1858.html#23.1%20-%... paragraph 13:
-13- Those container member functions with rvalue-reference parameters may assume that the reference truly refers to an rvalue, and specifically is not a reference into the same container.
Example: template > class vector { ... iterator insert(iterator position, const T& x); iterator insert(iterator position, T&& x); ... }; Inside the insert overload taking a T&&, the code is allowed to assume that x has bound to a temporary. This means that the code does not have to check for the self-referencing case, and is thus faster. If a client moves an lvalue to the insert signature, the onus is on the client to make sure that all existing references to that lvalue promise not to notice (or care) that the lvalue has been moved from. void foo() { std::vector<A> v(10); v.insert(v.end(), std::move(v.front())); } The above is a run time error similar to: void foo() { std::vector<A> v(10); v.insert(v.end(), v.begin(), v.begin()+1); } (the latter is currently forbidden by 23.1.1, p4) --- Now let's look at the other side: void foo() { A a; std::vector<A> v; v.insert(v.end(), std::move(a)); // Here "a" is required to be in a valid state, but the value of "a" is unknown } The definition of "valid" is up to the author of A. At a minimum, generic code will need to destruct and/or assign "a" a new value. However the author of A is free to define as part of the class invariant: After an A is moved from, you can't call A::bar() I don't think that is a very good design myself. But I also don't think the standard should prohibit it. For std::types I do not want to see any such restrictions on moved- from values. For example if a vector gets moved from, I expect it to still be fully functional, just with an unknown state (but you can test the state with the existing interface, e.g. size(), capacity(), empty(), etc.), and set the state however you like. With perhaps a few exceptions, I do not want to see the value of a moved-from std::type specified. For example: std::string s1("123"); std::string s2(std::move(s1)); // value of s1 not reliable here. "123" and "" are two good guesses --- Originally I preferred vector move assignment as just swap(). However I've recently become convinced that this is not the best definition. I now prefer the semantics of clear(); swap();. This means that move assignment is O(N) instead of O(1). Ok Ion, take a deep breath and stay with me for just a minute longer. :-) The semantics of ~thread() is going to be cancel(); detach();. That is, if thread A is holding a std::thread referencing thread B, and thread C cancels thread A, as thread A's stack unwinds, it will execute b.~thread() which cancels B, but does not wait around for B to respond to the cancel. Thus canceling A will not hang waiting on B to finish up. Now consider vector<thread>: vector<thread> v1; ... vector<thread> v2; ... v1 = std::move(v2); After the move assign, I think it best that whatever threads v1 happened to previously refer to, are now busy canceling themselves, instead of continuing to run under v2's ownership. If you want the latter, you've got swap. Cost analysis: It isn't nearly as bad as it sounds. Promise!!! :-) First, for vector<type with trivial destructor>, clear() is O(1) in practice (or it should be). And clear() does not dump capacity, so the capacity gets reused via the swap. So we only have to worry about vector<type with non-trivial destructor>. Consider vector<vector<thread>>::insert. And we're going to insert a new vector<thread> at begin(). The case where there is insufficient capacity only uses move construction, and not move assignment. So assume there is sufficient capacity. In this case we first move construct *--end() into *end(). This move construction leaves a zero capacity vector<thread> at *--end() (though that value should not be guaranteed, there is really little else vector can do for move construction). The next step is: *(end()-1) = std::move(*(end()-2)); Now we already said that *(end()-1) is a zero capacity vector<thread> prior to this move assignment. Therefore when the move assignment clears it, that clear is a no-op. Then the states are swapped, making *(end()-2) a zero capacity vector (again, that state should not be guaranteed, but it is practical). Repeat: *(end()-2) = std::move(*(end()-3)); Again we are move assigning into a zero-capacity vector, so clear();swap(); and just swap(); are virtually identical sequences of instructions. This repeats all the way down to: *(begin()+1) = std::move(*begin()); leaving *begin() as a zero capacity vector<thread>. Then the outside vector<thread> is moved assigned into *begin(). The outside temporary vector<thread> is then a zero capacity vector and presumably destructs. Summary: For vector<vector<thread>>::insert, defining vector move assignment as clear()+swap() instead of just swap() has a nearly identical cost. There are no extra destructions. I've gone through the same analysis with vector::erase, and all sequence modifying algorithms in <algorithm> which make use of move semantics. During all of these generic algorithms, move assignment is always assigning to a source that has already been moved from. Thus "clearing" the source is a no-op. And I consider the container::insert/erase and <algorithm>'s as one of the biggest consumers of move semantics, and even more importantly, as typical use cases of move semantics. In general, if you are move assigning *to* something. You've probably already move assigned or move constructed *from* it. That being said, if you haven't already moved from the target, and the target is a std::container or other std::type which owns objects, I think a "clear" is prudent so that move assignment has the same semantics as copy assignment. Getting back to shared_ptr move assignment, I would like to see the target's reference count decremented if it is not already at 0 prior to the move assignment (just as in copy assignment - this is the "clear" part of the algorithm). I would also like to not see any *new* constraints placed on the source as a result of being moved from. And finally I do not see the need to specify the value of the source after the move. I would like vendors to have the freedom to implement shared_ptr move assignment exactly as they do shared_ptr copy assignment. If atomic operations can be avoided (for example) by assuming that the source is a temporary (under move assignment) then so much the better. -Howard
Howard Hinnant wrote:
On Apr 16, 2007, at 4:32 PM, Ion Gaztañaga wrote:
I'm terrible explaining my points.
I can relate. :-)
I'll try harder now ;-)
There exists a small gap between what was voted into the WP last week regarding move semantics, and what my intent is. Below I attempt to explain my intent, and where that differs from what is in the WP, I will attempt to fix with defect reports.
I haven't cached the differences between your intention and the WP. Are valid assignment/move-assignment for moved values required for types to be inserted in std containers?
[snip moving A to a container...]
The definition of "valid" is up to the author of A. At a minimum, generic code will need to destruct and/or assign "a" a new value. However the author of A is free to define as part of the class invariant:
After an A is moved from, you can't call A::bar()
I don't think that is a very good design myself. But I also don't think the standard should prohibit it.
I've been revising some classes which implement pseudo-move semantics in Interprocess and for unique resource owning classes (a shared memory object descriptor which is not copyable but movable) A::bar() would return error instead of crashing. Not a big advantage over crashing, but otherwise there is nothing to do, because the resource is unique. And these classes have the interesting "trivial destructor after move" trait, something we could not achieve with objects that still hold resources. It's a shame that the compiler can't automatically detect such classes to avoid calling destructors if they've been moved. std::vector would really appreciate it... ;-)
Originally I preferred vector move assignment as just swap(). However I've recently become convinced that this is not the best definition. I now prefer the semantics of clear(); swap();. This means that move assignment is O(N) instead of O(1). Ok Ion, take a deep breath and stay with me for just a minute longer. :-)
Holding my breath...
The semantics of ~thread() is going to be cancel(); detach();. That is, if thread A is holding a std::thread referencing thread B, and thread C cancels thread A, as thread A's stack unwinds, it will execute b.~thread() which cancels B, but does not wait around for B to respond to the cancel. Thus canceling A will not hang waiting on B to finish up.
[more good stuff]
I've been revising a bit the implementation of move semantics for Intrusive containers and I've also seen that there is no advantage if we are constructing a new value. However, my hope is that move semantics will be very successful and people will start using move semantics everywhere: class ObjectWithString { public: ///.. //We can assign from anything convertible to std::string template<class T> set_str(T &&convertible_to_str) { str_ = forward(str); } private: std::string str_; } ObjectWithString object_with_string; std::vector<ObjectWithString> object_vect; for(int i = 0; i < NUM; ++i){ str += "prefix_"; str.append(to_string(i)); str_vect[i].set_str(move(str)); } If target memory is deallocated with every move-assignment the complexity might be good in theory but the result is "my code calls delete/new every two steps". If strings are passed as lvalues, and the target has capacity, the copy assignment might be more efficient than the move assignment, because no memory is being deallocated/allocated (str is being reused in the loop). On the other hand, if memory is swapped to the outside world, we can avoid a lot of allocations, because str can reuse memory already present in the contained objects. Note that this is compatible with your clear() + swap() approach. If the standard does not guarantee this, my only hope is to use move construction hoping that the implementation optimizes this (although I bet that most implementation will swap the memory, specially if that's "extra officially" encouraged).
[vector thread example...]
I've just realized that I can end criticizing arguments that I've passionately defended before. In the GC debate I defended the need of deterministic destructors, something that I miss defending swap() as the implementation of the move assignment, because nobody really knows when the moved source is going to be destroyed. Your clear() + swap() proposal seems the answer. However, if the object to be move assigned is std::vector<std::string>, the call to destructors will deallocate all the strings. Maybe the implementations could just detect that vector is a container holding a value whose destructor has no "visible" side effects (well, deallocating memory: it's holding a container of values with trivial destructors). So move assignment for this: std::vector<std::vector<std::string> > can be quite heavy unless the implementation can detect that there is no need to call destructors. I imagine that unless the loop I've written or similar, the rvalue is going to be destroyed anyway, so maybe there is no big impact. Time will tell.
Getting back to shared_ptr move assignment, I would like to see the target's reference count decremented if it is not already at 0 prior to the move assignment (just as in copy assignment - this is the "clear" part of the algorithm). I would also like to not see any *new* constraints placed on the source as a result of being moved from. And finally I do not see the need to specify the value of the source after the move. I would like vendors to have the freedom to implement shared_ptr move assignment exactly as they do shared_ptr copy assignment. If atomic operations can be avoided (for example) by assuming that the source is a temporary (under move assignment) then so much the better.
shared_ptr can also optimize the trivial destructor case (or even std::vector<std::string> > case) but apart from avoiding the atomic operations it can also swap the heap allocated reference count (what happens with the deleter?) hoping someone can reuse it outside. After all, shared_ptr looks like a (special) container. Still breathless, Ion
Howard Hinnant wrote:
[snip]
I now prefer the semantics of clear(); swap();. This means that move assignment is O(N) instead of O(1). Ok Ion, take a deep breath and stay with me for just a minute longer. :-)
[snip]
First, for vector<type with trivial destructor>, clear() is O(1) in practice (or it should be). And clear() does not dump capacity, so the capacity gets reused via the swap. So we only have to worry about vector<type with non-trivial destructor>.
Right now I'm thinking about std::list and (unordered_)map/set. clear() does not sound very lightweight... ¿collateral damage? ;-) Regards, Ion
On Apr 24, 2007, at 1:45 PM, Ion Gaztañaga wrote:
Howard Hinnant wrote:
[snip]
I now prefer the semantics of clear(); swap();. This means that move assignment is O(N) instead of O(1). Ok Ion, take a deep breath and stay with me for just a minute longer. :-)
[snip]
First, for vector<type with trivial destructor>, clear() is O(1) in practice (or it should be). And clear() does not dump capacity, so the capacity gets reused via the swap. So we only have to worry about vector<type with non-trivial destructor>.
Right now I'm thinking about std::list and (unordered_)map/set. clear() does not sound very lightweight... ¿collateral damage? ;-)
I think list is manageable, but I haven't figured out the standardeeze for it yet. I'm thinking something like (untested): template <class T, class A> list<T,A>& list<T,A>::operator=(list&& x) { iterator i = begin(); iterator j = x.begin(); size_type nodes_to_splice = x.size(); for (; i != end() && j != x.end(); ++i, ++j, --nodes_to_splice) *i = std::move(*j); if (i != end()) erase(i, end()); else if (j != end()) splice(x, j, end(), nodes_to_splice); return *this; } I.e. this is O(this->size()). It recycles existing nodes, takes advantage of the element's move assignment (if it exists), and is O(1) if this->size() == 0 (and yes, I'm assuming size() is O(1) and I don't even want to get into that side topic ;-)). The above needs to be fixed up to support unequal allocators, most likely reverting to clear() + swap() in that case. Also know that Swappable is going to be optional for C++0X allocators. If the allocator is swappable, you can swap it with swap. If the allocator isn't swappable (and is unequal), one will have to revert to creating nodes in the target. For (unordered_)map/set recycling nodes may be more trouble than it is worth. And the only saving grace is that most of the time one move assigns, the target is already empty, and so the clear() is dirt cheap (which also helps in the list case). The basic philosophy is that for: a = std::move(b); For every element in "a" before the move, either the element is move assigned or destructed within the move assignment (thus achieving the deterministic resource management you mentioned in your other post). -Howard
Peter Dimov wrote:
Joe Gottman wrote:
I see that rvalue reference support has just been added to the shared_ptr template, and I think that there's a subtle bug in the implementation. It is implemented as follows:
shared_ptr( shared_ptr && r ): px( r.px ), pn() // never throws { pn.swap( r.pn ); }
The problem is that after the move constructor has been called the moved -from shared_ptr, r, is in a dangerously inconsistent state. Its has an empty shared count, but it contains a non-null pointer. Usually it should be either destructed or assigned to shortly after the move constructor is called, in which case all will be well. However, if it remains unchanged then there is the danger that someone might try to dereference it after r.px has been deleted. This, of course, could result in a hard-to-track access violation. To see what I mean, consider the following rather silly code:
shared_ptr<int> r(new int(1)); shared_ptr<int> s(std::move(r)); s.reset(); if (r) { //r.get() != 0, so this returns true cout << *r; // Uh-oh }
The problem with the above code does indeed exist, but it is not a bug in the implementation (let alone a subtle one) - in the sense that the implementation is deliberately written in the way it's written, to not provide a guarantee about the consistency of r after the move. You are right that we can clear r.px easily for shared_ptr, but it's more important to think about the general case: is the user allowed to assume anything about the state of an object after it has been moved from?
void f( T t1 ) { T t2( std::move( t1 ) ); // What happens if I use t1 here? }
Using t1 after the move looks like a programming error to me.
I disagree. Suppose we have a function foo(shared_ptr<int> &&p) that might or might not move from p. For instance, foo might be one of several potential consumers of the shared_ptr. In this case, having the move constructor automatically zero out p would be a nice way to let the client know that p was actually moved from. It would enable code like the following: shared_ptr<int> p(new int(1)); foo(move(p)); if (p) { // foo didn't want it, try the next potential consumer bar(move(p)); } else { return; // foo consumed our shared_ptr, so we are done. } Also, leaving the shared_ptr in an inconsistent state can cause intermittent crashes far away from where the move occurred. This is unfair to the person who will be debugging the crash, who may well be someone different from the person who wrote the code with the move statement. Joe Gottman
I disagree. Suppose we have a function foo(shared_ptr<int> &&p) that might or might not move from p. For instance, foo might be one of several potential consumers of the shared_ptr. In this case, having the move constructor automatically zero out p would be a nice way to let the client know that p was actually moved from. It would enable code like the following:
shared_ptr<int> p(new int(1)); foo(move(p)); if (p) { // foo didn't want it, try the next potential consumer bar(move(p)); } else { return; // foo consumed our shared_ptr, so we are done. }
Of course you can always write: shared_ptr<int> p(new int(1)); if( !foo(move(p)) ) // foo didn't want it, try the next potential consumer bar(move(p)); } else { return; // foo consumed our shared_ptr, so we are done. }
Also, leaving the shared_ptr in an inconsistent state can cause intermittent crashes far away from where the move occurred. This is unfair to the person who will be debugging the crash, who may well be someone different from the person who wrote the code with the move statement.
Saying that something is undefined behavior doesn't mean that we shouldn't provide debugging features to help detect ill-formed code. Emil Dotchevski
Joe Gottman wrote:
shared_ptr<int> p(new int(1)); foo(move(p)); if (p) { // foo didn't want it, try the next potential consumer bar(move(p)); } else { return; // foo consumed our shared_ptr, so we are done. }
An interesting pattern, thanks for the example. A bit of a circular logic here, since for this example to work reliably shared_ptr must clear the source of the move; therefore, if we don't specify it to clear the source, this example will not be valid. (It isn't in general; a raw pointer, for example, is not zeroed when moved from.) But it may well be a pattern that we decide to support. This implies an "overspecified" assignment, though; the straightforward swap doesn't clear the source.
participants (10)
-
Emil Dotchevski -
Felipe Magno de Almeida -
Greer, Joe -
Howard Hinnant -
Howard Hinnant -
Ion Gaztañaga -
Joe Gottman -
Martin Bonner -
Peter Dimov -
Sohail Somani