[boost] Re: Variant Library: visitation algorithm

From: Eric Friedman (ebf_at_[hidden])
Date: 2003-04-03 20:57:30

Gennadiy Rozental wrote:
> > While I do agree O(1) is better than O(N), I would like to point out
that
> > it is usable only when the pseudo-variadic template interface is used
(i.e.,
> > variant<T1, T2, ..., TN> as opposed to variant<Types>).
>
> Why? And to be absolutely clear: what do you mean by "it"?

By "it" I mean the use of a switch, as you propose.

If variant is given types as a MPL-sequence (e.g., variant< mpl::list<T1,
T2, ..., TN> > instead of variant<T1, T2, ..., TN>), then technique you
propose will not work. Please prove me incorrect, but I don't think you can.
(Note, however, that loop-unrolling is still possible, though ultimately it
doesn't change the O(N) complexity of visitation.)

> > Also, I am still not convinced that an unrolled if-else implementation
> would
> > not be optimized in the same manner as a switch statement. That is,
> whether
>
> I do not know how smart are modern optimizers. But in general my
> understnding was that if-else form should use O(N) comparisons, while
switch
> form should be compiled into jump with some computed offset.

I'd be interested to know more about these assumptions before I spend a
great deal of time writing code based upon them.

Also possible, I'd like to note, is the use of a static array of function
pointers. I'll look into this, too, but the space-overhead involved may be
significant.

> > Further, I would like to point out that we are debating integer O(1) vs.
> > O(N) for integer-equality comparisons. While I am a proponent of
limiting
> > complexity, I would like to observe that you yourself suggested a cap N
=
> > 128.
> >
> > In sum, I'm not sure how pertinent this issue is at this point.
>
> I agree that by itself the difference is not that significant. But note
that
> visitation is very basic operation in regards to variant type. Almost any
> activity that involve variant will include some kind of visitation (look
> into your implementation for example). Some people fight to eliminate
extra
> level of indirection by using references vs. pointers. Or eliminate
virtual
> function to prevent double resolution. In this case the difference could
be
> much more significant (up to 128 times).
> So unless it's really unreasonably difficult to implement different
> visitation scheme, I see enough point to try to do this.

I agree that visitation is the fundamental operation for variant. I'll look
into it.

Thanks,
Eric