Hi @tylerweaver
Thank you for bringing up a very interesting topic. You’ve got a lot a questions here, so I’m responding inline to make sure that I get to all of them.
Anyways, let’s get down to it…
I’m curious how SMACC differs from [boost].SML (https://boost-ext.github.io/sml/ 4). I’ve been using SML in many projects recently and I really like it’s declarative syntax. I see that SMACC is built on Statecharts which for all the nice features it has I found the syntax much more cumbersome than SML. What are the features that SMACC offers that would make it worth using over SML?
Well, SMACC offers a number of features beyond just SML or Boost Statechart.
- SMACC provides tight integration with ROS and users are able to generate events using ROS topics, services and actions; right out of the box.
- SMACC offers a library of reference state machines, so that you don’t have to start your application from scratch; right out of the box
- SMACC offers a library of clients (such as MoveBaseZ and MoveItZ) that allow ROS users to control ROS packages like MoveBase, MoveIt!, ros_control, generic ROS publishers, and many more; right out of the box.
- SMACC comes with a SMACC Viewer that allows you to view the complete layout of your state machine and monitor performance during runtime, which is particularly helpful for debugging.
I notice on your website you compare Statecharts and MSM (Statechart vs MSM | SMACC – State Machine Asynchronous C++) and to do that you use a slide from a talk by the the author of SML and yet don’t seem to address it as an alternative to Statecharts or MSM. Looking through your website I found it hard to understand how I would use SMACC and what benefit it would offer over SML.
For the development of SMACC, we researched the two Boost libraries, Boost Statechart and MSM which were both written in the same era. SML came later. But SML is basically an updated, and stripped down version of MSM. At the time I wrote that page, less information was available for SML.
But let’s talk a little about the differences between Boost Statechart and SML…
Asynchronicity
-
Boost Statechart supports Asynchronous State Machines, Boost SML does not.
-
Boost Statechart is thread-safe by default, SML is not.
And while it’s true that SML allows you to define your own thread policies, as we’ll see later that can get real complicated for the user (if not impossible) once he has to take asynchronicity, hierarchy, orthogonals within hierarchy and multiple complex orthogonals into account, along with normal things like logging.
References
See Features/Benchmarks - [Boost::ext].SML under “Non-UML features”
See Overview - [Boost::ext].SML under “Thread Safety”
See User Guide - [Boost::ext].SML under “Thread Safe Policy”
Complexity
Boost Statechart allows you to build state machines that are an order of magnitude more complex than those possible with SML.
-
Boost Statechart allows you to have per-state transition tables, whereas Boost SML has a only a single global transiton table.
-
Boost Statechart allows you to spread your state machine over multiple translation units (Each state is a file, each orthogonal is a file, etc).
-
SML doesn’t really support Hierarchal State Machines, see below…
References
See The Boost Statechart Library - Rationale - 1.73.0 - Item #6
See Statechart vs MSM | SMACC – State Machine Asynchronous C++ First Chart, Column 3
Hierarchy
• Boost Statechart allows you to build hierarchal state machines, where states are classes and have parent states, with theoretically unlimited levels hierarchy.
• Boost Statechart also supports deep history (as opposed to shallow history) which enables advanced recovery procedures across different nested states.
• In SML when you want to introduce a hierarchal relationship into your state machine, you have to nest a new state machine inside of your current state machine.
And this approach taken by SML creates numerous problems, with data, transitions, event handling, and more. And because of this, I’m of the opinion that SML does not truly support hierarchal state machines.
Further, a quick view of the Open Issues on the SML Github page shows a substantial amount of open tickets related to hierarchal state machines that illustrate the numerous problems resulting from SML’s approach, some being open now for over 4 years…
See… Issues · boost-ext/sml · GitHub
`c_str()` overload for sub state machines · Issue #326 · boost-ext/sml · GitHub - (3/20/2020) - Status: OPEN
c_str() overload for sub state machines
Advanced hierarchical state machine support · Issue #289 · boost-ext/sml · GitHub - (8/2/2019) - Status: OPEN
Advanced hierarchal state machine support
How to access data members in a submachine when entering & exiting and from it's substates · Issue #266 · boost-ext/sml · GitHub - (4/29/2019) - Status: OPEN
How to access data members in a submachine when entering & exiting from it’s substates
How to model hierarchical state machines with Boost.SML · Issue #185 · boost-ext/sml · GitHub - (7/26/2018) - Status: OPEN
How to model hierarchal state machines with Boost.SML
Substate entry action is not actioned on entry. · Issue #122 · boost-ext/sml · GitHub - (6/28/2017) - Status: OPEN
Substate entry action is not actioned on entry
BOOST SML handling Hierarchial State Machine · Issue #111 · boost-ext/sml · GitHub - (6/21/2017) - Status: OPEN
BOOST SML handling Hierarchal State Machine
Handling events in nested and outer state machines · Issue #84 · boost-ext/sml · GitHub - (12/27/2016) - Status: OPEN
Handling events in nested and outer state machines
Composing finite state machines recursively · Issue #83 · boost-ext/sml · GitHub - (12/14/2016) – Status: OPEN
Composing finite state machines recursively
Marking initial state in transition that originates from its nested state · Issue #44 · boost-ext/sml · GitHub - (6/2/2016) - OPEN
Marking initial state in transition that originates from its nested state
**Issue 185 is particularly worth checking out. Scroll to the bottom of the (still open) issue and you’ll see the following entry by the user erikzenker…
In contrast, hierarchy is easy in Boost Statechart and SMACC. Here are some examples from the SMACC Library…
And here…
.
References
See Tutorial/Workshop - [Boost::ext].SML “A state machine may be a state inself”
See Examples - [Boost::ext].SML “in sub sm”
See Examples - [Boost::ext].SML
State Local Storage
- In Boost Statechart, states are classes, and like normal classes state can have member functions and member variables. This is referred to has state local storage, and this makes Boost Statechart better suited for behavioral state machine applications, where you actually want your state do something, as opposed just having the state machine do things on the transitions between states.
- In SML, states are basically just labels, and all resource handles and variables are stored in the state machine.
More on this below…
References
See Behavioral vs Protocol State Machines | SMACC – State Machine Asynchronous C++
I re-watched the talk that the slide on your website is from(https://www.youtube.com/watch?v=yZVby-PuXM0) and it reinforced all the reasons I wouldn’t want to use Statecharts.
The video you are referring to was from a talk given by Kris Jusiak, who is the author of Boost.SML, and unsurprisingly he thinks Boost SML is the best ( and I have no problem with authors thinking their library is the best) but…
The benchmark tests that he uses as the basis of his arguments, in my opinion don’t really represent likely real world scenarios. For instance, in all of his performance tests, the SM processes 1 million events, something I think would be very unlikely for an asynchronous robot running ROS.
But more on this below…
On your website you seem to dismiss performance concerns by saying that if you are building a “real robot” you don’t care about determinism and high loop rates and if you actually do care (your examples are an icbm and low cost uC), you will just write it in c99. I think this is a bit of a strawman argument by using such extreme examples. If I’m using C++ I do care about performance and the state machine library you chose has known issues with runtime performance. Called out in that cppcon talk are dynamic allocations, dynamic dispatch, and a high memory footprint.
I’ve never said that I don’t care about determinism, because I do care about it, and I’m going to instrument the library with LTTNG to ensure that SMACC is completely deterministic.
And maybe I’m being a little triggered by the word “strawman” but it is not a strawman argument to say that you don’t recommend someone using your library for certain applications, but I digress…
Anyways, let’s get into the issues Kris Jusiak raises of dynamic allocations, dynamic dispatch and high memory footprint…
Memory Footprint
While the Memory Footprint of Boost Statechart is higher than SML, it’s not high enough to be concerned with in a ROS based system. In the features/benchmark page of the Boost SML site, even the “Complex State Machine” benchmark test (the largest state machine tested, where the state machine consisted of 50 States, 50 Events and 50 transitions) the memory footprint only came to 200 bytes.
Dynamic Dispatch
The ability to build state machines with Boost Statechart that are an order of magnitude more complex than with SML (or MSM) comes with a cost…
In Boost SML, event dispatch is handled via function pointers. This is extremely fast, but requires that the entire state machine be confined to one file/translation (compilation) unit*.
In Boost Statechart, event dispatch is handled via a virtual call is followed by a linear search for the appropriate reaction, using one RTTI comparison per reaction. Although this technique is not as fast as the one used by SML (and MSM), it is this method allows the state machine to be distributed over multiple translation units.
For more information on this,
See The Boost Statechart Library - Performance - 1.73.0
See Boost mailing page: Re: [boost] [msm] Review
*Note: While it may be theoretically is possible for a developer to distribute a state machine written in SML over several translation units, the developer would then have to somehow manually connect all the pieces of the state machine together, which does not scale and is prone to error.
Dynamic Allocation
This is most important factor for state machine performance, and is related to Boost Statechart being a behavioral state machine library and providing State Local Storage.
In Boost Statechart, states are classes that are instantiated upon state entry, and destroyed upon state exit. In SML by contrast, because the states are basically labels, there is no time spent on memory allocation.
Performance
And it is true, that these factors (dynamic dispatch and dynamic allocation), make Boost Statechart an order of magnitude slower than SML at processing events, when benchmarked inside of the very simple state machines that SML can actually support. But it doesn’t really matter, because Boost Statechart is still really fast.
For instance, on the features/benchmarks page, in the test involving the “Composite State Machine” compiled with GCC-5.2, despite being slower than Boost SML, Boost Statechart still processed one million events in 404ms. This comes to a speed of approximately 2.5 MHz.
Even for the test involving the “Complex State Machine” (where as mentioned before the state machine consisted of 50 States, 50 Events and 50 transitions), Boost Statechart was able to process one million events in 5.52 seconds. This comes to a speed of approximately 181 KHz. – Still easily fast enough for ROS applications.
And of course the tests on this page do not specify what hardware these machines were running on, so one should not look at this and think that Boost Statechart is somehow limited to these speeds.
So to summarize. It’s true that Boost Statechart is slower than Boost SML, but it’s fast enough.
And if you’re operating in an asynchronous environment, you probably aren’t processing a million events per second. And then you are probably concerned with other performance metrics not covered in the tests referenced above.
One last important point is that in future development, we (SMACC) plan to really maximize our performance by utilizing our ability to use custom allocators, where we would give applications that require super high performance the ability to do things like pre-allocate states at the beginning of the program, cache states, etc. As mentioned before, this (state destruction and construction) is the main cause of the performance differences between Boost Statechart and SML…
References
See The Boost Statechart Library - Performance - 1.73.0 “State entry and exit: … roughly 3 quarters of total event processing time is spent destructing the exited state and constructing the entered state”
See The Boost Statechart Library - Performance - 1.73.0
See Features/Benchmarks - [Boost::ext].SML
You also seem to care allot that you can put variables in your states as a supported feature of the state machine library you chose. I don’t understand why you have this requirement and why the type based system in SML is worse.
It’s worse because you don’t have the ability to scope resource handles or variables, to the lifetimes of the states that use them. Leaving you with only the option of using essentially global variables, all stored in one place (like the “data” class shown here Examples - [Boost::ext].SML ) and making sure you don’t screw that up somehow.
And as your state machine gets larger, you wind up with a large number of resource handles and variables stored in that data class, most of which are only needed by some small portion of the state machine at any one time.
And you’re right that I do care a lot about the ability to put variables (and resource handles, transitions, behaviors, reactors, etc.) inside of states. Because it allows you to build behavioral state machines as opposed to simply protocol state machines.
In SML, and other protocol state machines, you’re limited to doing everything (via actions) on the transition. Which I submit is awkward for when you want to express complex robotic behaviors for a given state.
Maybe you want variables in a superstate so that you can loop through a sequence a number of times like we did here…
Or you might want to synthesize information from multiple orthogonals in the state and act on it like we did here…
Another fact that I think illustrates that it is more natural for programmers to scope variables and resource handles used by a state to the lifetime of the state that uses them, is that that all of the python-based state machine libraries such as SMACH and Flexbe (which have their own problems) also provide state local storage with what they refer to as userdata.
And here is an open SML issue with a user complaining about exactly this issue…
Examples of states with data · Issue #259 · boost-ext/sml · GitHub - Examples of states with data (4/4/2019) - Status: OPEN
References
See The Boost Statechart Library - Rationale - 1.73.0
See The Boost Statechart Library - FAQ - 1.73.0
See Boost mailing page: [boost] Re: Storing variables in states [was: Re: RE: Re: overloads-20050207.tar.gz]
See Boost mailing page: [boost] Storing variables in states [was: Re: RE: Re: overloads-20050207.tar.gz]
See Boost mailing page: Re: [boost] [msm] Review
If I’m using C++ I care about performance (determinism, utilization, etc) even if I’m not running on a micro-controller. Why would I want to use an old state machine library (Statecharts) that has known performance problems compared to SML?
As I mentioned above, because you can build state machines that are far more complex and are still more than fast enough.
It’s true that Boost Statechart is an older library, which is both good and bad. On the good side, Boost Statechart has been used in industry now for 16 years. And let’s also remember that [boost].SML is not actually a Boost library. It simply aspires to be one, and is trying to get accepted by Boost….
But on the bad side, it is true that Boost Statechart is getting a little long in the tooth, and will probably need an upgrade in the next 5 years. We (SMACC) are aware of this and are working on plans to support and maybe add some updates to the library.
We generally are working on complex robot systems using manipulators with moveit and have found SML to be really nice for our applications
That’s cool. I’m glad you like SML for your applications.
But in the interest of furthering the discussion, do you have some code we could see?
That way we could compare code side by side.
For myself, I would be very curious to find out things like…
How did you handle the asychronicity issue? Did you just use a bunch of sleep() functions?
Or did you use multiple threads? If so what thread policy did you use?
How did you handle data?
How did you handle orthogonals/different subsystems?
How would you handle, SM’s with both orthogonals, and hierarchy?
It would also be very interesting if you could share what some of performance requirements were for these projects such as …
How fast did they run (in Hz)?
I’m going to guess that it was somewhere between 10Hz – 50Hz. Maybe I’m way off and they ran at 500Hz. Either way, these speeds are way below the performance limitations of Boost Statechart as described above.
Also, how many events were you typically responding to per second?
I’m going to guess that it’s less than 100. Which leaves some room between there and the 1 million events used in the SML-Boost Statechart performance benchmarks.
Conclusion
At their core, SML and Boost Statechart, have distinctly different models of state machines, with Boost Statechart being more focused on the states and with SML placing almost all of the functionality into the state machine. This gives SML the edge in event processing speed while Boost Statechart has the ability to build far more complex state machines. And between these two, I believe that the the advantages accrue to Boost Statechart, in the realm of robotics, due to it’s asynchronous nature, as…
- The number of orthogonals/physical subsystems on the robot increases…
- The complexity of the orthogonals/physical subsystems themselves increase (think the NavStack vs a low battery sensor)…
- As the frequency of modifications made to the orthogonals/physical subsystems in order to meet varying mission requirements increases (think of the different F-16 missile payloads for different missions)…
- The mission complexity of the robot increase (demanding more states, hierarchy, advanced recovery sequences, etc.)
Anyways, I hope this post shed some light on SMACC, and the differences between SML and Boost Statechart.
Cheers.
