I had the pleasure of talking to some fellow state machine enthusiasts at DevDays in Munich. Here are some of the topics that were brought up, in randomized order:
Verification. How can you check that your state machine is sane, or rather, how can you disprove that it’s criminally insane? Currently there isn’t a way to do that. We tried to design the API so that many (most?) semantic errors will be caught at compile time. But that doesn’t get us all the way, unfortunately; what happens if you forget to specify the initial state of a compound state, for example? The QStateMachine::error() signal is there to report such cases; if the state machine detects a semantic error at any stage of executing its algorithm, it emits the error() signal. But maybe it would be nice to have a function that can run a set of standard sanity checks before the machine is started?
Performance. We currently implement the SCXML algorithm more or less exactly as it’s specified. I don’t yet know how well it scales wrt number of states and transitions; well, I have one benchmark where the running time grows exponentially, but there are many different configurations that need to be investigated (flat vs nested state machines, sequential vs parallel states, custom events and transitions vs built-in ones, etc.). Is anyone out there creating state machines with thousands of states, and if so, are you seeing performance issues?
Lazy population of states. For large compound states, it can make sense to only create the contents of the state when (if) the state is actually entered. To do that, you need only create an initial state, and reimplement QState::onEntry(). You need to create the initial state because the state machine will request it _before_ the compound state is entered (and QState::initialState() is not virtual…). In your onEntry() implementation, use a flag to check whether the state is being entered for the first time, and if so, create the remaining child states and add transition(s) to them from the initial state, as appropriate. The state machine actually does similar kinds of lazy initialization internally; the signal associated with a QSignalTransition is only connected when the transition’s source state is entered, for example.
Debugging. There’s no straightforward way to debug state machines in Qt 4.6. What’s needed first is a “debugger client” interface that the state machine can use to deliver notification of e.g. state changes. This interface would then serve as the basis of debugging tools. It would be nice to have a visual representation of the machine (tree view?) highlighting the current state, be able to “step” the state machine execution, set breakpoints on transitions, inspect the event queues, and so on. P.S.: If you’re building Qt from sources, there’s a QT_STATEMACHINE_DEBUG define that you can enable in qstatemachine.cpp; this will cause the state machine to spew out a log of everything it’s doing. This output can be difficult to parse humanely, though, especially when your machine has nested states.
Why QtCore? Couldn’t the state machine framework be in a library of its own? Yes, it could, but we chose to put it in QtCore so it can easily be used anywhere, without introducing new dependencies. The QtCore library grows by about 5% (150K) due to the state machine classes. Note that it’s still possible to remove the framework from compilation by using the qconfig tool, just like you can with the animation framework (also part of QtCore) and several other features in Qt.
Multithreading. How do you use state machines with threads? Well, there are a few things you should know. Firstly, the state machine classes are reentrant, meaning you can have multiple state machines running at the same time (one per thread, say). Secondly, the QStateMachine::postEvent() function is _not_ thread-safe, meaning that it’s not safe to call postEvent() on the _same_ machine from different threads; you’ll have to manage the synchronization yourself if you want to do so (but maybe QStateMachine::postEvent() should be made thread-safe, like QCoreApplication::postEvent()?). Thirdly, if you’re using signal transitions, there is no restriction on whether the object emitting the signal lives in the same thread as the state machine or not; the state machine will always create a connection of type Qt::AutoConnection, meaning that the connection will be queued if the object lives in a different thread. This means that the state machine can be processing events in its own thread concurrently with the signal being emitted in another thread, without you having to worry about synchronization.
See you in San Francisco, maybe?
No related posts.
13 comments
do you know if the time table for SF is the same as for Munich? I missed your talk there because I was giving mine (Qt In Use).
Was hoping to discuss integrating the Qt state machine with the one in Coin… hopefully in SF
Yes, it would be nice to have QStateMachine::postEvent() thread safe. I don’t do very complex state machines, but I do use multiple threads. And the later is in the air.
Something else that would be very useful is a graphical state machine designer that includes the ability to “promote” to custom states, transitions, and events. The view for such a tool would also be a nice component to use in any state machine debugger tool (as opposed to a plain tree view). When a state machine is loaded in the design tool it then also becomes self-documenting.
Hi, Kent! I’ve very enjoyed your presentation about QScript. And then I saw the one about State Machines, and it was stunning! (especially considering the field I come from). Great job, thanks!
Please make QStateMachine::postEvent() thread safe. I don;t know how you can justify it not being thread safe. It would severely limit its ability to scale.
The agenda for SFO is the same as the one for MUC.
I agree with Sean. Certainly a graphical state machine designer would be useful when designing the state machine. However, QStateMachine::postEvent() should be thread safe and should have priority over the designer. Having QStateMachine::postEvent() thread safe maintains consistent behavior with QCoreApplication::postEvent(), which is what a developer would expect.
Should we make a GUI tool to create state machine?
derekhe: Currently we don’t have any plans to create a statecharts tool. You’ll have to use an existing tool (or draw by hand), and manually code it as a QStateMachine. Alternatively, if the tool supports exporting to XML you can perhaps use XSLT to transform it into SCXML and feed it to Qt-SCXML (I’m not aware of any tool that can export directly as SCXML yet).
I’ve recently attempted to introduce the SMF into a game server that I am writing, and there is definitely potential.
The idea of binding transitions unconditionally to emitted signals is however causing me quite a bit of grief.
Let me explain.
A game instance changes its state not only depending on the game progress, but also based on the number of players in the game.
For instance, if the game is waiting to start, it must switch to a “READY” state once enough players have joined (ie. by listening for the playerCountIsTwoOrMore() signal.
Unfortunately, that signal is also needed during game play, as game logic changes depending on the number of players left alive in the game. Again, a state change (but a different one) must occur when the playerCountIsTwoOrMore() signal is emitted.
Unfortunately, (afaik) there is no way to handle this automagically in SMF (one particular signal always causes a state change to a fixed target state). Thus, I am left with the task of having to write glue code to perform one state change if the machine is currently in state X, and another state change if the machine is in state Y.
Wouldn’t it be possible to internalize such “conditional” state changes in the SMF, so as to avoid writing excessive amounts of glue code in user applications?
Ie. “if the machine is currently in state X and signal Q is emitted, fire transition Y, otherwise fire transition Z”.
Any thoughts?
boll: I might not understand entirely what you’re trying to do – but if I do understand it correctly it’s possible in QSMF.
All you have to do is create 2 transitions based on the same signal, and re-implement QAbstractTransition::eventTest (http://doc.trolltech.com/4.6-snapshot/qabstracttransition.html#eventTest) to differentiate between them.
If you need to query the state machine for its active states, you can use QStateMachine::configuration() in the eventTest reimp.
In general using QSignalTransition and the other QAbstractTransition subclasses would give you that kind of power, while QState::addTransition ( QObject *, const char *, QAbstractState *) is more of a simple-case syntactic sugar.
I raised the scalability issue with the SCXML w3c committee, and also analyzed the algorithm a bit.
The complexity of the SCXML algorithm (which we’re using) is not determined by the number of states, but by the amount of states that can run concurrently (i.e. children of parallel state groups).
A good way to address this scalability issue, if relevant, is by using sub-machines when possible (http://labs.trolltech.com/blogs/2009/07/23/qstatemachines-a-state-too/), and handle events that are only relevant to a particular sub-tree inside the additional QStateMachine.
Hi guys,
Due to popular demand, QStateMachine::postEvent() and friends have been made thread-safe.
Comments on this entry are closed.