[boost] Re: Variant Library: variant size and strong guaranty

From: Eric Friedman (ebf_at_[hidden])
Date: 2003-04-03 02:19:13

Gennadiy Rozental wrote:
> > > 7. Variant size
> > > Unfortunately I was not able to follow exact logic behind usage of 2
> > > different storages. But one thing I know:
> > > sizeof(boost::variant<int,std::string>) could not be 28.
> > > >From what I view it seems that types that are used to construct
> > > storage2 also used when constructed storage1. So we definitely have
> > > size duplication here.
> >
> > The two storages implement Anthony William's "double storage"
> > technique. (See
> > http://aspn.activestate.com/ASPN/Mail/Message/boost/1314807 for an
> > overview.) This technique is necessary to provide a general guarantee
> > of strong exception-safety, which in turn is necessary to maintain
> > a "never empty" invariant for variant.
>
> What is this invariant? And why is it that important.

The invariant is quite straightforward: any object of type variant<T1, T2,
..., TN> contains exactly one object of type T1, T2, ..., or TN.

The lack of this invariant is undesirable for a number of reasons. (See
http://aspn.activestate.com/ASPN/Mail/Message/1313807.) This undesirability
is what lead me to implement the double-storage technique in variant.

I am well aware, of course, of the trade-offs made by the use of this
technique. Thus the decision is not set in stone, and I'd be willing to
consider arguments against it.

I will make two final notes, however.

1) In addition to its role in enabling recursive variants,
boost::incomplete<T> provides a convenient way to increase space efficiency
(though at the expense of speed efficiency due to heap allocation). Note
though that this is only because incomplete wraps a T*, which is small. It
does *not* disable the double-storage technique.

2) For every type supporting non-throwing "move" operations, I have
implemented variant to use single-storage. As a (trivial) proof of this,
boost::has_nothrow_copy types *do* currently avoid the double-storage
overhead.) Of course, until Boost.Move becomes a reality this is nearly all
but meaningless for the vast majority of types.

> From what I see in above message, Anthony clearly indicate that here we
have
> a tradeoff between strong guaranty and doubled variant size. Not arguing
the
> importance of strong guaranty I still believe you are not allowed to make
> this important decision for the Variant library users. We either need to
> find a different way to implement boost::variant with strong guaranty or
> need to provide a way for the user to decide what is more important.

In August 2002, before the implementation of the double-storage technique, I
proposed fast_variant and safe_variant to answer this need. (Incidentally, I
now feel the names optional_variant and variant would be more appropriate.)

Another approach might be to take advantage of the introduction of 'void'
content. Since 'void' content would introduce the notion of an "empty"
variant, it *might* (see below for my strong reservations) make sense to
disable the double-storage technique for variants with allowable empty (i.e.
void content) states.

While this is certainly quite implementable, I feel a bit uneasy about
hinging variant's exception-safety guarantees on such a small point as
whether 'void' content is allowed. I imagine it would not only make variant
more confusing to use but also may not satisfactorily solve the problem of
delegating the space-vs-safety decision to the user.

I'm interested in feedback on this issue.

> BTW why do you need to carry this second storage all the way through the
> variant object lifetime. Why couldn't you use stack allocated buffer in
> copy/assign methods?

Because it is the only way the "never empty" invariant can be generally
maintained. If you think about it, I think you'll understand why.

On the other hand, I'd be quite glad if it were the case that I'm wrong, so
let me know.

> > In regard to the particularly large size you report, I believe it
> > results from a problem either with boost::type_with_alignment itself or
> > with my understanding of it. Thus, I am aware of the problem, but I am
> > still determining how best to address it.
>
> I think this should be resolved before boost::variant is going in release.

As I wrote in the message you quoted, I am working on it.

> > > Separate issue is the type of which field. Having it as int is an
> > > overkill. It would be enough in majority of the cases have char. But
> > > we should be able to deduce the correct type depends on number of
> > > argument types.
> >
> > You're probably right: I doubt more than 127 types will ever be needed.
> > Still, this is an implementation issue, and variant::which() will
> > return int.
>
> This is implementation issue that affect the library design (it affects an
> abstraction overhead). So it's as important as issues above.

So long as variant::which() returns an int, I don't see how it is anything
other than a design issue: in terms of space efficiency, the difference
between sizeof(char) and sizeof(int) is constant.

As a QoI issue, however, I have already admitted that use of a char is
probably more appropriate. Let me know if you disagree with my assessment of
this as QoI.

Thanks,
Eric