Article - Example state machine code for microcontrollers

[tggzzz]

IMHO that very much depends on how the statemachine is implemented. If you use a 2 dimensional array with function pointers (1 dimension is the state and the other the event) then I very much doubt you'll be able to make it run faster in Java.

I have no idea how the FSM was implemented in C.

In any case the system, which is what is important, was slower in C and faster in Java.

[Mechatrommer]

It would perhaps be easier and more maintainable code if you would put the statemachine in a lookup table...

there usually 2 big branch of school of thought of code/algorithm discussed... one is cpu intensive, one is memory intensive. yours is the later. each one have their own place in particular system.

In any case the system, which is what is important, was slower in C and faster in Java.

dont use the system then!

I have no idea how the FSM was implemented in C.

how you came to the conclusion if you dont know what you are dealing with? its like a blind faith in religion.

[tggzzz]

It would perhaps be easier and more maintainable code if you would put the statemachine in a lookup table...

there usually 2 big branch of school of thought of code/algorithm discussed... one is cpu intensive, one is memory intensive. yours is the later. each one have their own place in particular system.

You have missed a very important consideration: which is more easy to get correct in the first place and then more easy to keep correct during maintenance/enhancement. After all, if I don't have to get the correct operation, then I can make it arbitrarily fast or arbitrarily small.

In any case the system, which is what is important, was slower in C and faster in Java.

dont use the system then!

Now you're being silly. Clearly I didn't use the system; the company did. My fast Java system replaced the slow C system.

I have no idea how the FSM was implemented in C.

how you came to the conclusion if you dont know what you are dealing with? its like a blind faith in religion.

You're being silly again. I didn't need to know how the FSM was implemented in order to measure the system's speed nor to reimplement the system's function.

[tggzzz]

Don't be silly.
Better/worse can only be defined relative to requirements and constraints. Hence differing requirements and constraints will lead to different optimal technology.
I have myself implemented a telecom FSM in Java (implementing part of the ETSI Parlay standard), and it ran significantly faster than the equivalent system in C/C++. "Significantly" means that the engineers responsible for the earlier system were amazed, and an external company was so impressed that they unexpectedly purchased the code.

simply taking this sample case doesnt necessarily means one language is better than the other. they are just tools. the result will be good in the hand of a person who knows how to use the tool well.... "engineer" title alone also doesnt necessarily means he is a good guy. do you know him? he probably a bad c programmer and you are a better java programmer. as you said dont be silly, its a relative or differing requirements or constraints. re-quoting your statement...

C/C++ people (especially C/C++ gurus) tend not to understand what has been achieved in other domains. One result is that C++ is an unholy mess whereas Java isn't

this is not general or well accepted conclusion, it is more of your own personal opinion from your personal experience. remember some people are on the other side. well, my personal opinion is somewhat sounded like...

java people (especially java gurus) tend not to understand what has been achieved in other domains. One result is that java is an unholy mess whereas C/C++ isn't

and this is not based merely on my personal opinion alone, its shown everywhere when people posted code questions or examples in the net.. like our mr friend earlier with google search link with general keyword "simple state machine implementation" do you see any java implementation in the top list result? no need speak of, the truth will out, i?

btw, going c/c++ vs <insert any language here> pissing contest is not a worthy thing to do... lets concentrate on algorithm shall we?

I'm not going to respond to that since you have deliberately removed the context in which I made my statements. Arguing points taken out of context is often called a "strawman argument", and is regarded as suboptimal.

If anybody else is interested, which I doubt, they can go back and verify that your points become more-or-less irrelevant when you see the context in which I made my statements.

[donotdespisethesnake]

IMHO that very much depends on how the statemachine is implemented. If you use a 2 dimensional array with function pointers (1 dimension is the state and the other the event) then I very much doubt you'll be able to make it run faster in Java.

I have no idea how the FSM was implemented in C.

In any case the system, which is what is important, was slower in C and faster in Java.

Even if true, that statement is essentially meaningless, as comparing apples to wing nuts. While Java is typically 5x slower than C/C++, a different algorithm could be 10x or more slower than another. And then there is also all those factors like caching, memory use, API calls, parallelization which skew results.

So yeah, a really slow algorithm in C will be slower than a fast algorithm in Java. It's said "a bad programmer can write bad code in any language".

The only meaningful comparison is to compare the same algorithm implemented in different languages.

[TerminalJack505]

Regarding the look-up table/switch statement discussion...

I'm not a big fan of switch statements in general so I think the look-up table implementation is more elegant. 

That being said, the switch statement implementation will almost always compile to smaller code.  (If you don't believe that this is the case then a simple mental exercise should convince you that it is--or better yet, write some code.  A look-up table, by the way, will typically be faster.)  Code size is something a person is usually mindful of in the domain of MCUs. 

Jakeypoo's article was an introduction to state machines--seemingly aimed at Arduino users.  I think he made the right decision to use the switch statement implementation.  He likely would have had to do a lot of sidetracking if he had used the look-up table method.  He likely would have been teaching two new concepts.  Why muddy the waters?

Nice article, jakeypoo.

[jakeypoo]

Thanks. Yeah, the write up is far more basic than the other discussions in this thread.

As I said before, look-up tables of function pointers are great in certain applications, especially if you're reusing functions often. I personally don't think it's as elegant if you have to make a separate function for each state-event combo. But that's more opinion than best practice.

I've been wanting to follow this up with comparing a few different methods in code-size and speed, but it's always going to be application specific and it wouldn't be accurate to generalize.

[tggzzz]

IMHO that very much depends on how the statemachine is implemented. If you use a 2 dimensional array with function pointers (1 dimension is the state and the other the event) then I very much doubt you'll be able to make it run faster in Java.

I have no idea how the FSM was implemented in C.

In any case the system, which is what is important, was slower in C and faster in Java.

Even if true, that statement is essentially meaningless, as comparing apples to wing nuts. While Java is typically 5x slower than C/C++, a different algorithm could be 10x or more slower than another. And then there is also all those factors like caching, memory use, API calls, parallelization which skew results.

The statement that "Java is typically 5x slower than C/C++" is meaningless - and false in many people's experience. Consider the "high frequency trading" fraternity that are excessively sensitive to speed. Examples of "excessively sensitive" are one company spending $600m on a trans-Atlantic cable for their exclusive use, or another replacing Chicago-New York optical fibres with multi-hop point-to-point microwave links because the speed of light is slower in glass than in air. That fraternity is prepared to spend whatever is necessary (i.e. billions) to shave the odd  millisecond off each message's latency - and their new systems are developed in Java, not C/C++ for very good reasons. They may be reprehensible, but they are very intelligent and very clued-up.

The other factors (caching, parallelisation etc) are important, and they are one reason Java systems (not naive benchmarks) are faster. Java optimises itself at runtime to fit the code/data execution pattern on the specific processor in each machine. C/C++ cannot do that and has to produce pessimal code because the compiler cannot be omniscient. If you don't understand that, talk to any optimisation expert.

So yeah, a really slow algorithm in C will be slower than a fast algorithm in Java. It's said "a bad programmer can write bad code in any language".

The only meaningful comparison is to compare the same algorithm implemented in different languages.

No, it isn't meaningless.

If people can produce something 90% as "good" in Java in 10% of the time, then Java wins in most cases. The 10% of the time arises because of the wide range of high-quality Java libraries, plus the attributes of the language and run-time environment that enable more appropriate algorithms to be employed predictably and sooner.

[elgonzo]

That being said, the switch statement implementation will almost always compile to smaller code.  (If you don't believe that this is the case then a simple mental exercise should convince you that it is--or better yet, write some code.  A look-up table, by the way, will typically be faster.) 

Not really, at least not in the generalized way you argued. Generally speaking, for a small lookup table, the memory footprint will be rather equivalent to using switch statements. As soon as you have to create a lookup table with more entries, the memory footprint for an equivalent implementation with switch blocks will grow larger.

The reason is simple: Adding a new state and the necessary new state transitions to a switch-based implementation does not only add the data for the new state+transitions, but it also adds new code. Whereas, in a lookup-based implementation, only the data for the new state+transitions will be added, but no additional code.

Now, the question would be at which point (number of states+transistions) the switch-based solution becomes significantly worse than a lookup-based implementation. That is not easy to answer, as it will depend on a number of factors (the CPU's instruction set, memory barriers, performance requirements)...

Perhaps you were thinking about a particular implementation of a lookup table? If you think about a look-up table being implemented as a simple array whose elements represent state transitions (the current state information and the event are used as index into this array), then even for a rather few states the switch-based implementation will be larger. Compare memory footprint for the number of required switch-blocks vs. code to calculate array index from current state+event and access an element in one or two arrays plus the memory footprint of the array(s) itself. I wager, that for even half a dozen states, the switch-based approach will have a larger memory footprint... (Of course, if you have to use a data structures other than arrays, then half a dozen of states will in all likelihood not yield a memory gain vs. switch statements.)

Jakeypoo's article was an introduction to state machines--seemingly aimed at Arduino users.  I think he made the right decision to use the switch statement implementation.  He likely would have had to do a lot of sidetracking if he had used the look-up table method.  He likely would have been teaching two new concepts.  Why muddy the waters?

What "sidetracking", and what second new concept, are you talking about? You mean the typical Arduino programmer would already be overwhelmed when being confronted with basic data structures?

[tggzzz]

As I said before, look-up tables of function pointers are great in certain applications, especially if you're reusing functions often. I personally don't think it's as elegant if you have to make a separate function for each state-event combo.

You would only have to do that if different actions were required for each state-event combination. But that would be inherent in the specification, not an implementation artefact. If using switch-statements it would result in each switch statement having fully-enumerated cases, and the code in each case being different.

In practice, many of the state-event combos are "don't care" (i.e. a single empty function) or "should not happen" (i.e. a single function that logs the error and recovers).

[TerminalJack505]

That being said, the switch statement implementation will almost always compile to smaller code.  (If you don't believe that this is the case then a simple mental exercise should convince you that it is--or better yet, write some code.  A look-up table, by the way, will typically be faster.) 

Not really, at least not in the generalized way you argued. Generally speaking, for a small lookup table, the memory footprint will be rather equivalent to using switch statements. As soon as you have to create a lookup table with more entries, the memory footprint for an equivalent implementation with switch blocks will grow larger.

The reason is simple: Adding a new state and the necessary new state transitions to a switch-based implementation does not only add the data for the new state+transitions, but it also adds new code. Whereas, in a lookup-based implementation, only the data for the new state+transitions will be added, but no additional code.

Now, the question would be at which point (number of states+transistions) the switch-based solution becomes significantly worse than a lookup-based implementation. That is not easy to answer, as it will depend on a number of factors (the CPU's instruction set, memory barriers, performance requirements)...

Perhaps you were thinking about a particular implementation of a lookup table? If you think about a look-up table being implemented as a simple array whose elements represent state transitions (the current state information and the event are used as index into this array), then even for a rather few states the switch-based implementation will be larger. Compare memory footprint for the number of required switch-blocks vs. code to calculate array index from current state+event and access an element in one or two arrays plus the memory footprint of the array(s) itself... I wager, that for even half a dozen states, the switch-based approach will have a larger memory footprint...

Jakeypoo's article was an introduction to state machines--seemingly aimed at Arduino users.  I think he made the right decision to use the switch statement implementation.  He likely would have had to do a lot of sidetracking if he had used the look-up table method.  He likely would have been teaching two new concepts.  Why muddy the waters?

What "sidetracking", and what second new concept, are you talking about? You mean the typical Arduino programmer would already be overwhelmed when being confronted with basic data structures?

The particular case I was thinking about is when your look-up table is a table of function pointers.  If you can actually encode the necessary "information" completely in the look-up table then obviously that will produce smaller code than the equivalent switch statement.  (A rotatory encoder state machine is a good example of this.)

I think the Arduino programmer--like anyone else--will likely best be taken through a new concept through the simplest means possible.  Just like anyone else.  This is one of the keys to good teaching.

[elgonzo]

The particular case I was thinking about is when your look-up table is a table of function pointers.  If you can actually encode the necessary "information" completely in the look-up table then obviously that will produce smaller code than the equivalent switch statement.  (A rotatory encoder state machine is a good example of this.)

Ah, okay. Got you now...

I think the Arduino programmer--like anyone else--will likely best be taken through a new concept through the simplest means possible.  Just like anyone else.  This is one of the keys to good teaching.

What does that sentence even mean? How do you define "simplest means possible"? Doesn't it depend on what you want to teach? Doesn't it depend on prior knowledge the topic demands? If you have to assume your students are having difficulties in comprehending basic data structures, then you should perhaps not teach FSM to them yet, but teach how to work with basic data structures (or refer them to someone/some site where they can learn about it). Good teaching means not putting the cart before the donkey, but teach basics first and then build upon what you have taught before.

(On a side note: simple data structures such as structs and arrays/lists are so essential, you can barely program anything without knowing how to use them -- but that's just my opinion )

[elgonzo]

I've been wanting to follow this up with comparing a few different methods in code-size and speed, but it's always going to be application specific and it wouldn't be accurate to generalize.

That would be great.
What i wonder, is the Atmega328-based Arduino still the most sold model? My thinking is that the targeted readership are probably beginners which just recently bought an Arduino. Are they still buying mostly the Atmega328, or rather an Atmega32u4 or ARM-based Arduino? (which can be relevant if you want to talk about code size and performance)

[TerminalJack505]

I think the Arduino programmer--like anyone else--will likely best be taken through a new concept through the simplest means possible.  Just like anyone else.  This is one of the keys to good teaching.

What does that sentence even mean? How do you define "simplest means possible"? Doesn't it depend on what you want to teach? Doesn't it depend on prior knowledge the topic demands? If you have to assume your students are having difficulties in comprehending basic data structures, then you should perhaps not teach FSM to them yet, but teach how to work with basic data structures. Good teaching means not putting the cart before the donkey, but teach basics first and then build upon what you have taught before...

I guess I didn't make my point very clear since you are basically saying exactly what I was trying to say.  Start simple.  The look-up table implementation of state machines would, in my opinion, be best saved for a later lesson.

At any rate, neither you or I have written an article on the matter and jakeypoo has so we really don't have much of a right to say how he should have written his article.

[elgonzo]

I guess I didn't make my point very clear since you are basically saying exactly what I was trying to say.  Start simple.  The look-up table implementation of state machines would, in my opinion, be best saved for a later lesson.

I am sorry that i am so slow in understanding. Still slacking off the hangover... 

At any rate, neither you or I have written an article on the matter and jakeypoo has so we really don't have much of a right to say how he should have written his article.

Absolutely! But we can and do discussing it...

[TerminalJack505]

I guess I didn't make my point very clear since you are basically saying exactly what I was trying to say.  Start simple.  The look-up table implementation of state machines would, in my opinion, be best saved for a later lesson.

I am sorry that i am so slow in understanding. Still slacking off the hangover... 

At any rate, neither you or I have written an article on the matter and jakeypoo has so we really don't have much of a right to say how he should have written his article.

Absolutely! But we can and do discussing it...

Yep!     I just don't want jakeypoo to get discouraged.

I guess my argument is that the code-based solution (switch statement) would be simpler to understand than the data-driven solution (look-up table.)

It has been my experience that as a programmer "evolves" that the data-driven approach to problem solving actually comes at a fairly late stage.  (Almost as a eureka-type moment.)

Beginners, I think, will find the code-based solution easier to understand since it is a purely procedural solution and that is how most beginning programmers seem to think.

All just my opinion obviously!

[nctnico]

Thanks. Yeah, the write up is far more basic than the other discussions in this thread.

As I said before, look-up tables of function pointers are great in certain applications, especially if you're reusing functions often. I personally don't think it's as elegant if you have to make a separate function for each state-event combo. But that's more opinion than best practice.

Why would you need a seperate function? There is no reason a function cannot be called by multiple state/event combinations.

[ehughes]

Good article.   Don't worry about the people who need to tell you they would do it better.   Those people are would come up with some other way to do it anyway.

Compilers (at least good ones)   implement switch statements with a jump table.  It is very efficient, readable and safer than function pointers.

This is the about the only way you can do it and get safety certifiable code (I.E.  MIRSA,  Medical or Flight Safety) that is maintainable.

A couple other things I do:

Querys to the state Machine are always done through a function

uint8_t MyFSM_GetState();

transition are always done with a function (NEVER modify the variable directly)

uint8_t MyFSM_TransitionToState(uint8_t NextState);

The FSM has a Process and Init() function for The FSM

MyFSM_Init();

MyFSM_Process();


Each FSM also gets a 1mS tick variable that ticks up in the background to implement non-blocking "yeilds"

All programs need a super loop....   Even with an RTOS... Which is a glorified *set* of super loops with automated way to switch between them.

[tggzzz]

I guess my argument is that the code-based solution (switch statement) would be simpler to understand than the data-driven solution (look-up table.)

That's true on one level and false on another.

True: uses familiar language statements that you can see in a textbook.

False: more difficult to implement correctly and to ensure continuing correctness in the face of enhancements and maintenance. In the worst case I've seen, if-the-else statements were nested 10 (ten) deep! Shocking, but I was told that incremental business priorities trumped incremental technical debt.

It has been my experience that as a programmer "evolves" that the data-driven approach to problem solving actually comes at a fairly late stage.  (Almost as a eureka-type moment.)
Beginners, I think, will find the code-based solution easier to understand since it is a purely procedural solution and that is how most beginning programmers seem to think.

I wouldn't argue with that, but the "evolution" can be very rapid. IMNSHO experience all it takes is one previous exposure to the pathogen (switch statements) and being shown the vaccine (data driven programming, or appropriate uses of OOP). If it takes more, then I seriously question whether the person should be using a keyboard.

[tggzzz]

IMHO that very much depends on how the statemachine is implemented. If you use a 2 dimensional array with function pointers (1 dimension is the state and the other the event) then I very much doubt you'll be able to make it run faster in Java.

I have no idea how the FSM was implemented in C.

In any case the system, which is what is important, was slower in C and faster in Java.

Even if true, that statement is essentially meaningless, as comparing apples to wing nuts. While Java is typically 5x slower than C/C++, a different algorithm could be 10x or more slower than another. And then there is also all those factors like caching, memory use, API calls, parallelization which skew results.

The statement that "Java is typically 5x slower than C/C++" is meaningless - and false in many people's experience. Consider the "high frequency trading" fraternity that are excessively sensitive to speed. Examples of "excessively sensitive" are one company spending $600m on a trans-Atlantic cable for their exclusive use, or another replacing Chicago-New York optical fibres with multi-hop point-to-point microwave links because the speed of light is slower in glass than in air. That fraternity is prepared to spend whatever is necessary (i.e. billions) to shave the odd  millisecond off each message's latency - and their new systems are developed in Java, not C/C++ for very good reasons. They may be reprehensible, but they are very intelligent and very clued-up.

The other factors (caching, parallelisation etc) are important, and they are one reason Java systems (not naive benchmarks) are faster. Java optimises itself at runtime to fit the code/data execution pattern on the specific processor in each machine. C/C++ cannot do that and has to produce pessimal code because the compiler cannot be omniscient. If you don't understand that, talk to any optimisation expert.

So yeah, a really slow algorithm in C will be slower than a fast algorithm in Java. It's said "a bad programmer can write bad code in any language".

The only meaningful comparison is to compare the same algorithm implemented in different languages.

No, it isn't meaningless.

If people can produce something 90% as "good" in Java in 10% of the time, then Java wins in most cases. The 10% of the time arises because of the wide range of high-quality Java libraries, plus the attributes of the language and run-time environment that enable more appropriate algorithms to be employed predictably and sooner.

According to http://www.wsj.com/articles/SB10001424052702304065704577426500918047624 the trans-Atlantic cable will reduce latency from 65ms to 60ms, and "only" costs $300m.
According to http://www.wired.com/2012/08/ff_wallstreet_trading/all/ the Chicago - New York microwave link reduces latency from 14.5ms to 9ms.

That fraternity is seriously concerned with speed/latency, which makes their decision to use Java rather than C/C++ all the more significant.

[nctnico]

I love this quote for the first article:
But perhaps not even Einstein fully appreciated the degree to which electromagnetic waves bend in the presence of money.

Perhaps they choose Java because they couldn't find the hardcore C/C++ programmers in time. BTW recently I got a very well paying job offered to implement high speed trading in FPGAs.

[SL4P]

I'll probably get flamed for this, but 90% of CS graduates I have come across / interviewed in the last decade have no idea how to analyse a requirement - then write software - but they do know how to use Java, and HTML(5)/CSS to write games and web sites.

A few have basic Linux & .NET back-end skills, but being able to tie it all together is a very rare individual.
Ability to write user documentation - other than for course marking - is also very hard to get.

[tggzzz]

BTW recently I got a very well paying job offered to implement high speed trading in FPGAs.

I've heard of such things, but I haven't seen a sufficiently good description of what was implemented and why it was beneficial. Hence I didn't mention it.

Could you shed any light on the broad areas which were implemented in FPGAs, without revealing any trade secrets of course?

[tggzzz]

I'll probably get flamed for this, but 90% of CS graduates I have come across / interviewed in the last decade have no idea how to analyse a requirement - then write software - but they do know how to use Java, and HTML(5)/CSS to write games and web sites.

A few have basic Linux & .NET back-end skills, but being able to tie it all together is a very rare individual.
Ability to write user documentation - other than for course marking - is also very hard to get.

Unfortunately that doesn't surprise me, and I expect it will get worse rather than better.

When I was starting out it was perfectly possible to understand and do everything, from constructing an Altair8080-class computer, creating your own instruction set using bit-slice computers, through writing your own RTOS and on to application software. No longer, due to the complexity of all the individual pieces. Very interestingly, the Arduino-class computers are an excellent way of re-approaching that level of simplicity, and hence enabling people to learn in easy stages, as we did. The RPi is less successful at that, but more successful at a different level.

When my father was young, something similar could be said about cars, but by the time I was "at that age", cars were sufficiently complex that they often needed garage mechanics. Nowadays the worst care mechanics can't be trusted to put oil in the right orifice!

[nctnico]

BTW recently I got a very well paying job offered to implement high speed trading in FPGAs.

I've heard of such things, but I haven't seen a sufficiently good description of what was implemented and why it was beneficial. Hence I didn't mention it.

Could you shed any light on the broad areas which were implemented in FPGAs, without revealing any trade secrets of course?

I turned down the job offer before going for an interview because I wanted to work part-time (due to other obligations) and they insisted on getting someone full-time.

A very long time ago I worked at a stock broker & market maker where they started to use high speed trading. There are several ways to make money with shares: gamble on a share going up, gamble on a share going down (going short) and options which basically do the same but are more complicated. The trickiest bit are the options. Based on the shares you have it may be benificial to buy or sell certain options (http://en.wikipedia.org/wiki/Straddle). This takes a lot of calculations and time is of the essence.
Another application for high speed trading is market making: selling options and shares between stock exchanges if one share is listen on multiple exchanged. This takes a lot of comparing prices and acting fast.

I don't know why they choose to use FPGA. It sounds cumbersome to me for mass calculations. My first question would have been why they didn't use CUDA.

The whole speed trading thing is a true rat-race and it is a lucrative business for the companies making those systems. When the traders of the firm I worked for started to use their high speed trading systems they could easely rake in 8k per day each but that soon went down because a lot of other people started to use the same system. So for a trading company being ahead of the competition is equal to not going bankcrupt.