* Introduction. The nine requirements are well-stated, and I accept them.
Good. That's a start. [snip]
* Speed versus scalability tradeoffs.
Here there is a big problem. I accept that there must be a speed versus scalability tradeoff; in fact, I'd be slightly surprised if there weren't. However, I would normally expect a slow-down of at most a few percentage points when using a framework; I find it stunning that the difference in performance between hand-written machines and framework-generated machines is so significant (10ns/10ns vs. 130ns/220ns), even in a "somewhat unrealistic" test case.
See below.
In order to accept this performance gap I would need a very convincing explanation. Instead, the explanation seems to be of this form: "The requirements are X; I tried hard to satisfy X without compromising performance, but I couldn't; therefore, it can't be done."
Do I really say this? I don't see any place where I say or imply that something can't be done because *I* couldn't think of a solution.
The explanation of why the performance difference shouldn't matter is also unconvincing. I'm particularly disturbed by the implication that FMSs should not be used for parsing. Why not?
See my upcoming answer in the branch of this thread.
* Double dispatch. This seems like it should be a subsection of "Speed versus scalability tradeoffs"
Noted.
- GOF Visitor: It's natural to ask why a complex state machine can't be broken up into several parts which don't know much about each other, each of which uses a more efficient form of dispatch. Less efficient dispatch would be needed only at junctions between the separate parts. Dave Gomboc raised a similar point, and I don't think it has been adequately addressed.
I think the answer lies in the way how an FSM can be split up usefully, see below. Also, dispatch is typically not the main performance problem.
- Two-dimensional array of function pointers. This explanation makes no sense to me, even as supplemented by Andreas's reply to Iain Hanson this morning. It's common for a composite component to make use of several components implemented in different TUs. For instance, the composite commonent may "know about" the other components by derivation, by containment, typelists, etc. When it needs to assemble the array of pointers, it can simply ask each of them for their contribution.
No, in a nutshell it cannot because it doesn't know how many or what components exist. Of course, there must be links between the components but C++ does not allow you to follow these links in a useful way and there is no way to force the components in the TUs to register themselves. The only way you can guarantee the registration is by requiring the programmer to register all the parts explicitly, which is contrary to the scalability requirements. I can only show this with an example: What follows is stripped-down StopWatch code, one state (Running) is implemented in a separate TU. I'm currently too tired to push this through a compiler so I hope to get this correct enough to make sense: *** Main.hpp *** #include <boost/fsm/state_machine.hpp> #include <boost/fsm/event.hpp> #include <boost/fsm/simple_state.hpp> struct Active; struct StopWatch : fsm::state_machine< StopWatch, Active > {}; struct Stopped; struct Active : fsm::simple_state< Active, StopWatch, fsm::no_reactions, Stopped > {}; *** Main.cpp *** #include "Main.hpp" struct Stopped : fsm::simple_state< Stopped, Active, fsm::custom_reaction< EvStartStop > > { // Here we only say that we might do something with EvStartStop fsm::result react( const EvStartStop & ); }; int main() { StopWatch stopWatch; stopWatch.process_event( EvStartStop() ); return 0; } *** Running.cpp *** #include <boost/fsm/simple_state.hpp> #include "Main.hpp" struct Running : fsm::simple_state< Running, Active > {}; fsm::result Stopped::react( const EvStartStop & ) { // Here we connect the so far unrelated parts of the FSM together. return transit< Running >(); } Looking at the code above we notice several things: 1. Visibility: In the proposed FSM lib, an outer state "knows" only its inner initial state (which can be an incomplete type) but none of its other inner states (Active does not know that Running exists, neither does StopWatch). An inner state knows all its outer states. Now, that it is done this way and not the other way round (outer states know all their inner states but inner states don't know their outer states) is not a coincidence for the simple reason that the other way wouldn't leave any room for parts in multiple TUs. I also think this is pretty much the only sensible way how you can spread an FSM over multiple TUs. I can't prove this (for me this is just obvious). So, if you have any objections be sure to attach a proposal on how you would select the visibility to enable spreading over multiple TUs. It is worth noting that there are strong links to base classes and derived classes. A base class corresponds to an outer state, a derived class corresponds to an inner state, with the same directions of visibility, order of definition and inheritance of properties. 2. Connections: The proposed FSM lib connects the parts at link time, through a call to the react function. This works fine but does leave you with the "problem" that there is no way to have a global view at your FSM, *not* *even* *at* *runtime*. When the FSM still resides inside Stopped you don't have *any* way of knowing that Running even exists. Likewise, when the transition to Running has been made, you cannot possibly know whether there are other states because Running might itself define similar custom_reactions that lead you to other states when the reactions are triggered. Note that the custom reaction cannot possibly have any knowledge about the target state as you then can no longer hide Running in a separate TU. Now, let us consider other possibilities how Running could be connected to Stopped (I'm neither assuming a particular lib interface nor a particular lib implementation, the only thing that I assume is that we have an FSM employing a hypothetical lib with the same states Active, Stopped, Running spread over the TUs Running.cpp and Main.cpp): a) At compile time only: I don't see how that could work: Running.cpp does not have any knowledge about Main.cpp and vice versa. b) At runtime only: State definition could contain a static instance of a class, which, in its constructor, registers the state with its outer state. The outermost states would register with the FSM. This way the FSM would know all its states and also their place in the state hierarchy. Problem is: C++ does not guarantee when exactly the ctors of the static objects are called (see 9.4.2/7, 3.6.2/3). They might be called only "before the first use of any function or object defined in the same translation unit as the [static] object". So, registration with static instances is pretty much useless in our case. It's a hen/egg problem: The states don't register themselves until we call a function in the TU they are defined in but we don't know what functions we need to call until they are registered. I might be reading the standard wrong but I know of at least one platform that implements it exactly this way (MSVC7.1). That is enough for me to steer well clear of automatic runtime registration. There's another problem: Runtime-only registration pretty much rules out some forms of static checking (invalid transitions). c) Any combination of the above: I don't see how that could improve things in any way 3. State-local storage: Consider what we need to do if we want to give Running a new auxilary state variable, e.g. the startTime_ mentioned in the tutorial. Because Running has its own storage, we can simply add a member to its class and are done. We don't need to change Active or the StopWatch. If the proposed FSM lib wouldn't provide storage for each state, it would force people to change the state_machine each time they need to introduce such a variable (or at least once when they introduce the first variable). This is contrary to the scalability requirements. I can't think of other possibilities to ensure the scalability in this area. To improve the situation one can surely toy around with not destructing the objects holding the variables on exit (call entry() and exit() member functions instead), but I don't think this will buy you much performance-wise because it would make the bookkeeping inside the FSM harder (somewhere you still need to track active and inactive states). Also, in FSMs with many states this would fatten the memory footprint considerably. Point 1 & 2 limit the maximum possible dispatch performance, more on that later. Point 3 limits the maximum possible transition performance, which will typically be the main performance bottleneck.
If there are order of initialization problems, the arrays can be allocated on first use.
No, that is not an option. Unless the allocation and the filling of the array always take considerably less time than the reaction itself, this would prohibit the use of such an FSM lib in real-time applications. In real-time applications you mostly cannot afford to do such lazy init stuff, because that would raise the upper limit of the reaction time to often unacceptable levels. In other words: In real-time applications you much prefer having always the same performance characteristics for every event, even if that means that the average performance is worse than the average performance that could be achieved by making lazy init optimizations for the first event.
In my experience, C++ provides extremely fine-grained control over which parts of a computation are performed at compile time and which at runtime. I have a strong suspicion that a FSM library could be written which satisfies the nine requirements and also provides ruthless efficiencies, at least in many common cases.
I believe a library satisfying the 9 requirements can at best provide O(n) dispatch for an FSM using all the features, where n is the number of currently active orthogonal regions. So, if you don't use orthogonal states you get constant time dispatch. The reason lies in the fact that, as I hope I have shown above, you cannot know how your whole FSM looks. Dispatch must always begin with a currently active innermost state and consider its reactions first. Only if there is no suitable reaction for the innermost state, the next outer state can be considered and so on until an outermost state is reached. Now, since the innermost state knows all its outer states at compile time, it could collapse all the reactions of the outer states into a single STT, yielding constant time lookup for each innermost state *separately*. Hence, if there are n innermost states active at the same time you have O(n) lookup. In any case I don't expect dispatch to be the main performance bottleneck in a typical FSM, see above.
It may turn out to be necessary to sacrifice performance for some FSMs, but I believe I hybrid approach may be possible which uses fast dispatch in the majority of cases. I'm willing to be convinced that it is impossible, but I haven't seen a satisfying explanation yet.
A hybrid approach could indeed be possible, but I don't think it can be done without requiring help from the user (i.e. complicating the interface) or constraining the functionality. For example you could require the user to somehow (at CT or RT) register all the possible states of a machine or you could prohibit custom_reactions (i.e. require the implementation of the whole FSM in one TU). Both would give you O(1) lookup. But let's not forget that lookup is typically not the main performance bottleneck! Neither of these measures would speed up transition execution. Transition execution can only be sped up by prohibiting state-local storage, i.e. by further constraining the functionality. "Why not?" you might ask. It seems that this can only be done if you complicate the interface for everyone, including the users who need the full functionality. A user requiring state- local storage would be forced to somehow associate a state idenitifier with a type, which she can then use as a container to hold the auxillary variables. I guess here probably lies our main disagreement: For me the users requiring the full functionality have the priority. Why? Because I think that in a certain class of applications most non-trivial FSMs will hugely benefit from state-local storage (at least some users have confirmed that). To conclude the above: 1. Users confirm that the current interface and features is/are useful for a certain (IMO sufficiently large) class of applications. I realize that there is another sufficiently large class of applications which don't need many of performance-degrading features present in the proposed FSM library. 2. I agree that it is theoretically possible to implement a hybrid library that supports both classes, but *only* at the cost of a much more complex interface *and* a much more complex implementation. I would even go as far as saying that two separate libraries optimized for each class would have very little in common (interface or implementation). I don't see any benefits in a hybrid approach other than being able to say: "This is *the* solution for all your FSM problems". And it could very well turn out that the hybrid interface is so complex that users would not consider using it.
- The documentation warns that executing code after calling simple_state::transit (and several other functions) can lead to undefined behavior. I believe the library should prevent this from occurring. One approach would be to have the function specify a result which is stored until react has finished executing, and then acted upon. Another possibility would be to give result move semantics, so result instances can't be stored in local variables and returned later.
- The restriction on event deferral -- one must pass an event pointed to by an instance of intrusive_ptr -- is extremely inelegant:
int main() { myMachine.process_event( *boost::intrusive_ptr<Event>( new Event() ) ); }
I'm sure there is a good reason for this restriction, but there must be a cleaner way to accomplish the same thing.
Have you read the rationale for this? http://tinyurl.com/6xbo2 (Limitations, Deferring and posting events)
- The procedure for posting events from inside entry actions looks messy; this is noted in the docs, and it's not nearly as bad as the syntax for event deferral, but I'd like to see it improved.
I don't see how. Suggestions welcome.
- I don't understand why it is necessary to pass a type as a length-one mpl::list simply because it is a class template instantiation. The docs say it is "due to some template-related implementation details", but this sounds fishy to me.
This is the example in the docs: struct NotShooting : fsm::simple_state< NotShooting, Camera, /* ... */, mpl::list< fsm::deep_history< Idle > >, fsm::has_deep_history > { // ... }; Internally, I use mpl::is_sequence to find out whether we already have a list of inner initial states. If there's none I need to make such a list. At the point of definition of NotShooting, Idle is an incomplete type. Now the problem is that mpl::is_sequence triggers an instantiation of the deep_history template and I have not found a way how I can prevent access to Idle inside that template. When you wrap that in a list the deep_history template is not instantiated and Idle is not accessed. I'm sure there is a solution but the problem simply never made it to the top of my to-do list. [snip]
I ran the regression tests on seven compilers, with the following results:
1. VC7.1 -- passed all tests 2. VC8.0 -- passed all tests 3. VC7.0 -- ...failed updating 36 targets.. ...skipped 144 targets... ...updated 506 targets... 4. GCC 3.4.1 (Cygwin) -- passed all tests 4. GCC 3.2 (MinGW) -- passed all tests 5. Intel 8.0 ...failed updating 4 targets... ...skipped 4 targets... ...updated 678 targets... 6. CW 8.3 ...failed updating 28 targets... ...skipped 112 targets... ...updated 546 targets... 7. Borland 5.6.4 ...failed updating 36 targets... ...skipped 144 targets... ...updated 506 targets...
I'd be happy to send the full error messages.
Please do, thanks for the testing! Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.