Boost C++ Libraries: Ticket #7718: Basic rvalue and C++11 support (part 2)

Antony Polukhin — Thu, 22 Nov 2012 17:52:28 GMT

'variant_reference_test' currently fails with this patch.

attachment set

Antony Polukhin — Mon, 26 Nov 2012 19:31:44 GMT

attachment → rvalues2.patch

Antony Polukhin — Mon, 26 Nov 2012 19:33:21 GMT

Now compiles and passes 'variant_reference_test', but sigfaults at 'test3'

attachment set

Antony Polukhin — Mon, 26 Nov 2012 19:35:06 GMT

attachment → rvalue_test.cpp

Updated tests (now tests variant usage with move-only containers)

Antony Polukhin — Wed, 28 Nov 2012 19:20:21 GMT

(In [81617]) Basic rvalues and C++11 support part 2 (refs #7718 , all bugs from patch were fixed)

Antony Polukhin — Sat, 01 Dec 2012 15:32:11 GMT

(In [81652]) Refs #7718 : Workaroung GCC-4.7.2 internal compiler error More functions marked with BOOST_NOEXCEPT Added move constructors and move assignment operators to recursive_wrapper

status changed; resolution set

Antony Polukhin — Sat, 08 Dec 2012 15:44:20 GMT

status new → closed
resolution → fixed

(In [81793]) Merge variant from trunk:

Fix #7718 (move constructor from template type added)
More tests and minor bugfixes
Deprecated macros replaced with new ones (thanks to Marshall Clow)

status changed; resolution deleted

Joel de Guzman — Sun, 06 Jan 2013 01:39:33 GMT

status closed → reopened
resolution fixed

Hi,

I just looked at the current state of variant and noticed that the implementation of recursive_variant's move ctor seems to be not as optimal as I hoped. The current implementation as written is:

recursive_wrapper<T>::recursive_wrapper(recursive_wrapper&& operand)

: p_(new T( detail::variant::move(operand.get()) ))

{ }

Unless I am mistaken, I think the heap allocation is not needed and the target should simply grab the pointer and mark the source pointer as 0 (with additional checks for 0 in the dtor):

template <typename T> recursive_wrapper<T>::recursive_wrapper(recursive_wrapper&& operand)

: p_(operand.release())

{ }

template <typename T> T* recursive_wrapper<T>::release() {

T* ptr = p_; p_ = 0; return ptr;

}

template <typename T> recursive_wrapper<T>::~recursive_wrapper() {

if (p_)

boost::checked_delete(p_);

}

The tests are running just fine (tested with gcc, msvc) with this (more optimal) implementation. I also run the Spirit test suite (Spirit makes heavy use of variant).

Thoughts? I can commit this patch if it is acceptable.

anonymous — Sun, 06 Jan 2013 23:50:15 GMT

Update. Just checked, the check for 0 is not needed. 0 is valid for checked_delete just like plain delete.

status, milestone changed; resolution set

Antony Polukhin — Sun, 20 Jan 2013 12:05:12 GMT

status reopened → closed
resolution → fixed
milestone To Be Determined → Boost 1.53.0

This issue was discussed in mainling lists. If in short we have to choose between thre solutions:
1) leave as is (slow move construction)
2) allow empty state (fast, but breaks users code and variant guarantees)
3) after move, do lazy default construction of value on request (fast, but adds default construction requirement for type and functions get() and get_ptr() may throw)

There were more votes for solution 1.

status changed; resolution deleted

Joel de Guzman — Sun, 20 Jan 2013 15:26:56 GMT

status closed → reopened
resolution fixed

There is no such vote! 2 is the current consensus, FYI. I will reopen this. This is not a closed issue, not especially the way you concluded it to be.

Joel de Guzman — Sun, 20 Jan 2013 15:29:49 GMT

BTW, you are wrong about 2. The way Peter Dimov outlines the solution does not break users code and variant guarantees. Have you read Peter Dimov's solution?

Joel de Guzman — Sun, 20 Jan 2013 15:32:00 GMT

Let me quote in case you missed it:

On 1/11/13 11:02 PM, Paul Smith wrote:

On Fri, Jan 11, 2013 at 4:18 PM, Peter Dimov <lists@…> wrote:

If the variant could be empty, or equivalently, if the variant always contained a type that can be reliably default-constructed (without an exception) such as int, the problems with assignment (both copy- and move-) and with move construction do not occur, because the target can be left holding the int.

So, one option is to enable move only in this case.

That's the first constructive solution so far. Something like:

template <typename T> struct is_legitimate_move_target specialize me

: has_trivial_constructor<T> {};

Paul, I agree!

Peter, I like the direction this is heading to. I really appreciate your interest in this.

Antony Polukhin — Sun, 20 Jan 2013 16:04:17 GMT

Sometimes I really miss a smiley that hits its head to the wall...

Variant is not a recursive_wrapper, recursive_wrapper is not a variant. recursive_wrapper may be used without a variant. recursive_wrapper currently can not hold an empty state. All the solutions above (1, 2 and 3) are for recursive_wrapper only.

Please, refer to the sources and documentation of variant. There you can find that solution of Peter Dimov already implemented...

If you have some other ideas for optimizing variant, please tell me about them short and clear. Otherwise, please close the ticket.

Joel de Guzman — Mon, 21 Jan 2013 00:31:03 GMT

:-) There you go (smiley). I'm sorry if I overreacted. This issue is very important for me as I've invested heavily on variant and I expect an optimal solution to this problem.

I know the code of variant and recursive_variant. This patch is about variant. recursive_wrapper happens to be an integral part of variant. No, the current code does not implement Peter Dimov's suggestion about move yet. If you think it does, then please point me to the location where this is implemented.

The idea is simplified with Peter's note:

<quote>

No, I'm suggesting that move (in the presence of recursive_wrappers) can be enabled only when there is at least one type that is nothrow-default-constructible, regardless of whether it's current.

typedef variant<int, recursive_wrapper<foo>> V;

V v1( std::move(v2) );

This move-constructs v1 from v2 and leaves int() into v2.

</quote>

So, this is a special case handling for recursive_variant. Depending on the implementation, there might be a friend relationship with variant in recursive_wrapper, allowing it to grab its contents and place it in the destination.

Note: I'll just check the the first type. Variant's design somehow makes the first type important. It's the one that's default constructed and it's (almost always) a nothrow-default-constructible type.

Tell me if you need help in implementing this. I know my way around variant.

Antony Polukhin — Mon, 21 Jan 2013 06:29:28 GMT

Now I've got the idea :-) . Yes, it is not currently implemented and will give a good speed boost.
But in example above, won't the user be confused by v2 holding an int (instead of recursive_wrapper)? This proposal looks not much better than the first proposal, but requires more code to implement and adds 'friend' relationship (which is not nice).

Maybe a more correct solution would be to create an additional class nullable_recursive_wrapper/lazy_recursive_wrapper, and possibly mark recursive_wrapper as a deprecated one? Or just use an unique_ptr/shared_ptr instead of it?

Joel de Guzman — Mon, 21 Jan 2013 06:46:11 GMT

No. As I said in the mailing list, this should happen only in the 0.0000001% of the cases. In 99.9999999% of the cases, when you move something, the next thing that will happen is that it will be destructed. Please read the extensive exchange on this matter in the list. Only in very rare occasions (dare I say reckless cases) will someone want to do something on a moved-from object after a move. In that case, documentation should be sufficient to make this clear.

Joel de Guzman — Mon, 21 Jan 2013 06:58:53 GMT

BTW, that "No" is in reply to "won't the user be confused by v2 holding an int (instead of recursive_wrapper)?".

Perhaps there's a way to implement it without friend access, but I'm not sure. Anyway, the extra code is mostly TMP code for checking the the "blank" type.

nullable_recursive_wrapper is a good idea, but there's this extra check for null on all access that makes it less optimal. And that null check will be there to make the 0.0000001% of the cases happy. I don't know what you mean by lazy_recursive_wrapper. Same thing? As for unique/shared_ptr, AFAICT, they won't work as plug-in replacements.

Antony Polukhin — Mon, 21 Jan 2013 08:10:27 GMT

First of all, I also dislike that 'new' call in move constructor, but I just do not see a better solution. Let me explain:

Replying to djowel:

BTW, that "No" is in reply to "won't the user be confused by v2 holding an int (instead of recursive_wrapper)?".

Perhaps there's a way to implement it without friend access, but I'm not sure. Anyway, the extra code is mostly TMP code for checking the the "blank" type.

nullable_recursive_wrapper is a good idea, but there's this extra check for null on all access that makes it less optimal. And that null check will be there to make the 0.0000001% of the cases happy.

I'm trying to point, that solution that makes variant change its internal type is as good/bad for user, as a solution with nulling the pointer of recursive_wrapper. But nulling the pointer is much more easy to implement.

Here is some comparison of solutions (as I see it):

Nulling pointer after move constructor:
1) fast and efficient
2) triggers an assert when user tries to reuse moved object
3) must have a BOOST_ASSERT in get_pointer() finction
4) easy to implement
5) optimization will be used even if varinat has no type with trivial default constructor

Make varinat change its internal type:
1) fast and efficient
2) obscures user, when he tries to reuse moved object
3) requires a few more assignments in variant for which_ and maybe for trivial type construction
4) hard to implement
5) optimization will be used only if varinat has no type with trivial default constructor

I don't know what you mean by lazy_recursive_wrapper. Same thing?

It is an implementation, that after move does a lazy default construction of value on request.

Joel de Guzman — Mon, 21 Jan 2013 12:17:25 GMT

To be honest, I still prefer nulling the pointer. However, people seem to agree that that will ultimately place a precondition on recursive_variant (which is not good on extremely rare cases). Me? I don't care much about that. IMO, it's just a matter of documentation that people should simply not use a moved-from object.

The solution Peter suggested is a compromise. You do not need any asserts (which is present only on debug builds) and the variant's never-empty guarantee is not violated. If you are not happy with it, then you can probably ask for a vote in the Boost list. I'd personally vote for nulling the pointer. I'm sure many will too.

Bottom line: Either way is fine by me. I don't care which way we choose as long as we don't choose the "leave it as is" route.

Antony Polukhin — Mon, 21 Jan 2013 12:49:55 GMT

Replying to djowel:

To be honest, I still prefer nulling the pointer.

Nulling a pointer looks like a less ugliest solution. I`ll start a vote in the Boost list (and hope this time, nulling a pointer will win).

Antony Polukhin — Thu, 02 May 2013 08:39:37 GMT

(In [84104]) Update docs of Boost.Variant. Add advice about recursive_wrapper performance (refs #7718)

Antony Polukhin — Thu, 02 May 2013 09:12:23 GMT

As a result of discussion at mailing list - adding an empty state to recursive_wrapper is not a good idea (unfortunately). Updated documentation contains note about that and an advice for achieving better performance.

status changed; resolution set

Antony Polukhin — Thu, 02 May 2013 09:58:58 GMT

status reopened → closed
resolution → fixed

(In [84105]) Merge from trunk:

Update docs of Boost.Variant. Add advice about recursive_wrapper performance (fixes #7718)