[boost] Re: What is Double Dispatch ?

From: Andreas Huber (ah2003_at_[hidden])
Date: 2003-06-07 05:34:15

Bohdan wrote:
[snip]
>> BTW, this double dispatch variant is only "cool" ;-) for cases where
>> the second stage of the double dispatch has to choose from only a
>> few different possibilities. That's because the second stage
>> performs a linear search.
>
> Second stage means inner states ?

No, I was referring to the second stage of double dispatch. The first stage
is done with a virtual function while the second stage is a linear search as
discussed.

>
>> In
>> contrast to GOF-visitor, which is essentially constant-time, this
>> variant becomes slower the more choices it has in the second stage.
>> But it scales much better in terms of dependencies.
>
> Does it mean that for some use cases your lib can be event slower
> than FSM implementation with acyclic visitor ? IMHO inner states are
> not too rare thing in practice ...

Not a chance, at least according to my benchmarks on the MSVC7.1 platform.
For flat machines, acyclic vistitor needs one dynamic_cast and two virtual
calls per dispatched event. This looks like constant-time, but it isn't
because dynamic_cast needs longer the more reactions a given state defines.
Moreover, if there are inner states an additional dynamic_cast is needed
each time the dispatch algorithm moves to an outer state because the inner
state did not define a reaction. So, acyclic visitor gets slower with the
number of reactions per state *and* the state nesting depth.
The current algorithm essentially only gets slower with the total number of
reactions seen from the current innermost state. You can nest your states as
much as you like, you only pay a more or less fixed amount of time per
reaction that has to be considered during event dispatch.

See double dispatch section in the rationale.html for more information.

Regards,

Andreas