Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk