I am sorry this is late. I made the mistake of introducing my kids to snow skiing. Now they can not get enough of it. Thus, we were gone again until Wednesday (yes, I let them skip a few days of school to go skiing). * What is your evaluation of the documentation? How easy (or hard) it is to understand library features? What can be improved? I think the documentation is relatively complete. However, I am not exactly thrilled by the requirement on the reader to understand UML diagrams. On the other hand, this library is intended to represent UML in C++ (at least to my understanding), so I'm not sure what else can be done. A link to a basic tutorial on UML state machine diagrams would be appropriate in the "UML to boost::fsm Mapping Summary." I know you link to the 730 page OMG document on UML, but I'd also like to see something that describes the basic UML for state charts. * What is your evaluation of the design? What features are supported better by alternative FSMs? What could be added (or removed) from the library? I think the requirements dictate the design. Specifically, the desire to mimic UML statecharts in C++. As stated before, the design brings with it some performance tradeoffs that will make this library unusable to some. * The library documentation contains few not yet solved issues (name, separating the library into two parts, exception handling). What is you opinion here? I think it is obvious that the library should be separated, though I do not think this issue itself should be a stumbling block for acceptance. Exception handling is very important, and I do not buy the rationale that allowing destructors to throw is not a problem in practice. I also do not think I really understand "two stage exit." * What is your evaluation of the implementation? Are there parts of code too obscure or duplicating exiting Boost functionality? Can something be factored out to standalone library or among general utilities? I did not look too much at the implementation, so I can not comment much here. * 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 think we have to define real-time. Traditionally, real-time systems have hard completion time requirements (e.g., the XYZ event must be processed in under 50ms). Even though I have performance issues with this library, I think it can still be utilized in many real-time situations. Andreas has stated several times that the dispatch time will be small compared to the handling time. However, I find this argument a bit lacking, especially for hard real-time requirements, where each cycle taken for dispatch is stolen from the reaction handler. My current application requirements do not fit the traditional definition of real-time. However, my SMs need to be as fast as possible, because in a real sense, my code is competing with other code. Without going into too much detail, when an "opportunity" is available, it is only available to the first one to see it, respond, and take that opportunity. Thus, my real-time requirement is that I have to be faster than anyone else playing my game. I think using this library would put me at a disadvantage in that particular space. However, I do have some applications in which this library could be used successfully (if I were inclined to learn enough UML to make sense of all the details). The documentation is clear enough about the performance issues. In fact, it may be too clear, as some people seem to see problems that may not exist in most applications. One last thing on performance, since it has been a hot topic in relation to this library. I do not think it has sufficient performance to warrant use in all my applications, and I assume the same for many others. However, it does have sufficient performance to be used in a large number of applications. If the docuemntation is clear (which it is), then users can decide when/how it can be used. I could make similar performance claims agains almost every boost library (and I have made them on this list about shared_ptr and signals). However, that does not mean we should eliminate those libraries from boost, nor does it mean that they should never have been accepted (but I would like to see a larger commitment to address performance issues in all currently accepted libraries). I would, however, like to see a separate submission which has a focus on performance, and I would really like to see the performance issue of this library revisited, especially with input from some of the folks here who claim expertise in that area. * What is your evaluation of the potential usefulness of the library? Can you compare this FSM to other implementations? I have used sevaral versions of SMC, solutions from Samek's "Practical Statecharts in C/C++," and my own hand-crafted stuff. I think SMC is the easiest to use, though it also offers the least flexibility. With moderate use, I think this library could become the standard tool for implementing state machines, with the caveat of every tool: it may need to be replaced if it is too slow. However, I also think that this tool requires a more structured design of your state machine than ad-hoc methods. Thus, if speed were an issue, translating this code to something else would not be too difficult. One thing I have not seen in other reviews is a comparison to GUI state machine tools. I know this is a library, with very different requirements. However, having virtually no experience with GUI tools that build FSMs, I'd be interested to see how this code stacks up with code generated by such tools. Specifically, I have avoided them because I want more control than they allow (or at least allowed when I first looked at them). Does anyone have experiences to offer in this regard? * Did you try to use the library? With what compiler? Did you have any problems? Do you have tips for better support of older compilers? What are possible portability problems? I used it on linux, with gcc. I am probably the last person in this community to offer porting advice to older compilers. * How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I read all the documentation, and played with a few examples. Specifically, I tried to implement a subset of a current state machine to compare ease of use and performance. This library seemed more difficult to use, but I attribute most of that to inexperience. I am convinced that with some moderate level of experience, I could write state machines more easily with this tool. * Are you knowledgeable about the problem domain? I would not consider myself an expert, by any stretch of imagination. However, I have done my fair share of work coding state machines. I have used a small number of tools, and I have crafted my own, so I am at least comfortable with the problems represented by such a library. And finally, every reviewer should answer this question: * Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. Yes, with two conditions. 1. The name should definitely be changed. I am not sure, however, what a new name should be. I tend to favor one of Andreas' alternatives: umlfsm. 2. I also think there should be some commitment to revisit the performance issues. I am not sure how this works, but I'd be satisfied with a commitment from Andreas, possibly accompanied by a request to the Boost community for assitance. I am not certain that an acceptable solution can be found, but I think the issue at least needs to be addressed again, specifically with input from the Boost community.
On Fri, 11 Mar 2005 11:16:17 -0500, Jody Hagins wrote
* Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion.
Yes, with two conditions.
1. The name should definitely be changed. I am not sure, however, what a new name should be. I tend to favor one of Andreas' alternatives: umlfsm.
2. I also think there should be some commitment to revisit the performance issues. I am not sure how this works, but I'd be satisfied with a commitment from Andreas, possibly accompanied by a request to the Boost community for assitance. I am not certain that an acceptable solution can be found, but I think the issue at least needs to be addressed again, specifically with input from the Boost community.
I'm glad to see someone actually use a 'conditional accept' clause -- because it seemed like we had an awful lot of 'mostly good stuff, but I reject because it won't work for me because of <fill in reason here>' reviews -- where 'performance' seems to be the biggest reason. And Jody, I with you in that, I'm not certain that without a code generator there is a solution that balances all the forces such multiple translation units (essential for real-world use), performance, scalability, etc. So if we reject the library now, we shut out the C++ community that would use the library in current form in the hope that Andreas will keep working in hopes of an optimum solution to all the design tradeoffs. If one doesn't appear or Andreas is discourage then one group will suffer at the expense of this pursuit. I really feel this is the wrong path. As an analogy, I don't want to give up std::string just because it isn't performant enough to handle all string processing needs... Jeff
I'm glad to see someone actually use a 'conditional accept' clause -- because it seemed like we had an awful lot of 'mostly good stuff, but I reject because it won't work for me because of <fill in reason here>' reviews -- where 'performance' seems to be the biggest reason. And Jody, I with you in that, I'm not certain that without a code generator there is a solution that balances all the forces such multiple translation units (essential for real-world use), performance, scalability, etc. So if we reject the library now, we shut out the C++ community that would use the library in current form in the hope that Andreas will keep working in hopes of an optimum solution to all the design tradeoffs. If one doesn't appear or Andreas is discourage then one group will suffer at the expense of this pursuit. I really feel this is the wrong path. As an analogy, I don't want to give up std::string just because it isn't performant enough to handle all string processing needs...
Jeff
On the other hand .... 1. Boost is about Excellency 2. Nothing prevent usage of the library. It's accessible. And in this particular case I noticed several support request in users ML 3. As well as rejection may lead to discouraging further efforts, so could acceptance do. Could you expect any major issues to be resolved once library is delivered? 4. In numerous case attempts to address any major issues results in complete new interface/design/implementation. Any users relying on accepted version would be disappointed. Also It most probable wont going to be reviewed as well (as it should be) 5. I really-really with somebody spent more time with std::string on drawing board. Maybe we wouldn't have as much issues now. Even worse now everybody kinda required to accommodate it's existing interface and, for example, this #^*%ing traits template parameter is spreading like plague around numerous designs. As a compromise for the situation like this we could introduce new section/area: "Unofficial libraries" where we could place those "complete/finished" submissions that did not passed a review (yet or again). Maybe some other staff. Regards, Gennadiy
"Gennadiy Rozental" <gennadiy.rozental@thomson.com> writes:
On the other hand ....
1. Boost is about Excellency
I think you mean "excellence," your Excellency ;-)
2. Nothing prevent usage of the library. It's accessible. And in this particular case I noticed several support request in users ML
3. As well as rejection may lead to discouraging further efforts, so could acceptance do. Could you expect any major issues to be resolved once library is delivered?
4. In numerous case attempts to address any major issues results in complete new interface/design/implementation. Any users relying on accepted version would be disappointed. Also It most probable wont going to be reviewed as well (as it should be)
5. I really-really with somebody spent more time with std::string on drawing board. Maybe we wouldn't have as much issues now. Even worse now everybody kinda required to accommodate it's existing interface and, for example, this #^*%ing traits template parameter is spreading like plague around numerous designs.
The serialization library is a beautiful example of how a rejection ended up being very positive for the library and for Boost. Whether or not that experience can be replicated is another question. It was certainly not easy for Robert. -- Dave Abrahams Boost Consulting www.boost-consulting.com
Combining a couple replies...
"Gennadiy Rozental" <gennadiy.rozental@thomson.com> writes:
On the other hand ....
1. Boost is about Excellency
Agree.
2. Nothing prevent usage of the library. It's accessible. And in this particular case I noticed several support request in users ML
While I agree that this is technically true, in the commercial world the politics matter -- and being an 'add-in' boost library makes it difficult to handle. I also believe it limits seriously the audience that will look at the library because my perception is that most boost users don't mess with the sandbox or CVS -- they use the releases and that's it.
3. As well as rejection may lead to discouraging further efforts, so could acceptance do. Could you expect any major issues to be resolved once library is delivered?
Yes, I expect major changes over time. Many libraries in boost have evolved significantly over time as users adopt and run into issues that cannot be fully anticipated in reviews. Iterator adaptors comes to mind as a library that, in theory, it's current state could have been fully analyzed up front. But, in fact, it took usage and a major refactoring, including interface changes, to get to the current design. Filesystem is another evolving library -- it solves real problems for many current users, but it doesn't do everything people want. Many of the changes are usage and user driven as Beman evolves the library interfaces. Some of the eventual changes are issues that were known at the time of the review. Just as another example, I think boost.threads needs a full do over, but that doesn't make it any less useful for those that can make use of the library as it is and boost would be lesser for it's absence.
4. In numerous case attempts to address any major issues results in complete new interface/design/implementation. Any users relying on accepted version would be disappointed. Also It most probable wont going to be reviewed as well (as it should be)
I agree. We certainly have known ways of handling this -- deprecating one interface over a couple releases, etc. As for reviews, I think if there is a truly motivated core of people the change then they will pursue and review the change more than the general boost list ever could. Much of this library future has to do with the nature of the author. One of my unstated evaluation criteria is the 'behavior' of the library author. The author must understand the domain, be ready to take criticism with grace, and move the work forward. If I didn't think Andreas is willing and up to this task I would have voted to reject...
5. I really-really with somebody spent more time with std::string on drawing board. Maybe we wouldn't have as much issues now. Even worse now everybody kinda required to accommodate it's existing interface and, for example, this #^*%ing traits template parameter is spreading like plague around numerous designs.
Perhaps, but I suspect there would be different tradeoffs with an alternative design. The other side is that if more time had been spent, it might have been like hash_map -- it would have just been absent. Where would C++ be if std::string wasn't part of the lib? Hard to imagine. In fact, 98% of the time when I'm writing a program I could care less about the traits template parameter and the other failings of std::string. BTW, I don't think I've seen a proposal that identifies and eliminates all the std::string issues -- I suspect that's because it's very difficult to balance the entire design space for strings in a single interface.
As a compromise for the situation like this we could introduce new section/area: "Unofficial libraries" where we could place those "complete/finished" submissions that did not passed a review (yet or again). Maybe some other staff.
Yeah, I've wondered about this approach myself. One of the great things boost does is 'normalize' the entire library development process. Where to put the headers, where to put the source, build system, documentation, regression testing, licensing, etc. Once a user or author has consumed this framework understanding the next library is fully focused on the library itself and not the surrounding mechanisms. The boost development framework is helpful, but it is currently 'tightly coupled' with review process. Interestingly, the Comprehensive Perl Archive Network (CPAN) has to handle all these same mechanisms (build, docs, etc), but it dispenses with the review. Anyone can upload a library the follows the conventions and it becomes available for use. In general, this makes me distrust everything I download from CPAN since there is a lack or quality control. However, there are many excellent packages -- many better than I could write from scratch. Sometimes a CPAN package might just serve as design inspiration for some custom code. Bottom line is CPAN is very useful if you are doing something in Perl. In fact, I suspect that Perl wouldn't be as widely used if not for CPAN. The closest C++ equivalent to CPAN is the 'boost sandbox'. It's good, but overall it doesn't have the searchability and other aspects that make CPAN useful -- wasn't designed to. C++ is also different from Perl in that portability to different compilers is still, unfortunately, a non-trivial issue. So practically speaking I have to download the sandbox library and run it against my compiler to even begin the evaluation of whether it will work for me -- a full Boost library has a regression test report. Anyway, while I think there are interesting directions that can be pursued to expand the contribution base via the sandbox, we would need significant work, in my opinion, to pursue these. And, in fact, perhaps we would want this to be a different organization from boost to make it clear that these aren't reviewed boost libraries.
David Abrahams wrote The serialization library is a beautiful example of how a rejection ended up being very positive for the library and for Boost. Whether or not that experience can be replicated is another question. It was certainly not easy for Robert.
Yes, serialization worked out and it's the only example of a rejected library getting accepted that I know. In most other cases, rejection meant that the author walked away. In a couple cases, walking away was expected because the conclusion of the review was that there wasn't a clear need for the library (FC++ for example). In other cases, though, the author just wasn't prepared to spend the time to try and make people happy (Fixed-Point Decimal). Jeff
"Jeff Garland" <jeff@crystalclearsoftware.com> writes:
Combining a couple replies...
"Gennadiy Rozental" <gennadiy.rozental@thomson.com> writes:
On the other hand ....
1. Boost is about Excellency
Agree.
2. Nothing prevent usage of the library. It's accessible. And in this particular case I noticed several support request in users ML
While I agree that this is technically true, in the commercial world the politics matter -- and being an 'add-in' boost library makes it difficult to handle. I also believe it limits seriously the audience that will look at the library because my perception is that most boost users don't mess with the sandbox or CVS -- they use the releases and that's it.
3. As well as rejection may lead to discouraging further efforts, so could acceptance do. Could you expect any major issues to be resolved once library is delivered?
Yes, I expect major changes over time. Many libraries in boost have evolved significantly over time as users adopt and run into issues that cannot be fully anticipated in reviews. Iterator adaptors comes to mind as a library that, in theory, it's current state could have been fully analyzed up front.
Well, it's not perfect yet, by any means.
But, in fact, it took usage and a major refactoring, including interface changes, to get to the current design.
Yes, and that was an *enormous* effort involving many months and three people. Major redesigns are very hard, and usually they seem to require the original library author to become extremely uncomfortable with the limitations and/or problems of the original design. At least that's been true in my case. Andreas seems very comfortable with his design choices ;-)
Filesystem is another evolving library -- it solves real problems for many current users, but it doesn't do everything people want.
Yeah, but what we're talking about here probably involves more than just evolutionary development. The performance limitations of this design are built into the structure of the library, IIUC. And IIUC the author has given no indication he intends to address that issue other than by explaining that there's no way to do so while maintaining the other design goals. Please correct me if I'm wrong, anyone. I want to be clear that I don't have a vendetta against this library or its author. I do think it's important to be realistic about what's likely to happen to it if it's accepted.
David Abrahams wrote The serialization library is a beautiful example of how a rejection ended up being very positive for the library and for Boost. Whether or not that experience can be replicated is another question. It was certainly not easy for Robert.
Yes, serialization worked out and it's the only example of a rejected library getting accepted that I know. In most other cases, rejection meant that the author walked away. In a couple cases, walking away was expected because the conclusion of the review was that there wasn't a clear need for the library (FC++ for example). In other cases, though, the author just wasn't prepared to spend the time to try and make people happy (Fixed-Point Decimal).
Did I miss something? We reviewed a fixed-point decimal library?? -- Dave Abrahams Boost Consulting www.boost-consulting.com
On Sat, 12 Mar 2005 12:39:14 -0500, David Abrahams wrote
Yes, I expect major changes over time. Many libraries in boost have evolved significantly over time as users adopt and run into issues that cannot be fully anticipated in reviews. Iterator adaptors comes to mind as a library that, in theory, it's current state could have been fully analyzed up front.
Well, it's not perfect yet, by any means.
Sure, but even the old 'bad design' was a useful advance.
But, in fact, it took usage and a major refactoring, including interface changes, to get to the current design.
Yes, and that was an *enormous* effort involving many months and three people. Major redesigns are very hard, and usually they seem to require the original library author to become extremely uncomfortable with the limitations and/or problems of the original design.
No question that (re)design is hard. One of the ways that authors get uncomfortable is others apply the library in various projects and run across report various limitations. Users suggest and submit enhancement ideas -- sometimes fully coded. And, of course, this can happen even if the library is rejected -- it's just that the user audience will be smaller. And that assumes that Andreas would decide to continue working on it...
Filesystem is another evolving library -- it solves real problems for many current users, but it doesn't do everything people want.
Yeah, but what we're talking about here probably involves more than just evolutionary development. The performance limitations of this design are built into the structure of the library, IIUC. And IIUC the author has given no indication he intends to address that issue other than by explaining that there's no way to do so while maintaining the other design goals. Please correct me if I'm wrong, anyone.
I haven't read every last word, of the reviews, but what I did read seemed like a mostly healthy interchange of possible ideas and limitations with various approaches. No matter the final implementation the fsm concepts and background will stay the same. And perhaps the any new interface becomes different interface. I'm unsure if the various approaches can be unified...
I want to be clear that I don't have a vendetta against this library or its author. I do think it's important to be realistic about what's likely to happen to it if it's accepted.
Understood. There are basically 3 options from this juncture -- accept the library unconditionally, reject, accept with limitations. I think what I was hoping is that some sort of consensus could emerge which would allow a path to acceptance with conditions that would satisfy the folks that want to reject and would also work for Andreas. Ultimately it will be up to Pavel's judgement...
Did I miss something? We reviewed a fixed-point decimal library??
Yes, in 2003. Mr Seymour choose to walk away after the library was rejected. The history is here: http://www.boost.org/more/formal_review_schedule.html Jeff
"Jeff Garland" <jeff@crystalclearsoftware.com> writes:
On Sat, 12 Mar 2005 12:39:14 -0500, David Abrahams wrote
Yes, I expect major changes over time. Many libraries in boost have evolved significantly over time as users adopt and run into issues that cannot be fully anticipated in reviews. Iterator adaptors comes to mind as a library that, in theory, it's current state could have been fully analyzed up front.
Well, it's not perfect yet, by any means.
Sure, but even the old 'bad design' was a useful advance.
But, in fact, it took usage and a major refactoring, including interface changes, to get to the current design.
Yes, and that was an *enormous* effort involving many months and three people. Major redesigns are very hard, and usually they seem to require the original library author to become extremely uncomfortable with the limitations and/or problems of the original design.
No question that (re)design is hard. One of the ways that authors get uncomfortable is others apply the library in various projects and run across report various limitations.
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.
Users suggest and submit enhancement ideas -- sometimes fully coded.
Nobody ever submitted me anything that could be thought of as a progressive step towards the two major redesigns I've done (Boost.Python and Boost.Iterators). The redesigns took a great deal of imagination, the sort of thinking that someone who's just trying to get his own work done can't really afford to do.
And, of course, this can happen even if the library is rejected -- it's just that the user audience will be smaller. And that assumes that Andreas would decide to continue working on it...
Yes.
Filesystem is another evolving library -- it solves real problems for many current users, but it doesn't do everything people want.
Yeah, but what we're talking about here probably involves more than just evolutionary development. The performance limitations of this design are built into the structure of the library, IIUC. And IIUC the author has given no indication he intends to address that issue other than by explaining that there's no way to do so while maintaining the other design goals. Please correct me if I'm wrong, anyone.
I haven't read every last word, of the reviews, but what I did read seemed like a mostly healthy interchange of possible ideas and limitations with various approaches.
I don't understand why you're saying that. I made no judgement about the health of the conversation.
No matter the final implementation the fsm concepts and background will stay the same. And perhaps the any new interface becomes different interface. I'm unsure if the various approaches can be unified...
I want to be clear that I don't have a vendetta against this library or its author. I do think it's important to be realistic about what's likely to happen to it if it's accepted.
Understood. There are basically 3 options from this juncture -- accept the library unconditionally, reject, accept with limitations. I think what I was hoping is that some sort of consensus could emerge which would allow a path to acceptance with conditions that would satisfy the folks that want to reject and would also work for Andreas. Ultimately it will be up to Pavel's judgement...
Did I miss something? We reviewed a fixed-point decimal library??
Yes, in 2003. Mr Seymour choose to walk away after the library was rejected. The history is here:
I remember now, thanks. -- Dave Abrahams Boost Consulting www.boost-consulting.com
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: "it's too slow for my app". Fine for them, well at least until they leak memory in their app, (of course, they won't use shared_ptr either -- too much memory). That doesn't make std::string less useful for me or thousands of other programmers. I'm interested in using fsm in distributed server apps where the library overhead is completely irrelevant to application performance. The documentation was certainly upfront about the performance implications -- so it doesn't try to misrepresent itself -- if it did I would have major problems.
Users suggest and submit enhancement ideas -- sometimes fully coded.
Nobody ever submitted me anything that could be thought of as a progressive step towards the two major redesigns I've done (Boost.Python and Boost.Iterators). The redesigns took a great deal of imagination, the sort of thinking that someone who's just trying to get his own work done can't really afford to do.
Fair enough, but there have been major submissions for other libraries -- some more radical than others. I know there have been user submissions for design changes related to signals performance that Doug has been looking at. Perhaps it's a question of what you and I define as 'major redesign'....
I haven't read every last word, of the reviews, but what I did read seemed like a mostly healthy interchange of possible ideas and limitations with various approaches.
I don't understand why you're saying that. I made no judgement about the health of the conversation.
Well, my take was that Andreas was quite open to discussing the options and directions that would lead to better performance. Others seem to think that Andreas has closed off all viable options, but maybe I'm the one that's misreading the conversation. Jeff
"Jeff Garland" <jeff@crystalclearsoftware.com> writes:
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: "it's too slow for my app". Fine for them, well at least until they leak memory in their app, (of course, they won't use shared_ptr either -- too much memory). That doesn't make std::string less useful for me or thousands of other programmers. I'm interested in using fsm in distributed server apps where the library overhead is completely irrelevant to application performance. The documentation was certainly upfront about the performance implications -- so it doesn't try to misrepresent itself -- if it did I would have major problems.
All true, but I don't see what bearing it has on the likely evolution of the library. Remember, I am not making any argument about whether to accept the library here.
Users suggest and submit enhancement ideas -- sometimes fully coded.
Nobody ever submitted me anything that could be thought of as a progressive step towards the two major redesigns I've done (Boost.Python and Boost.Iterators). The redesigns took a great deal of imagination, the sort of thinking that someone who's just trying to get his own work done can't really afford to do.
Fair enough, but there have been major submissions for other libraries -- some more radical than others. I know there have been user submissions for design changes related to signals performance that Doug has been looking at. Perhaps it's a question of what you and I define as 'major redesign'....
Anything that requires a fundamental rethink of the library's approach.
I haven't read every last word, of the reviews, but what I did read seemed like a mostly healthy interchange of possible ideas and limitations with various approaches.
I don't understand why you're saying that. I made no judgement about the health of the conversation.
Well, my take was that Andreas was quite open to discussing the options and directions that would lead to better performance. Others seem to think that Andreas has closed off all viable options,
Maybe some others; I didn't think that.
but maybe I'm the one that's misreading the conversation.
All I'm trying to say is that Andreas hasn't given me the impression that he feels high performance is a _crucial_ area for this library to address. I come at FSMs from the "pure abstraction" point-of-view; the UML statecharts that this library is aimed at can have all kinds of warts and complications (some of which are very useful) on them that aren't part of the basic FSM abstraction. Part of what makes FSMs fast may be the simplicity of the model. It seems as though being able to model UML statecharts is a primary design goal for Andreas, and that he doesn't consider providing some useful subset of that functionality in order to get high performance an option. I could be misunderstanding; someone please correct me if so. It seems to me that if "orthogonal states" is the only feature in conflict with getting the highest dispatching performance, it ought to be possible to design a library whose performance only degrades if you use that feature. But this library seems to have a design that's fundamentally incompatible with an approach like that. To get there, both the interface and the implementation would have to be redesigned IIUC. So that sums up why I think evolving toward support for lightweight FSMs is not likely. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
All I'm trying to say is that Andreas hasn't given me the impression that he feels high performance is a _crucial_ area for this library to address.
You are right inasmuch as that performance is only 2nd on my priority list. First comes satisfying the requirements and ease-of-use. However, it *is* important for me to deliver something that can be described as efficient, given the requirements.
I come at FSMs from the "pure abstraction" point-of-view; the UML statecharts that this library is aimed at can have all kinds of warts and complications (some of which are very useful) on them that aren't part of the basic FSM abstraction. Part of what makes FSMs fast may be the simplicity of the model. It seems as though being able to model UML statecharts is a primary design goal for Andreas, and that
Yes.
he doesn't consider providing some useful subset of that functionality in order to get high performance an option. I could be misunderstanding; someone please correct me if so.
I did consider that and tried to explain why I failed. I'm afraid that I haven't been very successful in convincing people that the main obstacles aren't easy to overcome.
It seems to me that if "orthogonal states" is the only feature in conflict with getting the highest dispatching performance, it ought to be possible to design a library whose performance only degrades if you use that feature.
I suppose you are inferring that from what I said in http://tinyurl.com/7ybeq? I see that this can easily be misunderstood. Fact is that the current interface *theoretically* allows for constant time dispatch, as long as orthogonal states are not used. If they are used you get O(n) dispatch where n is the number of currently active orthogonal regions. However, there are a few practical problems for which I'll probably need help to overcome them.
But this library seems to have a design that's fundamentally incompatible with an approach like that. To get there, both the interface and the implementation would have to be redesigned IIUC. So that sums up why I think evolving toward support for lightweight FSMs is not likely.
See above, a few optimizations are theoretically possible but it is clear that the proposed FSM library will probably never earn itself the predicate lightweight. 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:
I did consider that and tried to explain why I failed. I'm afraid that I haven't been very successful in convincing people that the main obstacles aren't easy to overcome.
I think some of us are unsympathetic to the "it's hard" argument ;-) Maybe that's unfair, but it's the way it is.
It seems to me that if "orthogonal states" is the only feature in conflict with getting the highest dispatching performance, it ought to be possible to design a library whose performance only degrades if you use that feature.
I suppose you are inferring that from what I said in http://tinyurl.com/7ybeq? I see that this can easily be misunderstood. Fact is that the current interface *theoretically* allows for constant time dispatch, as long as orthogonal states are not used. If they are used you get O(n) dispatch where n is the number of currently active orthogonal regions.
That seems close to optimal, considering the alternatives.
However, there are a few practical problems for which I'll probably need help to overcome them.
But this library seems to have a design that's fundamentally incompatible with an approach like that. To get there, both the interface and the implementation would have to be redesigned IIUC. So that sums up why I think evolving toward support for lightweight FSMs is not likely.
See above, a few optimizations are theoretically possible but it is clear that the proposed FSM library will probably never earn itself the predicate lightweight.
I don't care if the library is lightweight (well I do a little). I'm talking about generating lightweight FSMs. But I suspect that's what you meant anyway. That would confirm my impression. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
"Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> writes:
I did consider that and tried to explain why I failed. I'm afraid that I haven't been very successful in convincing people that the main obstacles aren't easy to overcome.
I think some of us are unsympathetic to the "it's hard" argument ;-)
Understandably :-). [snip]
But this library seems to have a design that's fundamentally incompatible with an approach like that. To get there, both the interface and the implementation would have to be redesigned IIUC. So that sums up why I think evolving toward support for lightweight FSMs is not likely.
See above, a few optimizations are theoretically possible but it is clear that the proposed FSM library will probably never earn itself the predicate lightweight.
I don't care if the library is lightweight (well I do a little). I'm talking about generating lightweight FSMs. But I suspect that's what you meant anyway. That would confirm my impression.
Yes, I meant the generated FSMs. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
Jeff Garland wrote:
Perhaps, but I suspect there would be different tradeoffs with an alternative design. The other side is that if more time had been spent, it might have been like hash_map -- it would have just been absent. Where would C++ be if std::string wasn't part of the lib? Hard to imagine. In fact, 98% of the time when I'm writing a program I could care less about the traits template parameter and the other failings of std::string. BTW, I don't think I've seen a proposal that identifies and eliminates all the std::string issues -- I suspect that's because it's very difficult to balance the entire design space for strings in a single interface.
Unlike std::string, FSMs aren't used in 99% of C++ projects, especially big ones. It's a special market and only those who work there might have problems similar to lack of std::string. They know it better. However, FSMs are quite often used to describe class behavior but most of the time those classes are implemented without any fsm library. People just look at the diagram, then define a couple of bool members or 'int m_state;' and then they check restrictions imposed by fsm in every function drawn on the diagram (events are usually function calls). Typical example of such class is POAManager (CORBA). It has active, holding, discarding, inactive, start and end states and there are create_POA, activate, discard_requests, hold_requests, deactivate and destroy functions. I'd be happy to see a library in boost that can elegantly solve problems of such classes. Common problems are 1. Class invariants depend on state. This usually means that they lose simplicity and effectiveness. 2. Some class members are valid only in certain states. (Andreas has proved that state local storage is useful thing) 3. Because of 1 and 2, it's harder to maintan even basic exception safety. Because classical approach to implement POAManager and the like is not overly complex and because no special skills are needed, new library should have several advantages (to give answers to problems 1-3, at least) and it should have very clear and easily understandable model. Tutorial of this library should describe how to solve typical problems of classical approach. If this approach is taken, fsm may become a second tool after std::string :) (just kidding, there are a lot of more important tools) -- Alexander Nasonov
"Alexander Nasonov" wrote:
However, FSMs are quite often used to describe class behavior but most of the time those classes are implemented without any fsm library. People just look at the diagram, then define a couple of bool members or 'int m_state;' and then they check restrictions imposed by fsm in every function drawn on the diagram (events are usually function calls).
Typical example of such class is POAManager (CORBA). It has active, holding, discarding, inactive, start and end states and there are create_POA, activate, discard_requests, hold_requests, deactivate and destroy functions.
I'd be happy to see a library in boost that can elegantly solve problems of such classes. Common problems are
1. Class invariants depend on state. This usually means that they lose simplicity and effectiveness. 2. Some class members are valid only in certain states. (Andreas has proved that state local storage is useful thing) 3. Because of 1 and 2, it's harder to maintan even basic exception safety.
Regardless of current review: do you have something in mind? How would API of such FSM look like? /Pavel
Pavel Vozenilek wrote:
Regardless of current review: do you have something in mind? How would API of such FSM look like?
Please, give me more time :) I'm preparing a presentation for ACCU where I'm going to discuss FSM as one practical application of overload sets. When I finish it, I'll switch to compile-time optimization and only after that I'll switch to FSM tuning. -- Alexander Nasonov
2. Nothing prevent usage of the library. It's accessible. And in this particular case I noticed several support request in users ML
While I agree that this is technically true, in the commercial world the politics matter -- and being an 'add-in' boost library makes it difficult to handle. I also believe it limits seriously the audience that will look at the library because my perception is that most boost users don't mess with the sandbox or CVS -- they use the releases and that's it.
Filesystem is another evolving library -- it solves real problems for many current users, but it doesn't do everything people want. Many of the changes are usage and user driven as Beman evolves the library interfaces. Some of the eventual changes are issues that were known at the time of the review. Just as another example, I
I really believe we need to remedy this situation. I would love to use BOOST_FOREACH in my work projects, but end up writing my own think
boost.threads needs a full do over, but that doesn't make it any less useful for those that can make use of the library as it is and boost would be lesser for it's absence.
Much of this library future has to do with the nature of the author. One of my unstated evaluation criteria is the 'behavior' of the library author. The author must understand the domain, be ready to take criticism with grace, and move the work forward. If I didn't think Andreas is willing and up to
I believe in both above examples there were no major unresolved issues revealed during review. Fixing issues is natural part of library lifecycle whatever big changes involved. this
task I would have voted to reject...
It's your call. I did not follow the discussion that close.
In fact, 98% of the time when I'm writing a program I could care less about the traits template parameter and the other failings of std::string.
Just grep in boost and see in how name places libraries adding this parameter. And you (and I and vast majority of C++ community) never need it.
BTW, I don't think I've seen a proposal that identifies and eliminates all the std::string issues -- I suspect that's because it's very difficult to balance the entire design space for strings in a single interface.
For some time now I think we need boost::string. I hope upcoming reviews will cover this area (at least partially).
Anyway, while I think there are interesting directions that can be pursued to expand the contribution base via the sandbox, we would need significant work, in my opinion, to pursue these. And, in fact, perhaps we would want this to be a different organization from boost to make it clear that these aren't reviewed boost libraries.
As usual we just need volunteers to do the job ;) Gennadiy
David Abrahams wrote:
The serialization library is a beautiful example of how a rejection ended up being very positive for the library and for Boost. Whether or not that experience can be replicated is another question. It was certainly not easy for Robert.
If my hazy recollections are right, the initial serialization library review brought up various criticisms of the library, which had been solved by other libraries, or for which useful techniques were known and could be applied. This library seems to differ - it appears that there are criticisms of the library's performance characteristics, but no-one is pointing to alternative libraries that solve these problems (albeit they may be deficient in other ways). Similarly, I haven't noticed any suggestions for specific techniques that might be used to improve the performance of the current submission. Also, (albeit without much familiarity with state machines) I don't believe that the library should be rejected due to a lack of generality. If the solution is a non-starter for significant groups of potential users, then it will not be a hindrance in the development of other state machine libraries with different goals (or the same goals and better implementation). The people who need performance above features can continue to develop their high-performance solutions, hopefully to the eventual standard required for boost acceptance. Apologies to Andreas that I am not sufficiently qualified to submit a review. Matt
Matthew Vogt <mattvogt@warpmail.net> writes:
David Abrahams wrote:
The serialization library is a beautiful example of how a rejection ended up being very positive for the library and for Boost. Whether or not that experience can be replicated is another question. It was certainly not easy for Robert.
If my hazy recollections are right, the initial serialization library review brought up various criticisms of the library, which had been solved by other libraries, or for which useful techniques were known and could be applied.
This library seems to differ - it appears that there are criticisms of the library's performance characteristics, but no-one is pointing to alternative libraries that solve these problems (albeit they may be deficient in other ways). Similarly, I haven't noticed any suggestions for specific techniques that might be used to improve the performance of the current submission.
To the contrary, in previous threads I have posted several examples of small FSM libraries with either O(1) or O(#outgoing transitions) dispatch. Alexander Nasonov has also posted some examples using a very different approach. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
This library seems to differ - it appears that there are criticisms of the library's performance characteristics, but no-one is pointing to alternative libraries that solve these problems (albeit they may be deficient in other ways). Similarly, I haven't noticed any suggestions for specific techniques that might be used to improve the performance of the current submission.
To the contrary, in previous threads I have posted several examples of small FSM libraries with either O(1) or O(#outgoing transitions) dispatch. Alexander Nasonov has also posted some examples using a very different approach.
These techniques do not address the issues of state machines dispersed across multiple translation units, or support for orthogonal states, do they? Matt
Matthew Vogt <mattvogt@warpmail.net> writes:
David Abrahams wrote:
This library seems to differ - it appears that there are criticisms of the library's performance characteristics, but no-one is pointing to alternative libraries that solve these problems (albeit they may ^^^^^^^^^^^^^^^ be deficient in other ways). Similarly, I haven't noticed any ^^^^^^^^^^^^^^^^^^^^^^^^^^ suggestions for specific techniques that might be used to improve the performance of the current submission.
To the contrary, in previous threads I have posted several examples of small FSM libraries with either O(1) or O(#outgoing transitions) dispatch. Alexander Nasonov has also posted some examples using a very different approach.
These techniques do not address the issues of state machines dispersed across multiple translation units, or support for orthogonal states, do they?
So what? I think Alexander's does allow dispersed machines, FWIW. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
I think Alexander's does allow dispersed machines, FWIW.
Not yet that far. I have only tried separate compilation of dispatch table. I have a plan for further separation: Minimize compilation time ------------------------- - Use typeof in overloads::set wherever possible - Special unrolling for sets with fixed arity FSM-specific optimization ------------------------- - Put tranition table generation into separate translation unit. Even spread it over several TUs - one TU for one event or small group of events. - Avoid using get_state directly, better get states or results of operations on states througth visitors. Put visitation code in separate TU. It's not exactly dispersed machines but still may help to generate middle-sized (more then 100 transitions) FSMs. -- Alexander Nasonov
David Abrahams wrote:
Matthew Vogt <mattvogt@warpmail.net> writes:
These techniques do not address the issues of state machines dispersed across multiple translation units, or support for orthogonal states, do they?
So what?
I think Alexander's does allow dispersed machines, FWIW.
Probably. But it cannot support state-local storage in the same sense as this library. (otherwise, I like it)
Alexander Nasonov wrote:
Peter Petrov wrote:
Probably. But it cannot support state-local storage in the same sense as this library. (otherwise, I like it)
What's wrong with my approach?
Suppose that we have nested states, and we use state-local storage in the outer state. Now, for as long as we don't leave the outer state, (only making transitions between its inner states), it is natural to keep its storage. I.e. the lifetime of the storage should be the same as the logical lifetime of the state. Judging from your brief description of your approach, I presume that leaving an inner-state will also destroy the outer-state, since they are the same object (you said: "inheritance is used to model states hierarchy").
Peter Petrov wrote:
Suppose that we have nested states, and we use state-local storage in the outer state. Now, for as long as we don't leave the outer state, (only making transitions between its inner states), it is natural to keep its storage. I.e. the lifetime of the storage should be the same as the logical lifetime of the state.
Judging from your brief description of your approach, I presume that leaving an inner-state will also destroy the outer-state, since they are the same object (you said: "inheritance is used to model states hierarchy").
You're right. It has a different model. There is no outer state. Inheritance is used only to reduce number of transitions from a group of states to one transition from their common base. Of course, you can store outer state data in base class as shared_ptr and pass this pointer to all derived states. -- Alexander Nasonov
| -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Gennadiy Rozental | Sent: 12 March 2005 05:20 | To: boost@lists.boost.org | Subject: [boost] Re: FSM Review | | > I'm glad to see someone actually use a 'conditional accept' clause | because it seemed like we had an awful lot of 'mostly good stuff', | > | > Jeff | | On the other hand .... | | 1. Boost is about Excellency Agreed, but But "The Best is the Enemy of the Good". IMHO ALL designs are compromises (especially C++ itself!) and if we only accept perfection, and reject this (and others), we risk throwing the baby out with the bathwater. | 3. As well as rejection may lead to discouraging further efforts, A serious disadvantage. | 4. In numerous case attempts to address any major issues | results in complete new interface/design/implementation. So what - there aren't going to be too many things depending on it -- unlike string and serialisation. | Any users relying on accepted version would be disappointed. OK if someone comes up with a better, but incompatible solution, then no problem. Users of version 1 will either stick with it, with most of the bugs ironed out, or suffer the pain of moving to version 2 (which SHOULD be reviewed separately). | 5. I really-really wish somebody spent more time with std::string | on drawing board. Maybe we wouldn't have as much issues now. Hindsight is always so crystal clear... Paul Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539 561830 +44 7714 330204 mailto: pbristow@hetp.u-net.com
| 1. Boost is about Excellency
Agreed, but But "The Best is the Enemy of the Good".
IMHO ALL designs are compromises (especially C++ itself!) and if we only accept perfection, and reject this (and others), we risk throwing the baby out with the bathwater.
1. We do not through anything anywhere. It's still there. Just does not approved yet. It doesn't mean it's unusable. It just mean that community think it's still is not good enough. You may argue that library wouldn't get as good acceptance from managerial level (since it's not covered by Boost label). My position is accepting library that community think is not good enough yet has even worse consequences: eventually level of trust to the label will decline affecting all libraries. 2. I personally am not quite sure the baby exist in this case. I have extensive recent experience with applying FSM based logic to performance important parts of several utilities. But unfortunately I did not have a time and resources to invest into review for this submission. I only read tutorial. I must say it left me .. well .. open-mouthed: Why would anyone use solution like this? 1. All states are .. well .. stateless. no way to save anything into state - it gets destroyed every time 2. I have to spend time every time on new, constructor, destructor for each state 3. From what I see there is no way it could have constant dispatch time (just guess - no real analysis - but I would be really surprised if it's not true) 4. Interface limitations seems unreasonable: why would deferred event needs to be supplied as intrusive_ptr? Keep in mind that is just my opinion after perfunctory look on tutorial.
| 4. In numerous case attempts to address any major issues | results in complete new interface/design/implementation.
So what - there aren't going to be too many things depending on it -- unlike string and serialization.
I am not sure why you believe this is true. Gennadiy
I have extensive recent experience with applying FSM based logic to performance important parts of several utilities. But unfortunately I did not have a time and resources to invest into review for this submission. I only read tutorial. I must say it left me .. well .. open-mouthed: Why would anyone use solution like this?
I guess because for some people performance is a lot less important than features and expressiveness. I strongly believe that there is a sufficiently large class of applications where this library will not cause any noticeable overhead, which at least some users have confirmed.
1. All states are .. well .. stateless. no way to save anything into state - it gets destroyed every time
Hierarchical states solve this problem.
2. I have to spend time every time on new,
Did you notice that you can overload operator new and delete for all states?
constructor, destructor for each state
For good reasons (to satisfy the scalability requirements).
3. From what I see there is no way it could have constant dispatch time (just guess - no real analysis - but I would be really surprised if it's not true)
The interface theoretically allows for O(n) dispatch, where n is the number of orthogonal regions. So, if you don't use orthogonal regions you get O(1) dispatch. This is not yet implemented though and there are a few practical problems that need to be cleared first.
4. Interface limitations seems unreasonable: why would deferred event needs to be supplied as intrusive_ptr?
Have you read the rationale for that? Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
"Jeff Garland" <jeff@crystalclearsoftware.com> writes:
I'm glad to see someone actually use a 'conditional accept' clause -- because it seemed like we had an awful lot of 'mostly good stuff, but I reject because it won't work for me because of <fill in reason here>' reviews
I think I should be very clear that I (and Arkadiy, IIUC) was saying that it should not be accepted *under the name Boost.FSM* -- Dave Abrahams Boost Consulting www.boost-consulting.com
Hi Jody, Thanks for your review! Jody Hagins wrote:
I think the documentation is relatively complete. However, I am not exactly thrilled by the requirement on the reader to understand UML diagrams. On the other hand, this library is intended to represent UML in C++ (at least to my understanding), so I'm not sure what else can be done. A link to a basic tutorial on UML state machine diagrams would be appropriate in the "UML to boost::fsm Mapping Summary." I know you link to the 730 page OMG document on UML, but I'd also like to see something that describes the basic UML for state charts.
http://www.objectmentor.com/resources/articles/umlfsm.pdf doesn't do the trick (linked from the tutorial under Audience)?
* The library documentation contains few not yet solved issues (name, separating the library into two parts, exception handling). What is you opinion here?
I think it is obvious that the library should be separated, though I do not think this issue itself should be a stumbling block for acceptance. Exception handling is very important, and I do not buy the rationale that allowing destructors to throw is not a problem in practice.
I'm basically saying that you *usually* don't need to propagate exceptions out of exit actions. But sometimes you still need to do it and then you can use two stage exit.
I also do not think I really understand "two stage exit."
Two stage exit means that you now have two functions that are called whenever a state is exited. If present, exit() is called first and the states' destructor is called second. If you need to signal an exit action failure, you can do so by propagating an exception out of exit().
* 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 think we have to define real-time. Traditionally, real-time systems have hard completion time requirements (e.g., the XYZ event must be processed in under 50ms). Even though I have performance issues with this library, I think it can still be utilized in many real-time situations. Andreas has stated several times that the dispatch time will be small compared to the handling time.
What I meant was that if you have a typical hierarchical FSM with *empty* actions, then the time used to find the transition triggered by the current event (dispatch time) is typically small compared to what it takes to execute that transition (exit the original state configuration and enter the target state configuration). Even more so if you add non-trivial actions.
However, I find this argument a bit lacking, especially for hard real-time requirements, where each cycle taken for dispatch is stolen from the reaction handler.
I hope the argument makes more sense with the explanation above.
My current application requirements do not fit the traditional definition of real-time. However, my SMs need to be as fast as possible, because in a real sense, my code is competing with other code. Without going into too much detail, when an "opportunity" is available, it is only available to the first one to see it, respond, and take that opportunity. Thus, my real-time requirement is that I have to be faster than anyone else playing my game. I think using this library would put me at a disadvantage in that particular space.
Agreed, given that there are no other bottlenecks (network latency, etc.).
However, I do have some applications in which this library could be used successfully (if I were inclined to learn enough UML to make sense of all the details).
The documentation is clear enough about the performance issues. In fact, it may be too clear, as some people seem to see problems that may not exist in most applications.
I'm having exactly this gut-feeling ever since the performance discussion started and I'm really relieved that at least someone else thinks this way :-).
One last thing on performance, since it has been a hot topic in relation to this library. I do not think it has sufficient performance to warrant use in all my applications, and I assume the same for many others. However, it does have sufficient performance to be used in a large number of applications. If the docuemntation is clear (which it is), then users can decide when/how it can be used. I could make similar performance claims agains almost every boost library (and I have made them on this list about shared_ptr and signals). However, that does not mean we should eliminate those libraries from boost, nor does it mean that they should never have been accepted (but I would like to see a larger commitment to address performance issues in all currently accepted libraries). I would, however, like to see a separate submission which has a focus on performance,
I'd like to see that too.
and I would really like to see the performance issue of this library revisited, especially with input from some of the folks here who claim expertise in that area.
I'm willing to do that, see below.
* Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion.
Yes, with two conditions.
1. The name should definitely be changed.
Agreed.
I am not sure, however, what a new name should be. I tend to favor one of Andreas' alternatives: umlfsm.
Ugh, I'm not so fond of that name. I'd prefer Alexander's "Boost.Statechart".
2. I also think there should be some commitment to revisit the performance issues. I am not sure how this works, but I'd be satisfied with a commitment from Andreas, possibly accompanied by a request to the Boost community for assitance. I am not certain that an acceptable solution can be found, but I think the issue at least needs to be addressed again, specifically with input from the Boost community.
That's fine with me. I think it would be easiest if interested people contact me directly, so that we can look at ways to improve the performance. If we find ways to improve it *considerably* that require only small or no interface changes (and all the requirements are still satisfied), I will implement them (and I'm happy not to add the library until they are implemented). I'll leave it up to the interested people to define the acceptance process in case no ways to improve the performance are found within a certain time frame. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
On Sat, 12 Mar 2005 13:42:19 +0100 "Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> wrote:
http://www.objectmentor.com/resources/articles/umlfsm.pdf doesn't do the trick (linked from the tutorial under Audience)?
That is certainly what I was looking for, but I completely missed the link. Maybe a better place would be the introduction where you first introduce the idea of UML state machines.
Two stage exit means that you now have two functions that are called whenever a state is exited. If present, exit() is called first and the
states' destructor is called second. If you need to signal an exit action failure, you can do so by propagating an exception out of exit().
So, basically... you use exit() so that you are not technically throwing from the dtor.
What I meant was that if you have a typical hierarchical FSM with *empty* actions, then the time used to find the transition triggered by the current event (dispatch time) is typically small compared to what it takes to execute that transition (exit the original state configuration and enter the target state configuration). Even more so if you add non-trivial actions.
However, I find this argument a bit lacking, especially for hard real-time requirements, where each cycle taken for dispatch is stolen from the reaction handler.
I hope the argument makes more sense with the explanation above.
Yes, it makes more sense, but I still contend that in critical apps, every cycle used by the state machine mechanism is a cycle stolen from the handler, and these cycles could be the difference in making/missing the target deadline. In these situations, tha absolute amount of time in the dispatch is more important than the percentage of time spent in the dispatch relative to the reaction.
Agreed, given that there are no other bottlenecks (network latency, etc.).
Or, that the other bottlenecks are common enough that everyone pays them on a relatively equal footing. The cycles are even more important if the competition has lower cost in the common bottleneck areas.
Ugh, I'm not so fond of that name. I'd prefer Alexander's "Boost.Statechart".
To me, that one is a little less descriptive of what is going on, but I would be willing to accept it.
That's fine with me. I think it would be easiest if interested people contact me directly, so that we can look at ways to improve the performance. If we find ways to improve it *considerably* that require
only small or no interface changes (and all the requirements are still
satisfied), I will implement them (and I'm happy not to add the library until they are implemented). I'll leave it up to the interested people to define the acceptance process in case no ways to improve the performance are found within a certain time frame.
I would be fine with acceptance before the work was done, so long as a concrete commitment was in place to do more research on the issue. I think at this point, we are in a scenario in which no one has spent significant time investigating the newly proposed issues (unless Andreas has already tried the ones being proposed). Thus, we can only talk about possible solutions, and since no one has real answers, it seems to me that our collective intelligence and good nature is turning into technological hubris, thus preventing us from making much progress in this discussion. I've been there before, and it ain't a pretty picture, even for the party that turns out to be right. Thus, it seems that Andreas is not planning to make significant performance changes, and he has doubts as to the possibility that such changes are even possible. However, he has agreed to make a solid attempt to address the issues after acceptance (with the help of any volunteers), if such acceptance is granted. Maybe we should ease up a bit on the details of performance until such time as the library is either accepted or rejected. Then, we can resume such discussions as appropriate to the situation and goals of the library.
Jody Hagins wrote:
On Sat, 12 Mar 2005 13:42:19 +0100 "Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> wrote:
http://www.objectmentor.com/resources/articles/umlfsm.pdf doesn't do the trick (linked from the tutorial under Audience)?
That is certainly what I was looking for, but I completely missed the link. Maybe a better place would be the introduction where you first introduce the idea of UML state machines.
These links will be in index.html under Audience, I hope that's a better place.
So, basically... you use exit() so that you are not technically throwing from the dtor.
That's only part of the game, exit() is only called if there isn't already an exception pending.
What I meant was that if you have a typical hierarchical FSM with *empty* actions, then the time used to find the transition triggered by the current event (dispatch time) is typically small compared to what it takes to execute that transition (exit the original state configuration and enter the target state configuration). Even more so if you add non-trivial actions.
However, I find this argument a bit lacking, especially for hard real-time requirements, where each cycle taken for dispatch is stolen from the reaction handler.
I hope the argument makes more sense with the explanation above.
Yes, it makes more sense, but I still contend that in critical apps, every cycle used by the state machine mechanism is a cycle stolen from the handler, and these cycles could be the difference in making/missing the target deadline.
Absolutely. [snip]
That's fine with me. I think it would be easiest if interested people contact me directly, so that we can look at ways to improve the performance. If we find ways to improve it *considerably* that require
only small or no interface changes (and all the requirements are still
satisfied), I will implement them (and I'm happy not to add the library until they are implemented). I'll leave it up to the interested people to define the acceptance process in case no ways to improve the performance are found within a certain time frame.
I would be fine with acceptance before the work was done, so long as a concrete commitment was in place to do more research on the issue.
I think at this point, we are in a scenario in which no one has spent significant time investigating the newly proposed issues (unless Andreas has already tried the ones being proposed).
Nope, answering posts more than fills of what I can invest at the moment ;-). Thus, we can only talk
about possible solutions, and since no one has real answers, it seems to me that our collective intelligence and good nature is turning into technological hubris,
Do you mean hubris as defined in http://en.wikipedia.org/wiki/Hubris?
thus preventing us from making much progress in this discussion. I've been there before, and it ain't a pretty picture, even for the party that turns out to be right.
I don't think that turning out to right is the point of the performance discussion.
Thus, it seems that Andreas is not planning to make significant performance changes, and he has doubts as to the possibility that such changes are even possible.
As I have already mentioned to Dave, I do have a few ideas (O(1) dispatch seems theoretically possible for non-orthogonal machines)that I'm going to try as soon as I have more time. I see a few obstacles for which I don't yet have solutions. I guess I'll post the details to the developers list so that other brains than my increasingly biased one can think about it. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
Jody Hagins wrote:
On Sat, 12 Mar 2005 13:42:19 +0100 "Andreas Huber" <ahd6974-spamgroupstrap@yahoo.com> wrote: [...] Thus, it seems that Andreas is not planning to make significant performance changes, and he has doubts as to the possibility that such changes are even possible. However, he has agreed to make a solid attempt to address the issues after acceptance (with the help of any volunteers), if such acceptance is granted. Maybe we should ease up a bit on the details of performance until such time as the library is either accepted or rejected. Then, we can resume such discussions as appropriate to the situation and goals of the library.
One thing that bothers me about the performance discussion is that some parties seem to imply that there exists a single best point in the design space, and that the proposed library has not found it. Given all the different constraints and values that can differ from application context to application context and user to user, I hardly see how such a stance is justifiable. Without having followed the discussion too closely or reviewed the library in any depth, I would have to say that my impression is that Andreas has put together a reasonably solid library with decent rationale for his design decisions. And isn't that Boost is interested in? Quality libraries that put correctness first and performance second? I don't believe Andreas has at any point claimed that his library is the fastest possible implementation of FSMs in existence, so why should it be held up to that goal? If the library meets the stated design goals, and if those goals are useful to a significant number of people, then the library has real utility, no? I believe that in discussions of other libraries, it has been pointed out that Boost does not exclude the possibility of overlapping libraries when there is a reason to do so. If someone else would like to propose a fast FSM library that has different design goals, possibly including performance as a primary goal, then I don't see why such a library could not co-exist with the one that Andreas has built. I don't see why such a library *should* not co-exist. What I like about C++ is choice. I like the fact that I can work with big fat structures like std::map<> or fast simple structures like builtin arrays. I like the fact that nobody decides for me ahead of time what design decisions I must make in selecting prebuilt components. I use iostreams when I can, and cstdio when I must. In fact, I did exactly that in some recent utilities that had to work on fairly large files. Is it bad that C++ has both I/O libraries? Not at all. I can write iostream code much faster than cstdio code, and more correctly with less referral to documentation. But the simple fact is, cstdio is faster, hands down. When I need the extra speed, I have that option. When I don't, I will cruise in the luxury of iostreams. I like to use std::string, warts and all. It's easy. It's convenient. It's even better than Java's String. ;) But sometimes I have to get down to char* and dirty pointer arithmetic, and that's ok. Maybe Andreas has produced the iostreams of the FSM world. I consider that A Good Thing. Maybe someone else knowledgeable about and concerned with performance will write the cstdio version. That would also be A Good Thing. But the idea that for this domain, there is a unique best solution has not thus far been defended, and I strongly suspect that such a position is, in fact, indefensible. This library already has users before becoming a Boost library. That implies that people already find it useful. It will be a sad day when Boost rejects a good library because another library in a different part of the design space is theoretically faster. Dave
Hi Dave, On Mon, Mar 14, 2005 at 06:13:19PM -0600, David B. Held wrote:
One thing that bothers me about the performance discussion is that some parties seem to imply that there exists a single best point in the design space, and that the proposed library has not found it. Given all the different constraints and values that can differ from application context to application context and user to user, I hardly see how such a stance is justifiable. Without having followed the discussion too closely or reviewed the library in any depth, I would have to say that my impression is that Andreas has put together a reasonably solid library with decent rationale for his design decisions. And isn't that Boost is interested in? Quality libraries that put correctness first and performance second? I don't believe Andreas has at any point claimed that his library is the fastest possible implementation of FSMs in existence, so why should it be held up to that goal?
There is no doubt ( in my mind ) that Andreas has done some very good work. The issue is whether this library is suitable for acceptance into boost. IIUC boost is predominately about best of breed libs. The primary philosophy in C++ is you don't pay for what you don't use. Andreas has deliberately taken a different approach. He has chosen to go for the all singing, all dancing heavey weight approach. He has explained his approach on this list. You pay for State Specific Storage whether you want it or not. You currently get non-linear event dispatch ( without orthaganal regions ) if you use outer states. And you get horrible performance on transitions ( with loss os state specific storgge when you transition out of a state ). I know that if Inhand write a GOF state pattern I can get close to the scaleability of the FSM lib but with constant time event dispatch through a single indirection and can change state through a single assignment. FSM is the domain but whether itnis spelt STT of StateChart is irrelevent one can be mechanucally collapsed to the other. But the fsm proposal does not do this. If we have a StateChart lib in boost it should scale as wel as any other library in booat IMHO /ikh
Iain K. Hanson wrote:
[...] There is no doubt ( in my mind ) that Andreas has done some very good work. The issue is whether this library is suitable for acceptance into boost. IIUC boost is predominately about best of breed libs.
Yes. And sometimes there is more than one best in the breed.
The primary philosophy in C++ is you don't pay for what you don't use.
...And yet, we have iostreams.
Andreas has deliberately taken a different approach. He has chosen to go for the all singing, all dancing heavey weight approach.
...Much like shared_ptr<>, which got into TR1. And I dare say that shared_ptr<> is used in far more performance sensitive contexts than the FSM. If we declared that shared_ptr<> is the end-all, be-all smart pointer for C++, I would be as unhappy as you are.
He has explained his approach on this list. You pay for State Specific Storage whether you want it or not. You currently get non-linear event dispatch ( without orthaganal regions ) if you use outer states. And you get horrible performance on transitions ( with loss os state specific storgge when you transition out of a state ).
And if that were a deal-breaker, people wouldn't be using the library, would they? Apparently, there are applications where these are not the critical metrics, and people have already found use for it.
I know that if Inhand write a GOF state pattern I can get close to the scaleability of the FSM lib but with constant time event dispatch through a single indirection and can change state through a single assignment.
But can you provide all the other features of the FSM proposal? If not, then you're comparing apples to oranges, right?
FSM is the domain but whether itnis spelt STT of StateChart is irrelevent one can be mechanucally collapsed to the other. But the fsm proposal does not do this.
If we have a StateChart lib in boost it should scale as wel as any other library in booat
I'm not quite sure what you're saying here, but clearly there is precedent for solutions at different granularities/complexities /performance tradeoffs in Boost. Consider tokenizer/regex/spirit. Consider compose/bind/lambda. If you think that Boost needs a low-level FSM that concentrates on performance over abstraction, you may be right. But if you think that it does not need an FSM library that focuses on abstraction and ease of use, it would appear that some users might disagree with you. Dave
| -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of David B. Held | Sent: 15 March 2005 00:13 | To: boost@lists.boost.org | Subject: [boost] Re: FSM Review | It will be a sad day when Boost rejects a good library because | another library in a different part of the design space is | theoretically faster. IMO this hits the nail on the head. As with too many reviews, there have been very interesting, but essentially speculative, alternative ideas, produced not during the 'proposed library' development phase, but somewhat destructively and at the 'last minute'. These should not be a reason for rejection, but should spur development of different (and hopefully in some ways better) ideas to submit in future. Paul Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539 561830 +44 7714 330204 mailto: pbristow@hetp.u-net.com
participants (12)
-
Alexander Nasonov -
Andreas Huber -
David Abrahams -
David B. Held -
Gennadiy Rozental -
Iain K. Hanson -
Jeff Garland -
Jody Hagins -
Matthew Vogt -
Paul A Bristow -
Pavel Vozenilek -
Peter Petrov