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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
