Remove filter Showing only articles with tag "C++"

Implementing state-machines: An evaluation

Posted: Sunday, 2015-10-18 10:15 | Tags: Programming, C++

In the previous article I raised the question on whether -- from a performance standpoint -- one should implement state machines using switch-statements or function pointers.

We saw that switch-statements are compiled to a number of jump/compare instructions that grow at least logarithmically with the number of case-labels. I had to close with the observation that a too contrived example however leads to our compiler actually analyzing our state machine good enough to be able to rewrite our code into unrolled instructions and loops.

In this post I want to discuss a slightly less contrived example that is a (stupid and useless) "parser" for XML data. We will observe that even when the state logic is more complex and transitions depend on unforeseeable input data, the compiler can do smart transformations with switch-statements.


Implementing state-machines: switch() vs. method pointers

Posted: Saturday, 2015-10-17 15:51 | Tags: Programming, C++

Finite-state machines are useful for many purposes: Say we have a long running computation that goes back and forth between different phases and is executed chunk-by-chunk in a main loop that does other things in between (e.g. updating some user interface). Yes, you scream "threads", but there are some situations where those are just not necessary or wanted for whatever reason.

Another common use is building a lexer/parser that reads some kind of input and interprets the incoming characters differently depending on "in what state we are" e.g. whether we just read a '' or not might influence how we interpret the current character.

Most state-machine code I've seen so far is built with giant switch()-blocks and recently I've come to wonder whether this is always the way to go.