What's the best(when performance matters) way to implement a state machine in C#?

Question

I came up with the following options:

Using the goto statement:

Start:
    goto Data
Data:
    goto Finish
Finish:
    ;

using the switch statement:

switch(m_state) {
    case State.Start:
        m_state = State.Data;
        break;
    case State.Data:            
        m_state = State.Finish;
        break;
    case State.Finish:
        break;
}

using goto and switch together:

switch(m_state) {
    case State.Start:
        goto case State.Data2;
    case State.Data1:
        goto case State.Finish;
    case State.Data2:
        m_state = State.Data1;
        //call to a function outside the state machine
        //that could possibly change the state
        break;
    case State.Finish:
        break;
}

I prefer the first option using the goto statement, because it is faster and less verbose. But i'm not sure if it's the best option. Performance wise maybe, but when it comes to readability i don't know. That's why i ask this question. Which option do you prefer and why?

Answer 1

The advantage with the switch over the goto is that you have the state in a variable, not just in the instruction pointer.

With the goto method the state machine has to be the main loop that controls everything else, because you can't step out of it because you would lose the state.

With the switch method the state machine is isolated, and you can go anywhere you want to handle events from the outside. When you return to the state machine, it just continues where yuu left off. You can even have more than one state machine running side by side, something that is not possible with the goto version.

I'm not sure where you are going with the third alternative, it looks just like the first alternative with a useless switch around it.

Answer 2

I prefer mutually calling/recursive functions. To adapt your example:

returnvalue Start() {
    return Data();
}

returnvalue Data() {
    return Finish();
}

returnvalue Finish() {
    …
}

Theoretically, this can be completely inlined so that the compiler output is equivalent to your goto solution (hence, same speed). Realistically, the C# compiler /JITter probably won’t do it. But since the solution is vastly more readable (well, IMHO), I would only replace it with the goto solution after a very careful benchmark proving that it is indeed inferior in terms of speed, or that stack overflows occur (not in this simple solution but larger automata run into this problem).

Even then, I would definitely stick to the goto case solution. Why? Because then your whole messy goto pasta is well-encased inside a block structure (the switch block) and your spaghetti won’t mangle the rest of the code, preventing Bolognese.

In conclusion: the functional variant is clear but in general prone to problems. The goto solution is messy. Only goto case offers a halfway clean, efficient solution. If performance is indeed paramount (and the automaton is the bottle neck), go for the structured goto case variant.

Answer 3

There is a 4th option.

Use an iterator to implement a statemachine. Here is a nice short article showing you how

It has some disadvantages though. Manipulating the state from outside of the iterator is not possible.

I'm also not sure if it is very quick. But you can always do a test.

Answer 4

If you ever want to break your state machine transition logic into separate functions, you can only do it using switch statements.

switch(m_state) {
        case State.Start:
                m_state = State.Data;
                break;
        case State.Data:                        
                m_state = ComputeNextState();
                break;
        case State.Finish:
                break;
} 

It is also more readable, and the overhead of the switch statement (versus Goto) will only make a performance difference in rare circumstances.

EDIT:

You can use "goto case" to make small performance improvement:

switch(m_state) {
        case State.Start:
                m_state = State.Data; // Don't forget this line!
                goto case State.Data;
        case State.Data:                        
                m_state = ComputeNextState();
                break;
        case State.Finish:
                break;
} 

However you run the risk of forgetting to update the state variable. Which might cause subtle bugs later on (because you assumed that "m_state" was set), so I would suggest avoiding it.

Answer 5

Personally i prefer second one with goto since first one will require unnecessary loop step (for example) to go to the new state