On Fri, Jan 25, 2013 at 10:21 AM, Dave Abrahams <dave@boostpro.com> wrote:
Yes. IIUC the question here is whether the invariant of variant [;-)] shall be weakened to accommodate efficient move semantics, thereby breaking some code, or not, at some cost (the specific costs to be incurred by various strategies presently under discussion).
I'm new to this list, so I won't be offended if you correct me on any rookie mistakes. Concerning the invariant of variant: Why not provide a specialization of boost::optional for variant, which supports move Semantics? Users who don't want their invariant harmed, can use boost::variant as is. Users who need to squeeze out performance could use an optional<variant> and would be explicitly aware of the new null state they introduced for this. Markus www.clean-cpp.org
On Tue, Jan 29, 2013 at 1:34 PM, Markus Klein <markus-klein@live.de> wrote:
On Fri, Jan 25, 2013 at 10:21 AM, Dave Abrahams <dave@boostpro.com> wrote:
Yes. IIUC the question here is whether the invariant of variant [;-)] shall be weakened to accommodate efficient move semantics, thereby breaking some code, or not, at some cost (the specific costs to be incurred by various strategies presently under discussion).
I'm new to this list, so I won't be offended if you correct me on any rookie mistakes. Concerning the invariant of variant: Why not provide a specialization of boost::optional for variant, which supports move Semantics? Users who don't want their invariant harmed, can use boost::variant as is. Users who need to squeeze out performance could use an optional<variant> and would be explicitly aware of the new null state they introduced for this.
Why I don't think that's a particularly good idea: - optional< variant<blah> > doesn't have the same interface as variant<blah>. - It's a lot of syntactic noise. - It isn't obvious that you're using optional< variant<blah> > primarily to enable move semantics. - We can still get proper move semantics for variant in most use cases without ever violating the never-empty guarantee. This is only ever an issue for a recursive variant which is not default-constructible. The fix is easy: prepend your typelist with boost::blank. Also, welcome to the list, and don't let the above shy you away from sharing ideas :) I just don't think specializing optional< variant<blah> > is better than the other alternatives. - Jeff
2013/1/30 Joel de Guzman <djowel@gmail.com>:
On 1/30/13 7:23 AM, Larry Evans wrote:
This discussion might be facilitated if Joel et al (sorry Joel, I don't mean to pick on you, I just mean the group arguing for introducing this "singular" post-move state) simply said "yes, we understand we're making a breaking change (by possibly introducing an additional state to variant that violates the never-empty guarantee), but we still think it's the most practical approach to introduce efficient move semantics to variant". I can jive with that but I think Paul's concerned that you (again, as a representative of the platform you're taking) don't appreciate that this is a breaking change to variant.
No, Jeff, that is wrong. We are not violating the semantics to variant. It's not about variant. It's about recursive_wrapper. I think people are confused with this. The variant's never-empty guarantee still holds.
The page:
http://www.boost.org/doc/libs/1_52_0/doc/html/variant/design.html#variant.de...
says:
variant may be viewed precisely as a union of exactly its bounded types
but having a singular-valued recursive_wrapper violates this view, because there's no way you can dereference a singular-valued recursive_wrapper to get at one of the bounded types.
That is actually a good point. I didn't think of it that way, but yeah, I can appreciate that. So, I think I am inclined to agree with Jeff now.
I think that this example is perfect for showing the benefits of nulled recursive wrapper. Watch the hands: union my_union { my_union u_; // Impossible to do int i_; }; Because we can not use field of type my_union in my_union we need to wrap it: union my_union { recursive_wrapper<my_union> u_; // Ok int i_; }; Now we just need to decide, what a recursive_wrapper is! Is it behave like a reference: // # 1 union my_union { my_union& u_; int i_; }; Or is it behave like a pointer: // # 2 union my_union { unique_ptr<my_union> u_; int i_; }; #1 is not what a recursive_wrapper is, because recursive_wrapper OWNS a value #2 is much closer to functionality of recursive_wrapper 2013/1/28 Joel de Guzman <djowel@gmail.com>:
(BTW, who is the current maintainer of variant? I don't see Itay and Eric here in this list anymore. I've invested heavily on variant and I am willing to be a maintainer of variant or be a co-maintainer with Antony Polukhin)
Have not seen them either. I also invested heavily on variant, so I can keep an eye on it, but 4 eyes are much better! Especially because of me and Joel invested in different parts of it :) 2013/1/30 Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung@gmail.com>:
- We can still get proper move semantics for variant in most use cases without ever violating the never-empty guarantee. This is only ever an issue for a recursive variant which is not default-constructible. The fix is easy: prepend your typelist with boost::blank.
It is already implemented (see 1.53 release notes for variant). Variant with recursive_wrapper is default constructible if its first parameter default constructible. -- Best regards, Antony Polukhin
On 01/30/13 04:58, Antony Polukhin wrote: [snip]
Now we just need to decide, what a recursive_wrapper is! Is it behave like a reference:
// # 1 union my_union { my_union& u_; int i_; };
Or is it behave like a pointer:
// # 2 union my_union { unique_ptr<my_union> u_; int i_; };
#1 is not what a recursive_wrapper is, because recursive_wrapper OWNS a value #2 is much closer to functionality of recursive_wrapper
[snip] So #2 would be like: int OR int* OR int** . . . int********.... Is that right?
On 01/30/13 08:55, Larry Evans wrote:
On 01/30/13 04:58, Antony Polukhin wrote: [snip]
Now we just need to decide, what a recursive_wrapper is! Is it behave like a reference:
// # 1 union my_union { my_union& u_; int i_; };
Or is it behave like a pointer:
// # 2 union my_union { unique_ptr<my_union> u_; int i_; };
#1 is not what a recursive_wrapper is, because recursive_wrapper OWNS a value #2 is much closer to functionality of recursive_wrapper
[snip] So #2 would be like:
int OR int* OR int** . . . int********....
Is that right?
I think it is based on the output: vec_us.size()=0 vec_us[0]= :te[0]=0 vec_us[1]= :te[0]=1 :te[1]=0 vec_us[2]= :te[0]=1 :te[1]=1 :te[2]=0 vec_us.size()=3 from the attached. -regards, Larry
On Wed, Jan 30, 2013 at 12:58 PM, Antony Polukhin <antoshkka@gmail.com> wrote:
I think that this example is perfect for showing the benefits of nulled recursive wrapper. Watch the hands:
union my_union { my_union u_; // Impossible to do int i_; };
Because we can not use field of type my_union in my_union we need to wrap it:
union my_union { recursive_wrapper<my_union> u_; // Ok int i_; };
Now we just need to decide, what a recursive_wrapper is! Is it behave like a reference:
// # 1 union my_union { my_union& u_; int i_; };
Or is it behave like a pointer:
// # 2 union my_union { unique_ptr<my_union> u_; int i_; };
#1 is not what a recursive_wrapper is, because recursive_wrapper OWNS a value #2 is much closer to functionality of recursive_wrapper
Neither of these are models of what recursive_wrapper is. It's not a pointer and it's not a reference. A unique_ptr owns an object, not a value. It can own different objects or nothing at all during its lifetime. A reference is an alias for an object. A recursive_wrapper *is* the object it wraps and its value *is* the object's value - it doesn't own anything else or have any other visible state. The fact that it has its storage allocated on the heap is an implementation detail. The point is simply to allow recursive_wrapper<T> to be a complete type even when T isn't. A variant that contains a recursive_wrapper<T> behaves exactly like a variant that contains a T, except that T can be a recursive type - that's all. And this is exactly why it shouldn't have different semantics - move or otherwise. If you want the semantics offered by unique_ptr, shared_ptr, "copy_ptr", reference_wrapper, optional or anything else - by all means, use that! -- Paul Smith
2013/1/30 Paul Smith <pl.smith.mail@gmail.com>:
On Wed, Jan 30, 2013 at 12:58 PM, Antony Polukhin <antoshkka@gmail.com> wrote:
I think that this example is perfect for showing the benefits of nulled recursive wrapper. Watch the hands:
union my_union { my_union u_; // Impossible to do int i_; };
Because we can not use field of type my_union in my_union we need to wrap it:
union my_union { recursive_wrapper<my_union> u_; // Ok int i_; };
Now we just need to decide, what a recursive_wrapper is! Is it behave like a reference:
// # 1 union my_union { my_union& u_; int i_; };
Or is it behave like a pointer:
// # 2 union my_union { unique_ptr<my_union> u_; int i_; };
#1 is not what a recursive_wrapper is, because recursive_wrapper OWNS a value #2 is much closer to functionality of recursive_wrapper
Neither of these are models of what recursive_wrapper is. It's not a pointer and it's not a reference. A unique_ptr owns an object, not a value. It can own different objects or nothing at all during its lifetime. A reference is an alias for an object. A recursive_wrapper *is* the object it wraps and its value *is* the object's value - it doesn't own anything else or have any other visible state. The fact that it has its storage allocated on the heap is an implementation detail. The point is simply to allow recursive_wrapper<T> to be a complete type even when T isn't.
A variant that contains a recursive_wrapper<T> behaves exactly like a variant that contains a T, except that T can be a recursive type - that's all. And this is exactly why it shouldn't have different semantics - move or otherwise. If you want the semantics offered by unique_ptr, shared_ptr, "copy_ptr", reference_wrapper, optional or anything else - by all means, use that!
From theoretical point of view you are absolutely correct, and my example is lame. Moreover, current implementation of move assignment and move constructors for recursive_wrapper were implemented to model that behavior.
But I do understand Joel's efforts to make it faster. Just look at the variants assign implementation for type T and imagine that T is a recursive_wrapper: void move_assign(T&& rhs) { ... // heap allocation in move constructor of recursive_wrapper variant temp( detail::variant::move(rhs) ); // heap allocation in move constructor of recursive_wrapper // Potential call to less effective move_assign implementation if // variant does not have fallback_type (+1 heap allocation and deallocation) variant_assign( detail::variant::move(temp) ); ... // heap deallocation in destructor of recursive_wrapper } Allowing destructive move constructor for recursive_wrapper will make variant at least 3 times faster. Leaving recursive_wrapper as is will provoke users to use a really slow implementation. Unique_ptr and other types can not be used as a drop in replacement for recursive_wrapper. May be we shall deprecate recursive_wrapper and add recursive_ptr/nullable_recursive_wrapper class, that implements destructive move constructor? It does not break recursive_wrapper invariants,but adds a class with different invariants. -- Best regards, Antony Polukhin
On Thu, Jan 31, 2013 at 9:24 AM, Antony Polukhin <antoshkka@gmail.com> wrote:
From theoretical point of view you are absolutely correct, and my example is lame. Moreover, current implementation of move assignment and move constructors for recursive_wrapper were implemented to model that behavior.
Just pointing out that move assignment is not affected by this discussion. Everything is already allocated so it's as efficient as a pointer swap.
But I do understand Joel's efforts to make it faster.
[snip]
Allowing destructive move constructor for recursive_wrapper will make variant at least 3 times faster.
Oh, I never said otherwise, and I definitely sympathize with the desire to make it faster :-) What I'm saying is that this sort of tradeoff was taken into account when move-semantics were designed, and it's awkward to retroactively go against that.
Leaving recursive_wrapper as is will provoke users to use a really slow implementation.
Well, it's not like the introduction of move semantics made existing code slower all of the sudden :-)
Unique_ptr and other types can not be used as a drop in replacement for recursive_wrapper.
That's right, although since they have different semantics, it's not necessarily a bad thing.
May be we shall deprecate recursive_wrapper and add recursive_ptr/nullable_recursive_wrapper class, that implements destructive move constructor? It does not break recursive_wrapper invariants,but adds a class with different invariants.
I don't think we should deprecate anything. But adding a type with different semantics (in addition to option III which is always a good idea) is definitely far better than changing recursive_wrapper. Let each user pick their own poison. -- Paul Smith
on Thu Jan 31 2013, Paul Smith <pl.smith.mail-AT-gmail.com> wrote:
On Thu, Jan 31, 2013 at 9:24 AM, Antony Polukhin <antoshkka@gmail.com> wrote:
From theoretical point of view you are absolutely correct, and my example is lame. Moreover, current implementation of move assignment and move constructors for recursive_wrapper were implemented to model that behavior.
Just pointing out that move assignment is not affected by this discussion. Everything is already allocated so it's as efficient as a pointer swap.
Actually the correct semantics of move assignment is the same as "swap + clear" if there's an empty state. See http://cpp-next.com/archive/2009/09/your-next-assignment/ I recommend reading the whole article. -- Dave Abrahams BoostPro Computing Software Development Training http://www.boostpro.com Clang/LLVM/EDG Compilers C++ Boost
2013/1/31 Paul Smith <pl.smith.mail@gmail.com>:
On Thu, Jan 31, 2013 at 9:24 AM, Antony Polukhin <antoshkka@gmail.com> wrote:
From theoretical point of view you are absolutely correct, and my example is lame. Moreover, current implementation of move assignment and move constructors for recursive_wrapper were implemented to model that behavior.
Just pointing out that move assignment is not affected by this discussion. Everything is already allocated so it's as efficient as a pointer swap.
Can not agree (variant makes some additional manipulations to guarantee non emptyness): void move_assign(recursive_wrapper<T>&& rhs) { ... // heap allocation in move constructor of recursive_wrapper // can be optimized away (see #7960) variant temp( detail::variant::move(rhs) ); // *this stores type different from recursive_wrapper<T>, // so it another call to move constructor of recursive_wrapper // will be made // Potential call to less effective move_assign implementation if // variant does not have fallback_type (+1 heap allocation and deallocation) variant_assign( detail::variant::move(temp) ); ... // heap deallocation in destructor of recursive_wrapper } With recursive_ptr this would be: void move_assign(recursive_ptr<T>&& rhs) { ... // swap ptrs // can be optimized away (see #7960) variant temp( detail::variant::move(rhs) ); // recursive_ptr move constructor does not throw, so // variant will use a fastest possible move assignment implementation // *this stores type different from recursive_wrapper<T>, // so it calls to move constructor of recursive_ptr // => swap ptrs variant_assign( detail::variant::move(temp) ); ... // destructors of temporaries will call delete on nullptrs // Whole function will be noexcept => variant can be move // assigned in STL containers (containers will use copy-assignments, // if this function can throw) } With recursive_ptr it is as efficient, as pointers swap! With recursive_wrapper it is multiple times slower. 2013/2/1 Dave Abrahams <dave@boostpro.com>:
on Thu Jan 31 2013, Paul Smith <pl.smith.mail-AT-gmail.com> wrote:
On Thu, Jan 31, 2013 at 9:24 AM, Antony Polukhin <antoshkka@gmail.com> wrote:
From theoretical point of view you are absolutely correct, and my example is lame. Moreover, current implementation of move assignment and move constructors for recursive_wrapper were implemented to model that behavior.
Just pointing out that move assignment is not affected by this discussion. Everything is already allocated so it's as efficient as a pointer swap.
Actually the correct semantics of move assignment is the same as "swap + clear" if there's an empty state. See http://cpp-next.com/archive/2009/09/your-next-assignment/
I recommend reading the whole article.
Oops, if move assignment shall be equal to "swap + clear", then the current implementations of recursive_wrappers move assign must be fixed (it just swaps). -- Best regards, Antony Polukhin
On Fri, Feb 1, 2013 at 8:37 AM, Antony Polukhin <antoshkka@gmail.com> wrote:
2013/1/31 Paul Smith <pl.smith.mail@gmail.com>:
On Thu, Jan 31, 2013 at 9:24 AM, Antony Polukhin <antoshkka@gmail.com> wrote:
From theoretical point of view you are absolutely correct, and my example is lame. Moreover, current implementation of move assignment and move constructors for recursive_wrapper were implemented to model that behavior.
Just pointing out that move assignment is not affected by this discussion. Everything is already allocated so it's as efficient as a pointer swap.
Can not agree (variant makes some additional manipulations to guarantee non emptyness):
I meant move-assignment of recursive_wrapper, not variant. It was never under discussion AFAICT. Sorry if it wasn't clear.
void move_assign(recursive_wrapper<T>&& rhs) { ... // heap allocation in move constructor of recursive_wrapper // can be optimized away (see #7960) variant temp( detail::variant::move(rhs) );
// *this stores type different from recursive_wrapper<T>, // so it another call to move constructor of recursive_wrapper // will be made // Potential call to less effective move_assign implementation if // variant does not have fallback_type (+1 heap allocation and deallocation) variant_assign( detail::variant::move(temp) ); ... // heap deallocation in destructor of recursive_wrapper }
With recursive_ptr this would be:
void move_assign(recursive_ptr<T>&& rhs) { ... // swap ptrs // can be optimized away (see #7960) variant temp( detail::variant::move(rhs) );
// recursive_ptr move constructor does not throw, so // variant will use a fastest possible move assignment implementation // *this stores type different from recursive_wrapper<T>, // so it calls to move constructor of recursive_ptr // => swap ptrs variant_assign( detail::variant::move(temp) );
... // destructors of temporaries will call delete on nullptrs
// Whole function will be noexcept => variant can be move // assigned in STL containers (containers will use copy-assignments, // if this function can throw) }
With recursive_ptr it is as efficient, as pointers swap! With recursive_wrapper it is multiple times slower.
IIUC you are talking about a scenario where the user assigns a recursive_wrapper to a variant directly (i.e. some_variant = some_recursive_wrapper_T). But this is ill-formed anyway - you can only assign an object of the recursive_wrapper's underlying type (i.e. some_variant = some_T). However, there are other scenarios which you can optimize if you're up for some extra work. When you need to back up a recursive_wrapper, there's no need to move-construct a temporary recursive_wrapper. Just copy and clear its pointer. Destroy the recursive_wrapper. Do the assignment. If it succeeds, delete the pointer. If it fails, reconstruct a recursive_wrapper using that pointer (have it take ownership over the existing object). And, ofcourse, Peter's optimization is equally viable for move-assignment as it is for move-construction.
2013/2/1 Dave Abrahams <dave@boostpro.com>:
on Thu Jan 31 2013, Paul Smith <pl.smith.mail-AT-gmail.com> wrote:
On Thu, Jan 31, 2013 at 9:24 AM, Antony Polukhin <antoshkka@gmail.com> wrote:
From theoretical point of view you are absolutely correct, and my example is lame. Moreover, current implementation of move assignment and move constructors for recursive_wrapper were implemented to model that behavior.
Just pointing out that move assignment is not affected by this discussion. Everything is already allocated so it's as efficient as a pointer swap.
Actually the correct semantics of move assignment is the same as "swap + clear" if there's an empty state. See http://cpp-next.com/archive/2009/09/your-next-assignment/
I recommend reading the whole article.
Oops, if move assignment shall be equal to "swap + clear", then the current implementations of recursive_wrappers move assign must be fixed (it just swaps).
Except that recursive_wrapper doesn't have "clear". The most sensible thing to do, if you want a truely "interference-free" move assignment, is to propagate it down to the underlying instance (i.e. lhs.get() = move(rhs.get()) ). Note that this can result in a copy. That's up to you. -- Paul Smith
On 01/30/13 00:32, Jeffrey Lee Hellrung, Jr. wrote:
On Tue, Jan 29, 2013 at 1:34 PM, Markus Klein <markus-klein@live.de> wrote:
On Fri, Jan 25, 2013 at 10:21 AM, Dave Abrahams <dave@boostpro.com> wrote:
Yes. IIUC the question here is whether the invariant of variant [;-)] shall be weakened to accommodate efficient move semantics, thereby breaking some code, or not, at some cost (the specific costs to be incurred by various strategies presently under discussion).
I'm new to this list, so I won't be offended if you correct me on any rookie mistakes. Concerning the invariant of variant: Why not provide a specialization of boost::optional for variant, which supports move Semantics? Users who don't want their invariant harmed, can use boost::variant as is. Users who need to squeeze out performance could use an optional<variant> and would be explicitly aware of the new null state they introduced for this.
Why I don't think that's a particularly good idea: - optional< variant<blah> > doesn't have the same interface as variant<blah>. - It's a lot of syntactic noise. - It isn't obvious that you're using optional< variant<blah> > primarily to enable move semantics. - We can still get proper move semantics for variant in most use cases without ever violating the never-empty guarantee. This is only ever an issue for a recursive variant which is not default-constructible. The fix is easy: prepend your typelist with boost::blank.
Hmm... Just brainstorming here: What about deriving the current variant from a new class, variant_core, which didn't have all the TMP used by the current variant for handling recursion( for example, look at all the TMP described here: http://www.boost.org/doc/libs/1_52_0/doc/html/boost/make_recursive_variant.h... ). Also, variant_core might not even need to have a never-empty guarantee if variant_core.which() is allowed to return some value indicating empty. IOW, variant_core would have *less* constraints than variant which seems consistent with the idea that a base class has *less* constraints than the derived class (where constraint here means either more member variables or functions or more specific virtual functions). Thoughts? -regards, Larry
On We, Jan 30, 2013 at 07:33 AM, Jeffrey Lee Hellrung, Jr. <jeffrey.hellrung@gmail.com> wrote:
Also, welcome to the list, and don't let the above shy you away from sharing ideas :) I just don't think specializing optional< variant<blah> > is better than the other alternatives.
- Jeff
Thanks, for your clarification. Don't worry about shying me away from sharing ideas, I joined this list to improve and learn. Markus www.clean-cpp.org
participants (6)
-
Antony Polukhin -
Dave Abrahams -
Jeffrey Lee Hellrung, Jr. -
Larry Evans -
Markus Klein -
Paul Smith