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
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 will not use it either, mainly due to the overhead. This library is easier to use than my current implementations, but the overhead is way too much for me to consider using it in my production code. However, I do not know that I would vote against it, based on the idea that it is not useful to me. On the other hand, I would not vote *for* it either. Maybe my feeling/reaction is in some way related to David's concern about the acceptance process...
Jody Hagins <jody-boost-011304@atdesk.com> writes:
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 will not use it either, mainly due to the overhead. This library is easier to use than my current implementations, but the overhead is way too much for me to consider using it in my production code.
However, I do not know that I would vote against it, based on the idea that it is not useful to me. On the other hand, I would not vote *for* it either. Maybe my feeling/reaction is in some way related to David's concern about the acceptance process...
IMO someone like you probably *should* vote against it, especially if you've taken the time to do reasonable review. At least you have a real-world need for FSMs. I just "know" that FSMs are sometimes used for lightweight speed-critical components. Or maybe more people should be voting for it on the *condition* that an option with fast dispatch must be available. I must say, in a world replete with high-performance generic components, I agree that "Boost FSM" is too broad to cover a library that only does dynamic double-dispatch. -- Dave Abrahams Boost Consulting www.boost-consulting.com
Dave Abrahams wrote:
Or maybe more people should be voting for it on the *condition* that an option with fast dispatch must be available. I must say, in a world replete with high-performance generic components, I agree that "Boost FSM" is too broad to cover a library that only does dynamic double-dispatch.
Personnally, in its current shape I wouldn't vote for this library as an element of an FSM lib. But, there is something that I find really funcky that Andreas has discovered. That you can scale FSMs by spliting them across compilation units in user code I'd love to see a DSL ( Domain Specific Language ) for state charts that generated Alexsey style FSMs with states able to be defined in seperate compilation units. This would solve the scaleabilty problems. /ikh
Iain K. Hanson wrote:
I'd love to see a DSL ( Domain Specific Language ) for state charts that generated Alexsey style FSMs with states able to be defined in seperate compilation units. This would solve the scaleabilty problems.
If you're talking about this http://boost-consulting.com/boost/libs/mpl/example/fsm/player2.cpp then there is nothing to put in separate TUs because states are numbers. Probably, you mixed states up with transitions. This is more a problem of proposed Boost.FSM then yours. In my opition, too many things are put in state definition and too much a user has to remember: 1 curiously recurring template pattern 2 forward declaration of events 3 state context 4 transitions and other reactions 5 other advanced features (only for advanced user) I think some of them should be defined somewhere else. -- Alexander Nasonov
"Alexander Nasonov" wrote:
This is more a problem of proposed Boost.FSM then yours. In my opition, too many things are put in state definition and too much a user has to remember:
1 curiously recurring template pattern 2 forward declaration of events 3 state context 4 transitions and other reactions 5 other advanced features (only for advanced user)
I think some of them should be defined somewhere else.
Would you mind to write review or just list of problems and whether/how they can be solved? I am prepared to wait for opinions after review period ends. What role do you see for your system from: http://aspn.activestate.com/ASPN/Mail/Message/boost/2176732 ? /Pavel
Pavel Vozenilek wrote:
Would you mind to write review or just list of problems and whether/how they can be solved?
First sentences of my review are in my drafts folder. I need more time to finish it.
What role do you see for your system from: http://aspn.activestate.com/ASPN/Mail/Message/boost/2176732
It's more close to Dave's and Alexey's fsm example rather then to proposed Boost.FSM. So, it's not yet a system, it's only an example of metaprogramming on overload sets. Compared to MPL fsm, in my example (a) states are _types_, not numbers, (b) inheritance is used to model states hierarchy and (c) transition table is represented by a set of call operators. There is no history, orthogonality and all these cool features implemented by Andreas. Currently, I'm working on mpl::set interface for overload sets. New version is almost ready, I hope to get my state machine working tomorrow. -- Alexander Nasonov
Hi Alexander,
Iain K. Hanson wrote:
I'd love to see a DSL ( Domain Specific Language ) for state charts that generated Alexsey style FSMs with states able to be defined in seperate compilation units. This would solve the scaleabilty problems.
If you're talking about this http://boost-consulting.com/boost/libs/mpl/example/fsm/player2.cpp then there is nothing to put in separate TUs because states are numbers. Probably, you mixed states up with transitions. This is more a problem of proposed Boost.FSM then yours. In my
I don't think so. Even with Aleksey's approach, with an FSM becoming sufficiently large at some stage the compiler will give up because it reached its template nesting depth limit or compilation becomes infeasible because it takes too long (usually because the compiler eats up so much memory that there's a lot of swapping).
opition, too many things are put in state definition and too much a user has to remember:
1 curiously recurring template pattern
Why is it a problem to remember that?
2 forward declaration of events
You mean states? That shouldn't be too hard either?
3 state context
This is inherent in the UML model, no?
4 transitions and other reactions
Ditto.
5 other advanced features (only for advanced user)
Ditto and you only have to remember what you actually use.
I think some of them should be defined somewhere else.
Where? Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
"Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> writes:
Hi Alexander,
Iain K. Hanson wrote:
I'd love to see a DSL ( Domain Specific Language ) for state charts that generated Alexsey style FSMs with states able to be defined in seperate compilation units. This would solve the scaleabilty problems.
If you're talking about this http://boost-consulting.com/boost/libs/mpl/example/fsm/player2.cpp then there is nothing to put in separate TUs because states are numbers. Probably, you mixed states up with transitions. This is more a problem of proposed Boost.FSM then yours. In my
I don't think so. Even with Aleksey's approach, with an FSM becoming sufficiently large at some stage the compiler will give up because it reached its template nesting depth limit or compilation becomes infeasible because it takes too long (usually because the compiler eats up so much memory that there's a lot of swapping).
That could happen in any program that uses templates. Or uses a compiler, for that matter. I believe this to be FUD, and false for practical sizes of FSMs. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams <dave <at> boost-consulting.com> writes:
"Andreas Huber" <ahd6974-spamgroupstrap <at> yahoo.com> writes:
I don't think so. Even with Aleksey's approach, with an FSM becoming sufficiently large at some stage the compiler will give up because it reached its template nesting depth limit or compilation becomes infeasible because it takes too long (usually because the compiler eats up so much memory that there's a lot of swapping).
That could happen in any program that uses templates. Or uses a compiler, for that matter. I believe this to be FUD, and false for practical sizes of FSMs.
The BitMachine example shows that at least one current compiler (MSVC7.1) fails to compile a flat state machine having between 32 and 64 states (at the time when the library still worked on MSVC6.5, it failed with < 16 states). Exactly where it fails I didn't test, moreover it is a rather arificial FSM that noone would construct in practice. Unfortunately I don't have real-world experience with machines that large but I do have feedback that such large FSMs exist in practice (40 states). Moreover, I expect the problem to become worse with the use of hierarchical/orthogonal states. For me this is enough evidence that I cannot just ignore the issue. Maybe Darryl has more information of this. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
Andreas Huber <ahd6974-spamgroupstrap@yahoo.com> writes:
David Abrahams <dave <at> boost-consulting.com> writes:
"Andreas Huber" <ahd6974-spamgroupstrap <at> yahoo.com> writes:
I don't think so. Even with Aleksey's approach, with an FSM becoming sufficiently large at some stage the compiler will give up because it reached its template nesting depth limit or compilation becomes infeasible because it takes too long (usually because the compiler eats up so much memory that there's a lot of swapping).
That could happen in any program that uses templates. Or uses a compiler, for that matter. I believe this to be FUD, and false for practical sizes of FSMs.
The BitMachine example shows that at least one current compiler (MSVC7.1) fails to compile a flat state machine having between 32 and 64 states (at the time when the library still worked on MSVC6.5, it failed with < 16 states). Exactly where it fails I didn't test, moreover it is a rather arificial FSM that noone would construct in practice. Unfortunately I don't have real-world experience with machines that large but I do have feedback that such large FSMs exist in practice (40 states). Moreover, I expect the problem to become worse with the use of hierarchical/orthogonal states. For me this is enough evidence that I cannot just ignore the issue.
I'm not saying that Aleksey's library can handle all practical state machines. I'm saying that it's possible to build a statically-dispatched FSM library that handles all practical state machines. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
I'm not saying that Aleksey's library can handle all practical state machines. I'm saying that it's possible to build a statically-dispatched FSM library that handles all practical state machines.
In one TU or spread over multiple TUs? Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
"Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> writes:
David Abrahams wrote:
I'm not saying that Aleksey's library can handle all practical state machines. I'm saying that it's possible to build a statically-dispatched FSM library that handles all practical state machines.
In one TU or spread over multiple TUs?
I was thinking of the latter. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
"Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> writes:
David Abrahams wrote:
I'm not saying that Aleksey's library can handle all practical state machines. I'm saying that it's possible to build a statically-dispatched FSM library that handles all practical state machines.
In one TU or spread over multiple TUs?
I was thinking of the latter.
That depends on the functionality. I don't think it is possible if you want to provide support for orthogonal regions. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
"Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> writes:
David Abrahams wrote:
"Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> writes:
David Abrahams wrote:
I'm not saying that Aleksey's library can handle all practical state machines. I'm saying that it's possible to build a statically-dispatched FSM library that handles all practical state machines.
In one TU or spread over multiple TUs?
I was thinking of the latter.
That depends on the functionality. I don't think it is possible if you want to provide support for orthogonal regions.
Sorry, I don't really understand the concept. How are they different from separate state machines? -- Dave Abrahams Boost Consulting www.boost-consulting.com
On Mon, Mar 07, 2005 at 06:03:15PM -0500, David Abrahams wrote:
"Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> writes:
[snip]
That depends on the functionality. I don't think it is possible if you want to provide support for orthogonal regions.
Sorry, I don't really understand the concept. How are they different from separate state machines?
AFAICT nothing. State charts are always collapseable to state transition tables. For each state event pair you would need to allow for a pre-transition action followed by a transition paramaterised by a guard ( condition) followed be a post transition action. The common case does not need two actions and it tends to be fairly arbitary which you use ( more a matter of taste ). The other item required is a context. The common case is a context per FSM. The FSM submissionn allows for a contect per state. context is just a parameter of state which could either common user defined class or a per state class. If you can accomadate that then writting the DSL for state_charts should be fairly straight forward. /ikh
"Iain K. Hanson" <ikh@hansons.demon.co.uk> writes:
On Mon, Mar 07, 2005 at 06:03:15PM -0500, David Abrahams wrote:
"Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> writes:
[snip]
That depends on the functionality. I don't think it is possible if you want to provide support for orthogonal regions.
Sorry, I don't really understand the concept. How are they different from separate state machines?
AFAICT nothing. State charts are always collapseable to state transition tables.
This has something to do with STTs and State Charts? I'm lost. Nothing else you say here helps clarify the concept of orthogonal regions for me.
For each state event pair you would need to allow for a pre-transition action followed by a transition paramaterised by a guard ( condition) followed be a post transition action. The common case does not need two actions and it tends to be fairly arbitary which you use ( more a matter of taste ).
The other item required is a context. The common case is a context per FSM. The FSM submissionn allows for a contect per state. context is just a parameter of state which could either common user defined class or a per state class.
If you can accomadate that then writting the DSL for state_charts should be fairly straight forward.
/ikh
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Dave Abrahams Boost Consulting www.boost-consulting.com
Iain K. Hanson wrote:
AFAICT nothing.
See my answer to Dave.
State charts are always collapseable to state transition tables.
If you mean a single STT per FSM then this requires knowledge about the whole FSM. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
On Tue, Mar 08, 2005 at 08:18:52PM +0100, Andreas Huber wrote:
Iain K. Hanson wrote:
AFAICT nothing.
See my answer to Dave.
State charts are always collapseable to state transition tables.
If you mean a single STT per FSM then this requires knowledge about the whole FSM.
Yep. And i can't see why that would have any effect on scaleability. Its just a meta program for assembling the fsm. /ikh
Iain K. Hanson wrote:
If you mean a single STT per FSM then this requires knowledge about the whole FSM.
Yep. And i can't see why that would have any effect on scaleability. Its just a meta program for assembling the fsm.
With scalability I mean that an FSM can be split up in parts that are implemented in separate TUs. E.g. in the Camera example the inner states of Configuring could reside in one TU and the inner states of Shooting could be implemented in a separate TU. How do you piece the information in these two TUs together? Possibilities: 1. At compile time. I don't see how that could ever work portably. Separate TUs don't have any knowledge of each other. 2. At runtime. Each TU could have one static variable of a type with a constructor. Inside the ctor you register your part of the FSM with the FSM object. This sounds like it could work. Problem is that the standard does not give many guarantees when exactly these static objects are constructed. You can *hope* that they are constructed before the FSM object and on some platforms they actually are constructed at program startup but there's no guarantee for that. So if you want to stay portable you pretty much have to rule out runtime registration. You surely could do it manually but I don't think users would like that. 3. At link time. The proposed FSM lib uses this method (I call it this way because a function declaration is bound to its implementation at link time). A states' react function can be implemented in the FSMs cpp file and from there a transition can be initiated to a state that is unknown in the FSMs hpp file (see Camera example code for details). The "problem" of this method is that there is no way of knowing how many or what states a particular FSM has, not even at runtime. Sure, you know that a state exists when you find the machine residing in that state. But you never know what the next state will be when the next transition is executed. I hope this rather lengthy explanation shows that a statically checked FSM spread over multiple TUs cannot be collapsed into an FSM-global STT (at least not portably). However, since each innermost state must know all its outer states (1), it is theoretically possible to collapse all the reactions of these states into a STT that is local for each innermost state. At a rather hefty price, this would give you constant-time lookup, *separately* for each innermost state. In FSMs with orthogonal regions multiple such innermost states can be active at the same time, which makes lookup linear again. Hence my previous remark to Dave. (1) Just in case you're wondering: It's not a coincidence that outer states don't know their inner states (apart from the initial one) but an inner state knows all its outer states. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
"Andreas Huber" wrote:
2. At runtime. Each TU could have one static variable of a type with a constructor. Inside the ctor you register your part of the FSM with the FSM object. This sounds like it could work. Problem is that the standard does not give many guarantees when exactly these static objects are constructed. You can *hope* that they are constructed before the FSM object and on some platforms they actually are constructed at program startup but there's no guarantee for that. Just note: Singleton library (the one written by Jason Hise) allows guaranteed construction order for objects in multiple TUs.
/Pavel
Pavel Vozenilek wrote:
"Andreas Huber" wrote:
2. At runtime. Each TU could have one static variable of a type with a constructor. Inside the ctor you register your part of the FSM with the FSM object. This sounds like it could work. Problem is that the standard does not give many guarantees when exactly these static objects are constructed. You can *hope* that they are constructed before the FSM object and on some platforms they actually are constructed at program startup but there's no guarantee for that. Just note: Singleton library (the one written by Jason Hise) allows guaranteed construction order for objects in multiple TUs.
I guess it does that with the Andrei's longevity technique? That would be contrary to the scalability requirements, because you manually have to give the parts unique ids. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
"Andreas Huber" wrote:
2. At runtime. Each TU could have one static variable of a type with a constructor. Inside the ctor you register your part of the FSM with the FSM object. This sounds like it could work. Problem is that the standard does not give many guarantees when exactly these static objects are constructed. You can *hope* that they are constructed before the FSM object and on some platforms they actually are constructed at program startup but there's no guarantee for that. Just note: Singleton library (the one written by Jason Hise) allows guaranteed construction order for objects in multiple TUs.
I guess it does that with the Andrei's longevity technique? That would be contrary to the scalability requirements, because you manually have to give the parts unique ids.
Either this or other technique available in Singleton. If the IDs could be generated and assigned dynamically then this could be done during statics initialization time too. /Pavel
Pavel Vozenilek wrote:
"Andreas Huber" wrote:
2. At runtime. Each TU could have one static variable of a type with a constructor. Inside the ctor you register your part of the FSM with the FSM object. This sounds like it could work. Problem is that the standard does not give many guarantees when exactly these static objects are constructed. You can *hope* that they are constructed before the FSM object and on some platforms they actually are constructed at program startup but there's no guarantee for that.
Just note: Singleton library (the one written by Jason Hise) allows guaranteed construction order for objects in multiple TUs.
I guess it does that with the Andrei's longevity technique? That would be contrary to the scalability requirements, because you manually have to give the parts unique ids.
Either this or other technique available in Singleton.
If the IDs could be generated and assigned dynamically then this could be done during statics initialization time too.
/Pavel
If any singleton A needs to be created before and live loner than any singleton B, the code is as simple as: class A : public basic_singleton < A > { }; class B : public basic_singleton < B > { private: A::pointer a_ptr; }; The first pointer to a singleton creates the singleton. Because B's pointer to A is created before B completes construction, A is guaranteed to be created first. In addition, it is guaranteed that basic_singleton based singletons are destroyed in reverse order of creation, so A will outlive B. There are other ways provided to control the order of creation and destruction, which are easy to use and explained at length in the docs packaged with the library. The lib is available in the sandbox, under the singleton folder. (http://boost-sandbox.sourceforge.net/vault/) -Jason
David Abrahams wrote:
"Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> writes:
David Abrahams wrote:
"Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> writes:
David Abrahams wrote:
I'm not saying that Aleksey's library can handle all practical state machines. I'm saying that it's possible to build a statically-dispatched FSM library that handles all practical state machines.
In one TU or spread over multiple TUs?
I was thinking of the latter.
That depends on the functionality. I don't think it is possible if you want to provide support for orthogonal regions.
Sorry, I don't really understand the concept. How are they different from separate state machines?
Orthogonal states are different from separate FSMs in two ways: 1. Automatic entry/exit: If a transition (or any other reaction) leads to an exit of a state containing orthogonal regions then all the active states inside the orthogonal regions are exited before their parent is actually exited. The opposite happens upon entry of a state containing orthogonal regions. With separate FSMs you'd have to manage this yourself, which IMO becomes non-trivial with 4 or more such regions on different levels in the state hierarchy. 2. Automatic event dispatch: An FSM lib supporting orthogonal regions automatically searches for the orthogonal region that "is willing" to react to the current event. Again, with separate FSMs you'd have to do that yourself (dispatch to first FSM and if that didn't consume the event, dispatch to second FSM and so on). This is trivial to do manually but IMO tedious. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
Andreas Huber wrote:
I don't think so. Even with Aleksey's approach, with an FSM becoming sufficiently large at some stage the compiler will give up because it reached its template nesting depth limit or compilation becomes infeasible because it takes too long (usually because the compiler eats up so much memory that there's a lot of swapping).
I agree with you. Your library is much more scalable.
Why is it a problem to remember that?
It's not a problem to remember one or two things but it's hard to remember more without a logic underneath. I suggest at least using smart indentation in tutorial for better visual impression. Actually, I never tried to remember state interface although I read your tutorial two or three times. I decided to postpone it till I really need to write my first state machine.
2 forward declaration of events
You mean states? That shouldn't be too hard either?
This confusion proves my words :)
I think some of them should be defined somewhere else. Where?
Template arguments are not only the place to play in. For example, you may use nested typedef for transition table like in MPL FSM example. -- Alexander Nasonov
Alexander Nasonov <alnsn <at> yandex.ru> writes:
Why is it a problem to remember that?
It's not a problem to remember one or two things but it's hard to remember more without a logic underneath.
Most people familiar with hierarchical FSMs (UML ones anyway) don't have a problem seeing the logic. Also, I don't see what I should explain more than I do already.
I suggest at least using smart indentation in tutorial for better visual impression.
I can do that.
2 forward declaration of events
You mean states? That shouldn't be too hard either?
This confusion proves my words :)
It may prove your words in your case, I don't think it proves anything how well other people can learn the syntax. See comments/reviews from people who have actually used the library.
I think some of them should be defined somewhere else. Where?
Template arguments are not only the place to play in. For example, you may use nested typedef for transition table like in MPL FSM example.
True. Then again, I don't see much of a difference usability-wise between: struct MyState : fsm::simple_state< MyState, Machine, mpl::list< /* ... */ > > {}; struct MyState : fsm::simple_state< MyState, Machine > { typedef mpl::list< /* ... */ > reactions; }; Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
From: Andreas Huber <ahd6974-spamgroupstrap@yahoo.com>
I don't see much of a difference usability-wise between:
struct MyState : fsm::simple_state< MyState, Machine, mpl::list< /* ... */ > > {};
struct MyState : fsm::simple_state< MyState, Machine > { typedef mpl::list< /* ... */ > reactions; };
I think the latter is far easier to grok since the fsm::simple_state parameter list is shorter and simpler. The same information must be supplied either way, but the second form separates distinct aspects of defining the state, so one can ignore some details when concentrating on others. Whether the latter form creates problems elsewhere, I don't know. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;
Rob Stewart wrote:
struct MyState : fsm::simple_state< MyState, Machine, mpl::list< /* ... */ > > {};
struct MyState : fsm::simple_state< MyState, Machine > { typedef mpl::list< /* ... */ > reactions; };
I think the latter is far easier to grok since the fsm::simple_state parameter list is shorter and simpler. The same information must be supplied either way, but the second form separates distinct aspects of defining the state, so one can ignore some details when concentrating on others.
You do have a point there. Plus, if I'm not mistaken then this would also remove a small glitch I have recently discussed with Darryl Green.
Whether the latter form creates problems elsewhere, I don't know.
I haven't checked yet but I think it shouldn't. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
Hi, On Sun, Mar 06, 2005 at 07:29:21PM +0300, Alexander Nasonov wrote:
Iain K. Hanson wrote:
I'd love to see a DSL ( Domain Specific Language ) for state charts that generated Alexsey style FSMs with states able to be defined in seperate compilation units. This would solve the scaleabilty problems.
If you're talking about this http://boost-consulting.com/boost/libs/mpl/example/fsm/player2.cpp then there is nothing to put in separate TUs because states are numbers. Probably, you mixed states up with transitions.
No. I was thinking states which implies a rework of the design. It was the idea of making this design scalable that intregued me. /ikh
"Iain K. Hanson" <ikh@hansons.demon.co.uk> writes:
Hi,
On Sun, Mar 06, 2005 at 07:29:21PM +0300, Alexander Nasonov wrote:
Iain K. Hanson wrote:
I'd love to see a DSL ( Domain Specific Language ) for state charts that generated Alexsey style FSMs with states able to be defined in seperate compilation units. This would solve the scaleabilty problems.
If you're talking about this http://boost-consulting.com/boost/libs/mpl/example/fsm/player2.cpp then there is nothing to put in separate TUs because states are numbers. Probably, you mixed states up with transitions.
No. I was thinking states which implies a rework of the design. It was the idea of making this design scalable that intregued me.
I don't think that would be too hard to do. -- Dave Abrahams Boost Consulting www.boost-consulting.com
"Iain K. Hanson" <ikh@hansons.demon.co.uk> writes:
Dave Abrahams wrote:
Or maybe more people should be voting for it on the *condition* that an option with fast dispatch must be available. I must say, in a world replete with high-performance generic components, I agree that "Boost FSM" is too broad to cover a library that only does dynamic double-dispatch.
Personnally, in its current shape I wouldn't vote for this library as an element of an FSM lib. But, there is something that I find really funcky that Andreas has discovered. That you can scale FSMs by spliting them across compilation units in user code
I'd love to see a DSL ( Domain Specific Language ) for state charts that generated Alexsey style FSMs with states able to be defined in seperate compilation units. This would solve the scaleabilty problems.
I think generating Aleksey-or-Dave style FSMs across translation units would be pretty easy. However, I seriously doubt the DSL can look like a state chart. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
IMO someone like you probably *should* vote against it, especially if you've taken the time to do reasonable review. At least you have a real-world need for FSMs. I just "know" that FSMs are sometimes used for lightweight speed-critical components. Or maybe more people should be voting for it on the *condition* that an option with fast dispatch must be available. I must say, in a world replete with high-performance generic components, I agree that "Boost FSM" is too broad to cover a library that only does dynamic double-dispatch.
As someone working in the game industry, I can say that right now, even if we use fully use Boost in our tools, in our engine we use Boost with parsimony (typically libraries .hpp without .lib; easier to control code size) and also disable RTTI since the memory overhead is not worth the cost. A performant state machine mechanism working without RTTI would be interesting. Regards, Nicolas
Nicolas Fleury wrote:
As someone working in the game industry, I can say that right now, even if we use fully use Boost in our tools, in our engine we use Boost with parsimony (typically libraries .hpp without .lib; easier to control code size) and also disable RTTI since the memory overhead is not worth the cost. A performant state machine mechanism working without RTTI would be interesting.
I always suspected that -fno-rtti is still widely used :) This example seems to work with g++ -fno-exceptions -fno-rtti http://boost-consulting.com/boost/libs/mpl/example/fsm/player2.cpp while this does not http://boost-consulting.com/boost/libs/mpl/example/fsm/player.cpp (you can also find them in $BOOST_ROOT/libs/mpl/example/fsm). -- Alexander Nasonov
Alexander Nasonov <alnsn@yandex.ru> writes:
Nicolas Fleury wrote:
As someone working in the game industry, I can say that right now, even if we use fully use Boost in our tools, in our engine we use Boost with parsimony (typically libraries .hpp without .lib; easier to control code size) and also disable RTTI since the memory overhead is not worth the cost. A performant state machine mechanism working without RTTI would be interesting.
I always suspected that -fno-rtti is still widely used :)
This example seems to work with g++ -fno-exceptions -fno-rtti http://boost-consulting.com/boost/libs/mpl/example/fsm/player2.cpp
That one is the 2nd of two dave-style FSMs. The first is attached. I should really stick this in the Boost tree. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams <dave@boost-consulting.com> writes:
This example seems to work with g++ -fno-exceptions -fno-rtti http://boost-consulting.com/boost/libs/mpl/example/fsm/player2.cpp
That one is the 2nd of two dave-style FSMs. The first is attached. I should really stick this in the Boost tree.
Done; at libs/mpl/example/player1.cpp -- Dave Abrahams Boost Consulting www.boost-consulting.com
Hi Jody,
I will not use it either, mainly due to the overhead. This library is easier to use than my current implementations, but the overhead is way too much for me to consider using it in my production code.
I'd be very interested in hearing what you are usually doing with FSMs and your timing constraints (processor freq., number of events, etc.). Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
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.
Hi Andreas, On Sun, Mar 06, 2005 at 07:42:59PM +0100, Andreas Huber wrote:
Hi Iain,
Thanks for your review!
I'm sorry it had to be negative but I did try to warn you when we discussed this previously. [snip]
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.
Thanks for the history that I've sniped. I understand fully what you mean. I have had the similar problems with my sockets library. The problem IMHO is a lack of meta-programming skills ( I've certainly suffered from ). However, Czarnecki & Eisenecker showed that C++ is Church Turring complete at compile time so as long as this conjecture holds it has to be doable. The approach that I believe would have the greatest chance of sucess would be to use layered ( GenVoca style ) implementation mixed with CRTP to provide two way communication between the layers to form a policy based design. Users would then use a DSL to specify there requirements and a generator would build the FSM.
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.
A name change would only solve part of my problem with this submission. I strongly believe that the C++ you only pay what is absolutely necessary for what you use can not be breached for a boost library. particularly as I have said above, with better meta-programmingi, constant time event dispatch and transition have to be achiveable given CT completness. I.e. event dispatch should idealy be a single indirection but I could live with double dispatch and a transition should idealy be an assignment. I'll address the reat tomorrow as I'm tired and it is late. regards /ikh
Iain K. Hanson wrote:
Thanks for the history that I've sniped. I understand fully what you mean. I have had the similar problems with my sockets library. The problem IMHO is a lack of meta-programming skills ( I've certainly suffered from ). However, Czarnecki & Eisenecker showed that C++ is Church Turring complete at compile time so as long as this conjecture holds it has to be doable.
I also have the suspicion that it is doable, or at least that a blended approach is possible in which you get ruthless efficiency as long as you don't use certain features. But I wouldn't draw to many conclusions from computational completeness. There are still some things you can't do in metaprograms, such as write "Hello World" to standard output. ;-) Jonathan
Jonathan Turkanis wrote:
Iain K. Hanson wrote:
Thanks for the history that I've sniped. I understand fully what you mean. I have had the similar problems with my sockets library. The problem IMHO is a lack of meta-programming skills ( I've certainly suffered from ). However, Czarnecki & Eisenecker showed that C++ is Church Turring complete at compile time so as long as this conjecture holds it has to be doable.
I also have the suspicion that it is doable, or at least that a blended approach is possible in which you get ruthless efficiency as long as you don't use certain features. But I wouldn't draw to many conclusions from computational completeness. There are still some things you can't do in metaprograms, such as write "Hello World" to standard output. ;-)
Jonathan
Well, perhaps not 'standard' output... ;) template < typename Unused > void meta_main ( ) { Hello_world; This_is_a_message_that_is_printed_to_the_list_of_errors; } int main ( ) { meta_main < void > ( ); return 0; } Output: 'Hello_World' : undeclared identifier 'This_is_a_message_that_is_printed_to_the_list_of_errors' : undeclared identifier - Jason
Jason Hise wrote:
Jonathan Turkanis wrote:
Iain K. Hanson wrote:
conclusions from computational completeness. There are still some things you can't do in metaprograms, such as write "Hello World" to standard output. ;-)
Output:
'Hello_World' : undeclared identifier 'This_is_a_message_that_is_printed_to_the_list_of_errors' : undeclared identifier
:-) The first C++ metaprogram was supposedly like this: it just generated error messages enumerating primes. My guess is that Boost.FSM would not attract many users if it just generated error messages. ;-) Jonathan
Iain K. Hanson wrote:
Hi Andreas,
On Sun, Mar 06, 2005 at 07:42:59PM +0100, Andreas Huber wrote:
Hi Iain,
Thanks for your review!
I'm sorry it had to be negative but I did try to warn you when we discussed this previously.
No need to apologize, that's what reviews are about!
[snip]
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.
Thanks for the history that I've sniped. I understand fully what you mean. I have had the similar problems with my sockets library. The problem IMHO is a lack of meta-programming skills ( I've certainly suffered from ). However, Czarnecki & Eisenecker showed that C++ is Church Turring complete at compile time so as long as this conjecture holds it has to be doable.
In one TU yes. I don't think it is doable over multiple TUs. The main problem I see is that there are no global data structures at compile time that would allow you to build a dispatch table with CT lookup. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
participants (10)
-
Alexander Nasonov -
Andreas Huber -
David Abrahams -
Iain K. Hanson -
Jason Hise -
Jody Hagins -
Jonathan Turkanis -
Nicolas Fleury -
Pavel Vozenilek -
Rob Stewart