State Machine Speed ​​- OO vs. Procedural

Question

Hello to all,
I am developing a program that will accept a number of tokens from the input and submit them to the state machine that I developed. I developed an end state test machine in an object-oriented style, with structures for the machine itself and transitions, etc. But the application that I write is the one where speed is very important.

Still using the machine, adding new states, etc. turned out to be simple and not very complicated. It is easy to understand and leave for a month, and returning to the code will not be very disorienting. However, I am not sure what the trading speed is with the current OO approach. Will there be a selection of objects, data storage, etc. Take away most of the speed that would be achieved with a set of labels and goto ?

Answer 1

I would prefer a well-structured structured, repairable, understandable (even after you left for a month, that is, pretty high-quality) code instead of a "bunch of goto labels and operators". As I said, I also launched a profiler to identify bottlenecks in speed analysis.

Answer 2

Instead of thinking about it from the point of view of OO more slowly than functional or procedural programming, think about it from the point of view of operations. Function call, branching, fetching, saving, etc. All this takes some time and to get an idea of ​​the performance of each solution that you need to calculate how many of them you will need to make.

The best way to do this is to use your OO test solution and see if it is enough enough. If not, profile it, find out which branches or stores you value the most, and see if you can avoid or optimize them. Redesign the solution slowly until it reaches your goals. In some cases, you may need to adopt a more functional or procedural style.

Finally, if you create a single function consisting of hundreds of stack variables, and you did it wrong. The code should always be readable and maintainable.

Additional thought: can you spend another $ 5,000 on the best equipment to avoid optimizing the development costs of $ 50,000?

Answer 3

Simply put, a processor runs faster when looking for tables when looking for tables than in branches. What you call the OO style will be faster if the table is acceptable and small enough to fit in the cache. (I would not say that any paradigm is associated with any implementation.)

To be very moderately more technical: the processor has 32-64 K L1 cache and from several to several tens of megabytes L2-L3. Branches in the cache are no more than a few kilobytes.

Answer 4

How often does the state of the machine change? If it remains constant for some time, then I translate it into a hard-coded procedure in any language that I prefer.

Where does the transition diagram of a finite state machine come from? Does this come from regex? You know that you can translate this directly into structured code without first creating an arc set. In fact, the easiest way to write this code is to get started.

Then I either just make this part of the application, or I dynamically compile and link it to the dll and load dynamically. The latter takes only a couple of seconds.

The final destination machines are so simple that they generally need to be run for a small fraction of the time required to load the I / O buffer. They should not do unnecessary memory allocation, building a data structure, any of these OO hoo-haw.

Remember that the final state machine, represented as a set of states and arc tuples, is a theoretical model. It exists, like Turing machines, to prove theorems about this. Like a Turing machine, this is not necessarily a good technique for implementing code.

---

Just to show you what I mean, consider a regular expression for decimal integers:

 dd* 

where 'd' means a number. As the final machine (tuples), this will be:

 A d -> B B d -> B 

as a code it will be:

 char c = getc(); if (DIGIT(c)){ c = getc(); while(DIGIT(c)){ c = getc(); } } 

See the similarity of this code to regex? Do not think c = getc() as "get the next character c". Think of it as "accept the current character c." Hopefully you will see that the code cannot be much faster than this.

If you really start with an arc set, you can generate this:

 c = getc(); A: if (DIGIT(c)){c = getc(); goto B;} goto END; B: if (DIGIT(c)){c = getc(); goto B;} goto END; END: 

which is spaghetti code, but no more than an arc set, and it will be as fast as structured code. (Actually, this is more or less what the compiler converts your structured code into.)