Base recursive_wrapper implementation on std::unique_ptr

[tomilov]

It is simpler to design recursive_wrapper as "wrapper" over ready-to-use to RAII std::unique_ptr. Just add value semantics (example).

[joto]

If I understand correctly, recursive_wrapper was implemented specifically because it was faster than using unique_ptr. Building recursive_wrapper on top of unique_ptr would defeat that purpose. On the other hand if the recursive_wrapper implementation was incomplete, that's not good either

@artemp can you shed some light on this?

One other thing to keep in mind: The implementation of recursive_wrapper was basically taken wholesale from boost, just ported to C++11. Keeping compatibility with boost is one of our goals here.

[tomilov]

I always thought that the use of the std::unique_ptr does not lead to any run-time performance degradation. It is as simple as possible, I sure. Keeping compatibility with boost in sense of immutability of interface (as opposite to implementation) should be sufficient, is not that so?

[artemp]

One other thing to keep in mind: The implementation of recursive_wrapper was basically taken wholesale from boost, just ported to C++11. Keeping compatibility with boost is one of our goals here.

Correct ^ . Our recursive_wrapper as complete as boost one in this regard.

If we can alias std::unique_ptr to recursive_wrapper and performance is not an issue than, yes, by all means lets do it. Not a priority for https://github.com/mapbox/variant/milestones/1.1.0 though.
/cc @joto @tomilov @lightmare

[artemp]

Just reading #50 - perhaps this should go into 1.1.0 it we have a consensus ?
/cc @joto @tomilov @lightmare

[lightmare]

👍 - and as for throwing destructors, they're such a dark matter that I probably shouldn't have added any noexcept(something complex) to variant destructor in the first place. Just require that alternatives have non-throwing destructors and be done with it.

[joto]

Could we keep the discussion in this issue to the question it was started with? It is hard enough to keep track of all the different problems we have as it is.

@artemp what do you refer to in the sentence "perhaps this should go into 1.1.0"?

[artemp]

@joto - I referred to implementing recursive_wrapper as an alias to or based on std::unique_ptr in 1.1.0
(https://github.com/mapbox/variant/milestones/1.1.0).

[cbeck88]

I think boost::recursive_wrapper is not interchangeable with std::unique_ptr.

The difference has to do with how move works and what the empty state is.

A std::unique_ptr is permitted to be vacant. Default constructing it puts it in the empty state. And moving it, simply moves the pointer, leaving the moved from object in the empty state. So it's very fast and requires no pointer dereferences.

A boost::recursive_wrapper<T> is never permitted to be vacant. Default constructing it, default constructs an instance of T on the heap. Moving it, creates a new dynamic allocation and move constructs from the T value -- it's not simply a pointer move. This is necessary for boost::variant because boost::variant is strictly never empty. If boost::recursive_wrapper can move and be left in an empty state, it would mean that visiting a boost::variant after it is moved from can be UB, since its interface pierces the recursive_wrapper transparently to the user.

If mapbox::variant works like std::variant and legitimately has and supports an empty state, then this might not be an issue -- probably you want the pointer move for efficiency. But I think you would want to explicitly set the moved-from variant to empty, not leave it holding a dead unique pointer, so that if it is visited after that, you get an exception rather than null dereference.

I guess the other reason I would advocate against basing things on std::unique_ptr just because is,
variant is a pretty simple concept. In my implementation the only standard headers I bring in for the core definition are <cstddef>, <new>, <type_traits>, <utility>. On gcc the total preprocessed source for a trivial variant program is about 4000 lines of code. By contrast, bringing in one of the heavier standard library components like iostream, memory, or functional jumps you up to about 25kloc. Sure std::unique_ptr is very small and simple, but <memory> also brings in std::shared_ptr, the whole <atomic> header, etc. etc. I guess if you only need <memory> for std::unique_ptr, and you need to modify the unique_ptr anyways to do what you want, then why bother, at least that's the way I looked at it.

[tomilov]

@cbeck88 recursive_wrapper is wrapper around pointer (or reference) — this is essential thing for its implementation (due to wrapped type's incompleteness at point of instantiation of recursive_wrapper). Moreover, it is a pointer to object, which in turn placed (undoubtedly) on the heap. Using explicit new operator often considered as a bad practice. Therefore I can conclude using <memory> cannot be avoided, isn't it? I think <new> should never be encountered in the code for purposes to allocate some raw memory (just only for placement operator new or overloading, redefinition or something else less straitforward).

In the starting comment I gave the link to possible implementation of recursive_wrapper based on std::unique_ptr. Its emptiness is algoritmically prohibited into the very variant's logics. And I sure it is the best place for it, because (variant's) never-empty-guarantee does not apply to recursive_wrapper.

BTW I sure variant cannot be as simple as you mentioned above. It is quite entangled being.

[cbeck88]

@tomilov: Yeah, I mostly agree with you. But I think it's different for library code perhaps. If I only have one explicit new (which isn't placement new) in my whole lib, for recursive_wrapper, it's ok in my book if it will improve compile times.

I wish that they had put unique_ptr in <utility> or even <new>, it would be better in one of those places than in <memory> IMO.

Re never-empty-guarantee, I guess I just wrote a documentation section about this in my lib :p so it is fresh in my mind. IMO it's not very good to say "oh, the variant isn't empty, it merely contains a container that is empty" and give the user UB by transparently dereferencing null. If you want to document "hey user, you get UB if you visit the variant after it is moved from" that's up to you, but it also introduces other holes in the implementation -- what if we assign to the variant afterwards, to bring it back to life? It means, whenever we manipulate recursive_wrapper, we have to branch on whether this pointer is null or not? IDK it just makes it more complicated. In boost::variant, recursive_wrapper is not really a container -- rather it represents a T value which is allocated on the heap, and the pointer to it is not allowed (as part of the business logic) to be null. If you change that without proper safeguards in place, it is a subtle difference in the interface I think.

Re: preprocessed source complexity:

On my machine, this program

#include <cstddef>
#include <new>
#include <utility>
#include <type_traits>

int main() {}

gives me 3225 line count with gcc 5.4.0 when I check preprocessed source size like so:

$ gcc -std=c++11 -E main.cpp | wc -l
3225

clang 3.8 result is similar:

 $ clang -std=c++11 -E main.cpp | wc -l
3631

And sloccount counts my whole lib at 1507 lines. So that's what I based my comment on.

Granted, that preprocessed source lines is definitely not the only thing that affects compile times.

Edit

With this program:

#include <strict_variant/variant.hpp>

int main() {}

I get this line count:

$ g++ -std=c++11 -E -I../include example.cpp | wc -l
5039

[lightmare]

Can we revisit this, please?

One of the concerns raised against unique_ptr was performance. Where is this coming from? I don't see any operations in recursive_wrapper that would be slower with unique_ptr. On the other hand, all recursive_wrapper constructors pay the cost of allocation; I'll come back to this one, because it is much worse than it looks at first glance.

Second concern was that with unique_ptr, operations on a moved-from variant would be UB (dereferencing nullptr).

If you want to document "hey user, you get UB if you visit the variant after it is moved from" that's up to you, but it also introduces other holes in the implementation -- what if we assign to the variant afterwards, to bring it back to life?

It's the other way around. Unless the documentation explicitly says an operation can be performed on a moved-from value, you should assume STL convention: such value is in an indeterminate state and should only be assigned to or destroyed.

variant<int, const char*, std::string> a, b;
a = std::string("eggs");
b = std::string("bacon");
b = std::move(a);
// at this point, what `a` contains is nobody's business
// you certainly shouldn't be visiting it

After the move, a could contain empty std::string, or a non-empty one, or a (const char*)"spam", or int(42), or be in the no_init state that mapbox::variant also has. The fact that it currently only moves the stored value, keeping the alternative type, is an implementation detail -- it can help with performance in cases where you then assign another value of the same type; especially when the type implements move assignment by swapping pointers to dynamically allocated memory.

Now back to the cost of construction.

struct Terminal {};
struct NonTerminal;
using Tree = variant<Terminal, recursive_wrapper<NonTerminal>>;
struct NonTerminal { Tree child; };

Tree grow(int n)
{
  Tree t = Terminal{};
  for (int i = 0; i < n; ++i) {
    t = NonTerminal{ std::move(t) };
  }
  return t;
}

How many NonTerminal instances will grow(n) allocate?
The answer is not on the order of O(n). Each assignment to t in the loop increases the height of the tree, constructing i+1 recursive_wrappers, and each wrapper allocates a new NonTerminal.
So the total number of allocations done by grow(n) is O(n**2). I'll make a PR to benchmarks showcasing this.

This is really bad for bottom-up construction of tree-like variants. Such as in mapnik expression parser.