Boost logo

Boost :

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


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
> runtime. As near as I can tell, all proposed solutions to this problem
> 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:
> 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
> 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
> 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

  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),
    case (Which::value + (1)):
        return apply_visitor_impl(visitor, storage, static_cast<T1*>(0),
    // ...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
think this is as good as it gets.

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


Boost list run by bdawes at, gregod at, cpdaniel at, john at