Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk