[boost] Re: FSM Review

From: Andreas Huber (ahd6974-spamgroupstrap_at_[hidden])
Date: 2005-03-06 13:42:59

Hi Iain,

Thanks for your review!

Before I answer all your points I should perhaps explain how the library
evolved. At the very beginning I also had the dream that this will be
*the* solution for every application that needs static FSMs. However, as
soon as I had collected all the requirements I very quickly saw that it
won't be possible to satisfy everyone with *one* library. At first I
couldn't accept this conclusion and spent a few weeks pestering
colleagues whether requirement X is really that important, whether they
really need to build FSMs *that* large, constantly kicking out and
reintroducing requirements, etc. In the end I had to admit that if I
wanted to keep 2 key requirements (scalability and static checking) that
I will have to compromise on performance. I do realize that some
applications need the performance more than they need features but I
believe that there still is a sufficiently large number of applications
for which the key requirements are more important than performance.
BTW, I don't completely rule out that such a über-FSM library is
feasible, I personally just don't see how. So, if you or anyone else has
a good idea how all the requirements can be satisfied while keeping the
performance comparable to hand-written FSMs I'd be very interested to
hear it.

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

That's fine with me. As I wrote in the known issues section I wouldn't
mind changing the name. I guess it is best to vote on this.

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

I guess you mean the BitMachine example where I use templated states?
Agreed, that is a bit unfortunate. For all the other examples (this
includes the ones discussed in the tutorial) this shouldn't be a problem
because none of them uses template parameters (in the sense that they
don't define their own templates). I decided to do make the non-library
code uppercase so that users can very quickly distinguish library names
from example code.

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

Maybe the docs on this can't be called formal but quite a portion of
Rationale deals with performance and people actually using the library
think it is sufficient. May I ask what else you expected?

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

Have you read the rationale for this? If yes, why do you think that
reasoning there isn't conclusive.

> The documentation suggests that Visitor patter / double dispatch is
> used.

Does it? http://tinyurl.com/4puqm (Double dispatch)

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

It's actually the other way round, but this is of no importance for the
performance discussion.

> The performance of event dispatch will decay linnerly with the
> depth of the states.

Which I'm mentioning here http://tinyurl.com/4qrtl (see Resource usage,
Processor cycles, point 6).
Moreover, I don't think that event dispatch by itself will usually be
the performance bottleneck. Reactions of outer states in deeply nested
FSMs tend to get executed much fewer times than the reactions of inner
states. If this library causes a performance bottleneck in an
application then I expect it to be in transition execution and not in
event dispatch.

> I can see not good reason why event dispatch
> could not be achieved with constant time.

http://tinyurl.com/4puqm (Double dispatch), please let me know what's
wrong with the reasoning there.

> The reason it is like this
> is that the author has used state chart concepts for the design.

I don't understand. In some way the design must "use" state chart
concepts, mustn't it?

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

Right. A state_machine object occupies somewhere around 100 bytes, if
history is not used I guess somewhere around 24 are wasted.

> This library does not follow the C++ convention of you only pay for
> what you use.

True. Then again, I think optimizing this would have a barely
measurable effect, given that each state object also occupies around 40
bytes. An FSM of medium complexity probably has about 5 concurrently
active states, what puts the total footprint in the region of 300 bytes,
yielding about 10% savings. Even for a flat FSM the savings are < 20%. I
don't think this is worth the effort (and the added complexity in the
interface).

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

High speed is not important for everyone. If it's important for you,
don't use this library. Moreover, I'd be very interested in hearing what
you are usually doing with FSMs and your timing constraints (processor
freq., number of events, etc.).

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

I don't follow. The mutex locking is encapsulated in the Worker concept,
if you have a better algorithm (lock-free?) you can implement your own
Worker?

> 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

None of them probably satisfied the requirements this library does.

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

I can't cater for everyone, although I would love to. I have to live
with that.

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

Do they? Please elaborate.

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

Is it? How did you come to that conclusion?

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

We'll see...

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

I don't think that's often a requirement for real-time systems. Rather,
the time spent for event dispatch must not exceed an upper limit. Yes,
this upper limit can be so low that the use of this library would not a
good idea. However, I don't think that this is true for the majority of
real-time applications.

Regards,

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