[boost] [msm] scalability

Subject: [boost] [msm] scalability
From: Christophe Henry (christophe.j.henry_at_[hidden])
Date: 2009-11-24 09:57:04

Hi Simon,

> I think it would be worthwhile talking a little more about compile time performance in the documentation.

You're right, I could explain more in the documentation.
Unfortunately, the answer is not straightforward.
The compilation time (and how far the compiler plays with us) depends
on a number of factors:
1) the compiler
2) the compiler version
3) even your hardware (I get very different compile times on 2
different machines with the same processor)
4) the state machine structure and the chosen front-end

1) usually, g++ crashes later than VC and needed fewer workarounds
2) Surprisingly, g++4.2 > g++ 4.4. VC10 > VC9 > VC8
3) you will need RAM, especially with VC8
4) the compile-time is proportional to the number of transitions in
the transition table and to the depth of the state machine (meaning
submachine of submachine of...). EUML will cost you much more with VC
than g++ as it implies a metaprogramming layer above the standard
metaprogramming of the standard front-end and because the underlying
decltype/typeof seems much better implemented with g++ (if you don't
count the generated code size).

A small test with VC9 in Release mode (and no other code) gave me:
20 transitions => 11s
30 transitions => 16s
40 transitions => 22s
50 transitions => 31s

This is just to give you an idea as it can greatly depend on the
factors named above.

> Also I'd like to see some suggestions of how to improve compile times (and how factors including the number of entries in a transition table affect the compile time).

There is just one solution: reduce the number of transitions. The best
way to do it is using orthogonal regions. For example, if you see in
your diagram many transitions to a single state based on the same
event, you should factor them all into a second region.
Adding submachines could help in some cases. On one hand, the compiler
now has to generate code for a second machine, OTOH it reduces the
number of transitions in the main one. This will only help if your
submachine handles a small number of events, as Msm will add a row in
the main table for every event of the submachines. If you can in
exchange reduce the number of transitions, it can help.

> Is there provision to split a machine across multiple compilation units (I assume not)?

You unfortunately assume correctly, as what costs compile-time really
is the heavy metaprogramming.

> You include instructions for how to increase the maximum size of an MPL vector, but this only works up to 50 entries.  What do we need to do to increase this further?

This is pretty simple, we need to:
- add a vector60/70/80....hpp in mpl/vector.
- add a map60/70....hpp in mpl/map.
- if more than 50 states, add vector60/70....hpp in fusion/vector

This is pretty simple. If that helps, I can add them into the Msm
sandbox as I already wrote them. We could also request a feature in
the MPL.

You will however not manage to increase the size of the transition
table forever. At some point will almost every compiler crash in a big
cloud of dark smoke.
To give you an idea, I usually manage:
- 60-80 transitions max with VC9. The exact point is variable on a
number of different factors which are hard to understand.
- probably less with VC8. VC8 will also quite fast need > 2GB RAM.
- 80 transitions with g++4.2. It could probably manage more but I ran
out of RAM.
- 50-60 with g++4.4. Why 4.4 is in this case less good than 4.2 is a
mystery to me.
- In Debug mode, you'll see the compiler give up faster
- Euml will also have an influence.

> Euml looks really cool, but I'm getting an ICE when using it with 36 transitions in EumlSimple.cpp (12 and 24 work fine though)

VC8 only has limited support for eUML for 3 reasons:
- less than perfect metaprogramming capabilities
- bad support for SFINAE
- VC problems with decltype/typeof

So yes, I would advise eUML for VC8 for only small state machines and
without using complicated functors as actions/guards.
VC9 would work much better, VC10 better than VC9 too (so Microsoft
seems to be working on it).

>One of my favourite features of boost::statechart is state local storage.  It looks like this would have to be done manually in msm?

Yes, this is not supported yet. However, Msm has always been developed
very user-oriented and what users ask, they usually get it. Msm has
from the beginning greatly gained from clever people suggesting new
features and I will not stop the development after the review,
whatever the outcome is. If you'd like a feature, I'd be happy to
discuss a solution with you and implement it in the next version, thus
making Msm more useful.

> The library is looking really powerful and expressive (not to mention fast!) for small state machines.

Thanks. This is the reason for the compile-times ;-)

Christophe