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

From: Eric Friedman (ebf_at_[hidden])
Date: 2003-04-04 18:53:28

Gennadiy Rozental wrote:
> > > > 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.
>
> >From this it seems that in above passage ("This technique is necessary
...")
> you switched an order of importance:
> In fact you need double storage to implement "never empty" invariant (in
> other case you would need during copy/assignment to first destroy current
> object), that is necessary to implement strong guaranty.
> Isn't it?

Yes, sorry, I presented the logic in a reversed fashion.

The double-storage technique is necessary to maintain a "never empty"
invariant. The double-storage technique provides strong exception-safety
"incidentally."

>
> > 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.
>
> Several notes:
>
> 1. Intrinsic types have nothrow move constructor, so should follow second
> case road. Isn't it?

Unless there is a bug in the code, this should already be the case, as
intrinsic types are covered by has_trivial_copy.

> 2. Could type that implements swap() method somehow follow the second case
> road also? For example, could you somehow deduce T* from buffer and swap
it
> with local copy of the argument?

Yes, I can look into such optimizations. But as I noted in previous
messages, if I can prevent double-storage only for incomplete<T> (a point on
which I'm not certain is even true), it's probably not worthwhile. After
all, sizeof(incomplete<T>) == sizeof(T*), so double-storage means
2*sizeof(T*).

> 3. Could you use placement copy into local to assign storage and then
> memcopy it to variant storage? It wouldn't work with all types but may
work
> in many cases isn't it? Here we would have different tradeoff.

Such memcpy-able types are already covered by has_trivial_copy, which
ultimately enables has_trivial_move. Thus for these types double-storage is
already disabled (provided the appropriate traits are specialized).

> 4. Whatever way these matters will be decided I think it should be
carefully
> documented so the user have a perfect understanding of possible choices.

Agreed: the docs should state what requirements exist on types for the
various optimizations.

[snip]
> > > > > Separate issue is the type of which field. Having it as int is an
> > > 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.
>
> I do not want to argue on terms. My point is that this implementation
detail
> make variant<int,short> size at least 6 instead of 3. 100% difference. So
> let's just fix it before release.

I don't think it's as bad you say: I don't think variant<int, short> will be
a common use-case.

Nonetheless, I'll make the change.

 - Eric