[Development] Implementing QStateMachine using QtScxml module

[Jaroslaw Kobus]

Hi All,

recently I was investigating the possibility of replacing the internal implementation of QStateMachine
with QtScxml module. See https://bugreports.qt.io/browse/QTBUG-70261. Below I have gathered
some results and some conclusions. However, at this point it's not clear in which direction we should go,
so if anyone is interested in this topic and has some ideas or thoughts - please share them! Thanks!

====================
I. The initial idea:
====================

Replace the implementation of QStateMachine with QtScxml module. Upon every startup of QStateMachine
we would parse the state machine tree and create internally the QScxmlStateMachine document. QtScxml
module would then use it to instantiate QScxmlStateMachine and run it.

Pros:
1) One common codebase for both QStateMachine and QScxmlStateMachine
2) Smaller codebase

Cons:
1) Additional delay upon startup (parsing the QStates hierarchy, constructing the scxml document)
2) State machine structure can't be modified when it's running (currently we have some autotests
   which modify the structure when running, e.g. eventTransitions(), createPointerToMemberSignalTransition(), etc... ).
   This means that API won't change, the behaviour will change.
3) Slower running time due to used mappings (between scxml ids and pointers to QState objects)
   and two additional signal/slot connections for every state (connectToState,
   connectToEvent(finished., ...)). For every transition we also provide additional transition to be
   invoked by the eventless transitions on startup. Also, for every state we provide additional transition
   to react to "done.state." events.
4) Additional memory consumption due to internal scxml state machine

-----------
Benchmarks:

I've created a test case consisting of the state machine containing 10000 states,
chained together with transitions from state n to state n+1.
Transitions are being triggered by custom event. Whenever the state n
is being reached, it posts a custom event to the state machine,
what causes the next transition to be taken.

Construction of the state machine + startup time
(with new implementation it includes dynamic construction of scxml doc):
[old implementation]: about 50 ms
[new implementation]: about 620 ms

Running time (transitions from state 1 to state 10000):
[old implementation]: about 100 ms
[new implementation]: about 220 ms

-----------------------
State of the prototype:

Examples:

All examples are working with the new implementation.

Autotests:

3/4 of all statemachine autotests are passing now. Some had to be a bit modified
(e.g. additional call to processEvent()). 89 working out of 122 in total.
To be fixed:
- Handling state machine errors
- Running sub state machine
- Some tests can't be fixed (changes to the state machine structure during execution)

The prototype can be found here:

https://codereview.qt-project.org/c/qt/qtbase/+/271082

-----------
Conclusion:

In this approach we have a lot of data duplicated. We have:
1. QState hierarchy.
2. On state machine startup we create dynamically scxml document.
3. The scxml document is being parsed and scxml tables are being created.

It looks like this approach degrades performance and increases memory consumption.

===============
II. Comparison:
===============
So far I have compared the old implemenation with the new prototype
and the old implementation wins according to the points below.
However, it's not clear yet, and it probably should be investigated,
whether QtScxml is really faster than QStateMachine(!) In the prototype
I have glued together two existing APIs, but it may be worth to check
whether having another API instead of QStateMachine API and gluing it
with QtScxml would speed up execution.

While comparing different implementations of state machine
we should take the following into account:
- What is the ideal case / example / test to compare the speed of state machines?
  Is 10000 states case OK?
- Should we compare construction time / execution / or both?
- Should we compare memory consumption?

==============
III. Other options:
==============

Option A)
If we change the API of QStateMachine, so that we don't base QState on QObject,
we could at least save some memory and time spent on constructing the state machine.
However, we would have to take into account that QStateMachine
supports animations and property assignments currently, which QtScxml module doesn't support
out of the box. Please note that designing new general API is quite time consuming task.

Option B)
We could also try to start from refactoring the scxml document API, so that it would
serve as a public API, too. Currently there are too much internals and low level stuff exposed there,
so it doesn't fit for the public API ATM.

Option C)
?

Option D)
?

Thanks and regards

Jarek