[boost] Re: Variant Library: visitation algorithm

From: Gennadiy Rozental (gennadiy.rozental_at_[hidden])
Date: 2003-04-04 04:09:43

"Eric Friedman" <ebf_at_[hidden]> wrote in message
news:b6iopo$l7j$1_at_main.gmane.org...
> 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.)

I don't think there is a differrence. In both cases we either rely on actual
number of types that need to be computed (IOW is not sutable for PP) or on
upper limit of types amount (that is PP constant in both cases).

Here how  the second case could be implemented:

template<typename Typelist, typename Storage,typename Visitor>
void switch_visitor_selector( Storage& storage, int witch, Visitor visitor )
{
      switch( witch ) {
      case 1:
           visitor( Typelist[1](storage) );
           break;
      case 2:
           visitor( Typelist[2](storage) );
           break;
      ...
      case MAX_WITCH:
           visitor( Typelist[MAX_WITCH](storage) );
           break;
      }
}

> > 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.

Does anybody familiar with modern compiler design could confirm/deny above
statement. I will try to dig something myself.

Gennadiy