[boost] Re: Variant Library: visitation algorithm

From: Eric Friedman (ebf_at_[hidden])
Date: 2003-04-02 20:59:08

Gennadiy Rozental wrote:
> > > 8. Visitation algorithm
> > > In sketch presented visitation algorithm look like this:
> > >
> > > void foo1( which, visitor )
> > > {
> > >     if( n = 1 )
> > >        visitor(...)
> > >    else
> > >       foo2( which, visitor );
> > > }
> > >
> > > void foo2( which, visitor )
> > > {
> > >     if( n = 2 )
> > >        visitor(...)
> > >    else
> > >       foo3( which, visitor );
> > > }
> > >
> > > ....
> > >
> > > In a pseudo code it could be rewritten like this
> > >
> > > foo( visitor )
> > > {
> > >    if( which == 1 ) visitor( first field );
> > >    else if( which == 2 ) visitor( second field );
> > >
> > > ...
> > >    else if( which == n ) visitor( nth field );
> > > }
> > >
> > > It's obvious that switch-based algorithm will be more effective. And
> > > I believe that given at compile time number of the types supplied
> > > (or maximum possible types variant accepts we should be able to
> > > generate one (even if we will need to use PP for that )
> >
> > I'm not sure it's obvious, or even true. These functions are inlined,
> > and as of yet I have no reason to doubt my code will "unroll" to match
> > yours. Admittedly though, I have not inspected any disassembled
> > compiler outputs. Let me know any results you may uncover.
>
> Let's see. Even unrolled if/else based version has complexity
> O(Number_of_types). While switch based version should have a complexity
> O(1). IMO it's obvious that later is much more prefererable to former.
Don't
> you agree?

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

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

if (i == 1) f1();
else if (i == 2) f2();
...
else if (i == n) fN();

would be any less efficient after optimization than

switch (i) {
  case 1: f1(); break;
  case 2: f2(); break;
  ...
  case n: fN(); break;
}

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.

However, if you have particular evidence that compilers do not perform the
optimizations as I suggest (and whether the lack of this optimization is
significant), I would be willing to look into more advanced unrolling
techniques or even your special-case implementation.

Thanks,
Eric