Re: [boost] Proposal to add a Boost.FSM library

From: Andreas Huber (ahd6974-spamgroupstrap_at_[hidden])
Date: 2006-12-22 10:52:03

Hi Andrey

Andrey Semashev wrote:
> Well, I have read the Boost.Statechart documentation. Its
> functionality covers and extends my proposed implementation, though I
> must note its several deficiences:
> - The author notes the performance issue of Boost.Statechart. I have
> not inspected the library implementation but as I can see from the
> documentation, the performance of transition between states and event
> delivery to a reaction handler linearly depends on the number of
> reactions in the state.

Correct. However, measurements have shown that this is not normally the 
performance bottleneck in a Boost.Statechart FSM (see conclusions under 
"Detailed performance data"):

<http://www.boost-consulting.com/boost/libs/statechart/doc/performance.html#SpeedVersusScalabilityTradeoffs>

Because everything is known at compile time, compilers are able to 
inline and optimize rather aggressively in the dispatch code.

> Additionally, a transition between states involves
> memory allocations which, besides the performance losses in the first
> place, leads to memory fragmentation. A custom pooling allocator
> partially addresses the problem but in most real-world applications
> it will not evade the necessity of pool synchronization costs.

I don't think dynamic memory allocation by itself is the main 
performance bottleneck either. Rather, my performance measurements 
suggest that the main bottleneck is in the code that enters and exists 
the states during a transition. Currently, due to the fact that this 
code needs to work correctly even if user-supplied actions throw 
exceptions, some additional book-kepping is necessary even if the user 
does not need the error-handling features. My guess is that performance 
can be increased by 50% if this is optimized further.

> In the
> proposed implementation no allocations take place neither on
> transitions nor on event delivery. In addition, none of these 
> operations depend on state, transitions or reactions number.

As soon as an FSM needs to be able to process events of arbitrary types 
you usually need to allocate these events on the free store anyway, also 
allocating the states there just doubles the runtime needed for 
new/delete. Sure, you can save all those free store allocations when 
your FSMs only need to deal with one type of event and state but for 
many applications this simply is not flexible enough.

> The implementation even tries to minimize virtual function usage. So,
> even though I haven't done experimental comparisons, IMO the proposed
> implementation will outperform Boost.Statechart.

That wouldn't surprise me at all. Again, please see:

<http://www.boost-consulting.com/boost/libs/statechart/doc/performance.html#SpeedVersusScalabilityTradeoffs>

> - In Boost.Statechart to declare a custom reaction on some event we
> must add it as an element to the "reactions" typedef besides defining
> a "react" member function. No such duplication is needed in the 
> proposed
> implementation - only "on_process" (the synonym for "react") handler
> is needed. As a nice side effect it is possible to rely on C++
> overload resolution rules and even declare "on_process" templates.
> That makes the state code cleaner and more natural, IMO.
> - I can see no way to return a value from a Boost.Statechart's machine
> except by passing a reference or a pointer in the event.

Correct. How do you return a value? With boost::any?

> - I can see no easy way to describe a transition that should take
> place regardless of the current state of the machine in
> Boost.Statechart. To do this one must put the transition into each
> state's "reactions" type sequence.

There are two ways:
1. Define an outermost state that contains all other states and add a 
reaction triggered by event_base.
2. Add a member-function unconsumed_event to the state_machine<> 
subclass:
<http://www.boost-consulting.com/boost/libs/statechart/doc/reference.html#unconsumed_event>

> That being said, I may only purpose my implementation as a lightweight
> addition to the Boost.Statechart aimed to solve performance and
> simplicity issues for small and light FSMs. Is there any need in such?

I don't have time to look at your proposal right now, but I would guess 
that there is a need in a simple FSM lib that does not have all the 
bells and whistles of Boost.Statechart but does provide top-notch 
performance in return. However, I don't see how it can be a part of 
Boost.Statechart, it should probably be a separate library.

Regards,

-- 
Andreas Huber
When replying by private email, please remove the words spam and trap
from the address shown in the header.