[boost] RE : FSM Review : Performance Issues

From: jdspalding_at_[hidden]
Date: 2005-03-13 21:30:21

*******************************************************************************
BOOST Re: FSM Review : Performance Issues.
I'd like to add some overall comments about the FSM's 
perceived performance issues.  To clarify my bias, 
previous comments, I have already submitted a positive review, 
focusing on usage issues.
Context:
   On Sat, 12 Mar 2005 , Dave Garland wrote
   >On Sat, 12 Mar 2005 15:57:10 -0500, David Abrahams wrote
   >>  
   >>  Haven't a few people been reporting that they won't even begin to
   >>  apply this one because of particular limitations?  Anyone who needs
   >>  higher performance won't even get started.
   
   >Sure, and on the other hand we've had at least one testimonial that this was
   >the best fsm library they found -- served them well in a project. I've heard
   >the same sort of argument from people comparing std::string to a char*. 
   >std::string:
Discussion :
I believe the discussion of performance in the proposed boost 
FSM library is going in an unrewarding direction.  
Undefined design possibilities are being weighed against a working system.
 (notice : I am going to be sympathetic to the "working system".)
 
On the "design possibilties" side there seem to be a number of
major issues.
- double dispatch is O(n), we'd like O(1).
- overall performance is slow, state transitions in XXX nSec
are too slow for a proposed application.
- some people have the idea that the techniques used to
allow FSM to extend over multiple translation units could
be improved.
Again and again someone writes in and says the design does
not feel right, if we did XXX, FSM is likely to be able to
fix YYY.
However, the concrete solution is not yet conceived, 
and for now, a general plausability argument will have to do...
Proposal:
I think we could adopt a structured approach to evaluate these
competing claims.  
A) One viewpoint of the FSM library is through the filter of 
application performance tradeoffs.  
IMHO we have exhausted the qualitative approach,
and need the definiteness of the quantitative.
I would think the FSM critics have the obligation here to provide
support to their view, that FSM performace is inadequate.
A.1) It is said that performance considerations will keep FSM from
being considered for some applications.
  => Then could we specifically, and quantitatively define
  a class of applications for which FSM, as it exists today,
  would be inadequate? (model app)
  - in the timed performance area, what are the model app's
  FSM performace metrics, such as number of states, use of
  orthogonal states, depth of state nesting, number of
  events fired per second, number of events handled per
  second?
  
  - what are the model app's non FSM performance metrics,
  perhaps normalized to FSM metrics, such as lines of code 
  or execution time, per state change, or per event fired?
  
  - please also include some details about the context
  for the app's execution, usage area, etc., to assist
  the readers from other experience domains.
  
A.2) It is said that O(n) double dispatch is inadequate, 
that better design is required for acceptance.
  => To really assert this we really have to have a complete
  model of FSM's runtime behavior.  Since this is different
  in different usage scenarios, what we really need
  are several usage scenarios, and an analysis/measurement
  of where FSM spends its time.  I think Andreas has mentioned
  that he thinks other areas than double dispatch are more 
  important.  
  IMHO this is a quantitative issue, per usage scenario.
  
B) A second viewpoint of the FSM library is that of usage
requirements in the application's code. 
Here there are at least two areas of contention
  - B.1) The implications of the requirement for compilation
  in multiple translation units.
  
  - B.2) The overal ease of use of the FSM library's API.
  
Finally, here is my submission of data for a model
usage of FSM, in the above framework.
******************************************************
Quantitative data : example : from J. Spalding's use of FSM
                              area : industrial control.
   
   A.1) Performance metric
   
   Number of states : 15-20.
   maximum state nesting depth : 5.
   use of orthogonal states : no.
   maximum number of events per second (burst) : 10.
   events handled per second (burst) : 10.
   
   context : Use of FSM in a machine control application.
             FSM controls application's execution "mode",
             and the hardware error monitoring state.
             
   remarks : model app not stressing FSM performance.
             
   A.2) Runtime behavior profile
   
   not carried out.
   FSM performance trivial component of model application.
   
   B.1) Multiple translation units.
   
   model application code was broken across multiple
   translation units, no particular problems occurred.
   
   B.2) API Ease of Use.
   
   API was expressive, easy to configure to solve the problem.
   
   The only difficulties encountered were found in tracing
   compile time initial useage mistakes.  This is also a
   strength of the approach, incorrectly configured FSM
   machines will not compile.
   
***********************************************************
My Opinion : per FSM acceptance into Boost:
- I like the FSM API, think performance today is adequate
for many/most applications, think UML connection is a plus,
voted for FSM acceptance.
- Seeing statements such as 100 nSec cost per event handled
prevents serious use of FSM, does offend me, without a
supporting application performance model/context.  
IMHO Andreas has requsted such info many times, and has 
not been rewarded with any quantitative data.
- IMHO, If we were evaluating FSM for an engineering use today,
it would be accepted, due to good API, good documentation.  
The only way FSM could fail is if FSM code grabbed > (XX) %
of the app's compute cycles, or made an unacceptable latency
hit.  The alternatives, at least in the boost discussion of
it, are all proposed concepts requiring evaluation & development.
- Further it would be quick work to use FSM to prototype a
proposed use, and numerically evalute its time/space/latency
cost.  Just write the proposed FSM on the target machine,
install it with a test harness that puts out events at the
required rate, and you have a use/not use decision with
hard data.
If FSM were included in Boost, then this evaluation
might be accomplished a number of times in the future,
and the fsm interest group may acquire data justifying
a performace oriented new implementation/library.
***********************************************************