[boost] Re: switch-based runtime type selection (for variant)

From: Eric Friedman (ebf_at_[hidden])
Date: 2003-08-10 03:09:30

Brian,

Brian Simpson wrote:
> A fundamental problem encountered by boost::variant is that of invoking an
> overloaded function for the correct type, where the type is not known
until
> runtime.  As near as I can tell, all proposed solutions to this problem
have
> involved uncomfortable space or time tradeoffs.  I have read several posts
> which asked why we couldn't use a switch statement--it would avoid the
> expenses of the current solutions without incurring any of its own.
> Until recently, I agreed with those (whose expertise I highly respect) who
> said it was not possible.

I don't think anyone ever said it wasn't possible. It was just whether it
would actually improve anything -- i.e., it was unclear whether compilers
would optimize recursively-inlined switch statements better than
recursively-inlined if statements.

> However, while perusing the source for the current implementation of
> boost::variant, a possible solution occurred to me.
> I have spent some time fleshing out the proposed solution, and it seems to
> be all standard C++ (no non-standard).  I think it might be referred to as
> "sequence unrolling".
> Here's how it works:
[snip]
>
> Questions or comments?

Sorry, I've just gotten back from vacation. I haven't spent *too* much time
looking through your code, but I can't see how it improves on my current
code, which features sequence unrolling. If you could explain to me I'd
appreciate it.

> p.s.  I must acknowledge Itay's and Eric's efforts in the current
> implementation of boost::variant.  I've learned a lot just from studying
the
> code.

Thanks! It's nice to know our efforts are being recognized :)

> It was while I was browsing the recently added implementation of
> switched type selection based on the variadic template parameters that
this
> idea occurred to me.

Wait, hold on a second. The current implementation isn't tied to any
particular "unrolling constant." The current visitation mechanism after
preprocessing should like like this (see function template
apply_visitor_impl):

  typedef typename step0::type T0;
  typedef typename step0::next step1;
  typedef typename step1::type T1;
  typedef typename step1::next step2;
  // ...and so on until unrolling constant...

  switch (var_which)
  {
    case (Which::value + (0)):
        return apply_visitor_impl(visitor, storage, static_cast<T0*>(0),
1L);
    case (Which::value + (1)):
        return apply_visitor_impl(visitor, storage, static_cast<T1*>(0),
1L);
    // ...and so on until unrolling constant...
  }

  // ...else continue unrolling next "chunk" of types (by recursively
calling the above w/ stepN)...

Thus, if we are to assume O(1) complexity for a switch, then the complexity
of the visitation mechanism becomes O( N / unrolling-size ), where
unrolling-size is exposed as BOOST_VARIANT_APPLY_VISITOR_UNROLLING_LIMIT. I
think this is as good as it gets.

Let me know if your implementation is achieving a better result.

Thanks,
Eric