[boost] FSM Review

From: Iain K. Hanson (ikh_at_[hidden])
Date: 2005-03-05 19:58:30

I have a serrious problems with this library. FSM is a design pattern and 
they can be spellt in a wide variety of ways. E.g state transition tables
Deterministic Finite Automata, Coloured Petri Nets, and Harrel / UML state
charts. There are equallly, many ways of implementing FSMs. Calling this
library the FSM libray would be like submitting multimap and calling it the 
collections library.

* What is your evaluation of the documentation? How easy (or hard) it is to
understand library features? What can be improved?

On the whole, the documentation looks fairly good. Some nits are that the
exampls use upper case class names and can be confusing when the same
name is used for a template parameter.

The performance charcteristics should have been formally documented before
it came forward for review.

* What is your evaluation of the design? What features are supported better by
alternative FSMs? What could be added (or removed) from the library?

This is where I have a problem. I don't have any problem with specifying
an FSM using UML notation and certainly there plenty of users that will
like this. But any state chart can be collapsed into a state table and 
there is no good reason that event dispatch performance has to suffer.

The documentation suggests that Visitor patter / double dispatch is used.
and it looks like ( from the code ) that states are iterated over from 
outer most to inner most searching for a state willing to consume the event.
The performance of event dispatch will decay linnerly with the depth of the 
states. I can see not good reason why event dispatch could not be achieved
with constant time. The reason it is like this is that the author has used
state chart concepts for the design.

The state_machine class has a total of 5 conatiners ( two std::list and 
three std::map ) two of the maps are for history and are present even if 
you don't specify history.

This library does not follow the C++ convention of you only pay for what you
use. The author has already admitted in discussion on the list that FSMs
that generate events at high speed would not be appropiate for this library.

Because of the libraries design a seperate async version was needed that 
requires mutexs. There are many situations where I would prefer to use
a re-enterent disign using flyweight singleton states. TTThis tradeoff is
not possible with the current design.

Because of the above I vote against inclusion of this library into boost.

* Are you knowledgeable about the problem domain?
 
I have been building FSMs for the last 20 years as they are the one of the 
most common patterns I use. I have build them in assembler, C, C++, and Java
and none of them have ever required the space and time overhead of this library

If this library is accepted into boost I will
continue building my FSM by hand, use Alexsey's FSM, or SMC or even boost
function.

3. Exception handling support: Several people have rightly pointed out that
the rationale for the exception handling support is too thin.

The problems here stem from the design.

4. On some compilers (e.g. gcc), the asynchronous part of the library and most
of the tests currently cannot be compiled with RTTI turned off.

It is an unnecessary overhead that is an artifact of the design.

* Are there performance bottlenecks? Does the library design fit requirements
of real-time systems? How is it useable for embedded systems? Is the
documentation clear on performance tradeoffs?

I've discussed these above. I don't believe real-time system designers would
consider using this library. It is to heavey weight in both space and time,
they have to jump through extra hoops such as writting a custom alloactor
and custom class operator new/delete to overcome the libraries use of heap
allocation. And they definately won't like non constant time event dispatch.

/ikh