[boost] Variant Library: visitation algorithm

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

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

Gennadiy.