Object-Oriented State Machines

published: Thu, 31-Mar-2005   |   updated: Sun, 23-Jul-2006

In the March issue of The Delphi Magazine, I discussed refactoring state machines that had been implemented as giant case (or switch) statements into an object-oriented model. Essentially, the class model I used was the State pattern as described by the Gang of Four in Design Patterns.

As an example to illustrate the technique I took some code I'd written years ago to recognize a floating-point number in a string (to convert a string to a double, if you will). The code was originally written as a simple introduction on automata (DFAa and NFAs). (The code for the original case statement verison and the new object-oriented version can be downloaded here.)

The reasons I gave for applying this technique were (1) ease of writing the code (the class model mimics the state machine diagram), (2) ease of understanding the code when reading it for the first time (ditto), (3) ease of maintenance (adding states is easy, modifying existing ones equally so -- for example, you don't have to worry about having to change local variables and thereby afffecting other states) (4) ease of testing (you can test individual states one at a time). Notice that all these benefits are to do with writing and reading the code and ensuring that it is works correctly.

Anyway one of my readers sent me this email (slightly edited), making a valid point:

I've read your interesting article in TDM issue #115. I always read your articles with interest.

Having an OO state machine is conceptually interesting, but the performance is not there. Taking your own code, TFloatRecognizerUsingCase.Execute is 18 times faster than TFloatRecognizer.Execute (compiled with D7), without even mentioning the issues with increased memory usage and fragmentation that could occur.

This was my reply:

I think you're taking the example program as being the canonical example for the technique and then damning the idea because of the example.

In writing about a particular technique, I think it makes sense to provide an example that is simple in order that the reader can concentrate on the exposition of the technique without drowning in details about what the example is doing. A lot of times the example is so simple that it certainly doesn't make sense to use the technique on the example.

In essence, for this article I was writing to an audience of one person, the developer who wrote a ten page switch statement that I had to try and understand so that I could make recommendations about modifying the functionality. It certainly didn't seem to bother him that the indentation crept over beyond the halfway point on my screen. It certainly didn't bother him that there were 23 local variables, some of which were used in some case blocks but not in others, but it was hard to ascertain that they were correctly initialized or didn't have old invalid values. Etc, etc.

On to your particular points. Performance issues only make sense in the context of the application. The performance of a floating point recognizer doesn't matter in the least if it's just used to validate user input at the time for the input: the user won't notice. If it's used for converting a billion strings in an import routine, then yes, I'd be looking at a faster conversion routine. But even so, I'd be using a profiler to make sure that I'm optimizing what I should be optimizing.

Memory fragmentation issues. As it happens, in my example there is no state associated with each state object (apart from one, the ErrorState, but only one of those will ever be created anyway). Hence state objects could be reused without any problems. Hence all we need to do is create one instance of each type and add a factory routine to dispense them.

Now, all this is totally ancillary to the main technique. In effect it's optimizing memory performance without profiling to see if there is a problem in this area. Yes, I suppose I should have mentioned this possibility in the article, but I would say this: how do you know that there are heap fragmentation problems? From my understanding all the state objects created (apart from the ErrorState object) are exactly the same size. I would guess that the memory for these objects would be automatically reused so no fragmentation would occur.

Also, it could be that my readers take this technique and use it in Java or .NET or Ruby (I'm guessing that some of my readers use different languages and not just Delphi). For these we have a garbage- collected environment with no heap fragmentation issues and where small short-lived objects are very cheap.

Also, to be honest, you could take out the words "OO state machine" from your message and replace it with "OO class model" and still have a valid point: "Having an OO class model is conceptually interesting, but the performance is not there. [...] without even mentioning the issues with increased memory usage and fragmentation that could occur." At some point, you have to recognize that OOP is more about being able to write correct programs more easily and quickly, and not necessarily about raw speed or optimal use of the heap (although Delphi's heap has been optimized to a certain extent for small objects).