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

From: Brian Simpson (wheber_at_[hidden])
Date: 2003-08-13 10:20:53

Eric,

"Eric Friedman" <ebf_at_[hidden]> wrote in message 
news:<bh4ujr$crc$1_at_[hidden]>...
>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.
>
[snip]
>
>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.
>

Heavily qualified explanation to follow... :)

[snip]
>
> > 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):
>
[snip]
Oops!  I saw the typedef'd names, observed their similarity to the names of 
the template parameters, and immediately assumed that the switch was based 
on those parameters.  Therefore, the value I _thought_ I was adding was in 
the basing of the switch statement on an mpl::Sequence rather than on the 
template parameters.  I took a closer look at the current implementation and 
observed that it is, indeed, based on the Sequence rather than the template 
parameters--and I feel a little stupid for not noticing it before :).
>
>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

It sounds like you've become convinced that the switch is, indeed, worth the 
effort?  (I infer from the previous statement that you consider the 'if' to 
be O(N), as opposed to a O(1) for the switch.)

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

My implementation is not achieving a better result :).  It's achieving the 
same result as yours; I mentioned above the proposed extra value--which, 
unfortunately for my credibility, was based on a faulty reading.

Still, I would like to put forward a couple of considerations.  These are 
comparatively subjective:
1) The "runtime_type_selected_invoker" component is implemented independent 
of variant.  Two benefits deriving from this approach are:
  a) "variant" becomes a client rather than a collaborator in the usage of 
the functionality.  The practical differences?  A three-argument function 
call rather than a six-argument call dependent on two supporting typedefs.
  b) Distribution decisions can be made separately for the two.  One that I 
thought of was preprocessing.  If someone wants to distribute preprocessed 
versions of code, he can make one decision for variant and another for 
"rtts".

2) An interesting characteristic of your approach is that it results in the 
generation of "extra" cases which should never be executed.  There seems to 
be some extra complexity involved in implementing these extra cases.  The 
implementation I propose does not suffer this problem.  (Don't these extra 
cases seem like constructing a foundation with the cracks "built-in"?  I 
know that the correctness of the class should make it impossible to ever 
fall in, but it still makes me nervous.)
If you don't have to worry about how to implement "extra" cases, you can 
spend more time implementing more visible stuff!

To reiterate: these are subjective considerations.  The runtime behavior of 
both--which is the most objective measure--_is equivalent_.  (Actually, my 
posted implementation had an extra integer operation that yours didn't.  I 
changed it so that the operation is done at compile-time.  It required no 
changes to the interface, so variant benefited transparently.)

Again, thanks for your work.  I couldn't have even made this proposal (and 
had a little fun) had so much legwork not been done already.  And I 
apologize for saying that you hadn't implemented such a solution when you 
actually had.

Brian

_________________________________________________________________
The new MSN 8: smart spam protection and 2 months FREE*  
http://join.msn.com/?page=features/junkmail