EEVblog Electronics Community Forum
Electronics => Microcontrollers => Topic started by: jakeypoo on February 20, 2015, 04:57:45 pm
-
Howdy,
I wanted to share a write-up I put together on a piece of code I use regularly when a microcontroller application calls for a state machine. It goes over some example state machine code and explains some basics about how state machines work. Take a look if you're interested: http://www.heptapod.com/lib/statemachines/ (http://www.heptapod.com/lib/statemachines/)
The example uses an atmega328, but the concepts could be applied to any micro that uses C. It might be a little basic if you already know this stuff, but I hope it helps any beginners or intermediate folks out there trying to get away from writing the giant while(1) loops in their event-driven microcontroller code.
-
now you have giant switch. tell me mr programmer, how in the world you can get rid of the giant loop? its the essence of making a program continually running without reaching the exit() code...
-
It would perhaps be easier and more maintainable code if you would put the statemachine in a lookup table where you query for current state and event (like input) and get the new state. Every state has an associated "enter state" action/function pointer (and optionally an "leave state" action, if necessary).
To do state transitions, you will have just a generic routine that based on the current state does something like the following:
1. Wait for event.
2. Lookup the new state for {current state, event}.
3. Execute "Enter state" action of new state.
4. Goto 1.
What is needed for that approach are two data structures. One for the lookup:
typedef struct
{
currentState;
event;
newState;
} StateMachine;
and one that associates the states with the "Enter state" actions:
typedef struct
{
state;
enterStateActionPointer;
} StateAction;
Alternatively, if you have lots of states and or lots of events, the StateMachine structure from above could be split into something like this:
typedef struct
{
event;
newState;
} StateTransition;
typedef struct
{
state;
StateTransition[]; // array or lookup/hash table
} StateMachine;
(Note, the pseudo-code above is just one of many ways how you could create data structures for a state machine)
Right now, you have kind of spaghetti code that mixes management of the state machine and the actions that are associated with certain states. Having the code it like you do is not really a problem if your source code is small -- but then again, a simple nested switch block is as short and more readable. As soon as the number of possible states becomes larger, your approach leads to code that makes it difficult to read and maintain; it will also make it difficult to see the whole state machine that is embedded within the code...
-
@Mechatrommer - I believe switch statements are better for compiler optimization, so a large switch statement is less evil than a large group of if-else statements as far as the optimizer sees it.
@elgonzo - Lookup table implementations are a good approach, but I think more appropriate where every event should trigger a new state. I found in microcontrollers you more often need an event handler that can change its behaviour when you change modes or something like that. It stays pretty easy to manage if you keep your code encapsulated. Maybe it's not the cleanest approach, but it has been pretty reliable and easy to read/maintain for me in the past.
-
Switch statements are either better or worse for the compiler depending on the complexity of the code, the compiler, and the optimisation switches used.
Switch statements are OK for trivial state machines, but become a nightmare for complex state machines - particularly if they have to be maintained over a period by multiple programmers.
There are many different ways of encoding a state machine in a low/medium level language such as C. Each way has associated advantages and disadvantages - there is no "one best way".
Many people represent their state machines at a "higher level", and then use a tool to mechanically translate it into whatever language they are using.
Your approach is not sufficient when considering debugging and system integration. For those it is highly beneficial to explicitly abstract the concept of "state" and "event" into two data structures, and then log each event+state+time as it occurs. That will enable you to demonstrate that the problem is in other parts of your system, thus saving you time and money (and hair). Done properly, none of the debugging/logging code changes when the FSM changes.
-
There are absolutely other ways to code a state machine in C, I just wanted to share my approach. If you're concerned about automated testing/debugging then this is probably a little more basic than what you need.
-
There are absolutely other ways to code a state machine in C, I just wanted to share my approach. If you're concerned about automated testing/debugging then this is probably a little more basic than what you need.
The approaches are beneficial for all testing and debugging whether automated or manual - and more importantly for spotting obscure intermittent faults and then isolating the faulty code.
All non-trivial FSMs grow like Topsy until they become intractable - i.e. you can't accurately predict how they will operate. I've even seen an FSM similar to yours that had grown over the years until the turnaround time (customer request to deployed feature) was typically six months. Completely ridiculous of course, and it sank the product.
-
All non-trivial FSMs grow like Topsy until they become intractable - i.e. you can't accurately predict how they will operate. I've even seen an FSM similar to yours that had grown over the years until the turnaround time (customer request to deployed feature) was typically six months. Completely ridiculous of course, and it sank the product.
Yeah, I don't doubt it. The benefit of using something like a state machine should be that you fit your system to a construct you can implement quickly/reliably. And there's an added benefit of engineers being able to understand logic flow in a FSM better than other programming construct. But of course most of us aren't programmers and we can kludge even the best of code into a mess.
Are there any articles or examples of low-level FSM implementation you would recommend? I didn't find too much in the past specific to microcontrollers, made me want to share.
-
Are there any articles or examples of low-level FSM implementation you would recommend? I didn't find too much in the past specific to microcontrollers, made me want to share.
Have you tried searching...? (https://www.google.de/search?q=simple+state+machine+implementation)
There is nothing specific about implementing state machines in MCUs.
There might be application-specific considerations as well as considerations regarding memory footprint of code+data structures, but those are general considerations that apply to any kind code, and are not specific to state machine implementations. (If this is your interest, you should look for articles that talk generally about data structures and their memory footprints + performance characteristics with regard to the C language and your target MCU architecture...)
-
All non-trivial FSMs grow like Topsy until they become intractable - i.e. you can't accurately predict how they will operate. I've even seen an FSM similar to yours that had grown over the years until the turnaround time (customer request to deployed feature) was typically six months. Completely ridiculous of course, and it sank the product.
Yeah, I don't doubt it. The benefit of using something like a state machine should be that you fit your system to a construct you can implement quickly/reliably. And there's an added benefit of engineers being able to understand logic flow in a FSM better than other programming construct. But of course most of us aren't programmers and we can kludge even the best of code into a mess.
Nominally they were programmers. Personally I wouldn't have let them anywhere near a keyboard.
Are there any articles or examples of low-level FSM implementation you would recommend? I didn't find too much in the past specific to microcontrollers, made me want to share.
The trouble is I learned/reinvented various techniques before URLs even existed.
Have a look for Harel StateCharts. IMNSHO, while complete, they are a little overcomplicated.
An old low-level C technique is to have a 2D array of function pointers. Dimension 1 is the current state S (encoded as an integer), dimension 2 is the incoming event E (also encoded as an integer). Each pointer refers to the function to be executed when event E occurs in state S; the function takes whatever actions are necessary and specifies the next state (variant: the next state is encoded in a second parallel 2D array of integers).
Logging consists of recording <time,E,S> tuples. The set of states and events is fully explicitly enumerated, and it is unambiguous what happens when event E happens in state S1 or S2 or...
If you need a new action, then you don't have to dismember entangled switch statements, you just add a new function and point to it.
If an event "should not occur" then that can either be encoded as an empty function or, more usefully as a WTF-function.
Note that the execution time is constant and trivial - an array lookup and indirect jump to a function. Unless the state-event space is very sparse, which is unlikely for real-time systems, the 2D array is also space efficient.
If hierarchical FSMs better represent your problem, then encode encode each event as a class E, each state as a class C (where the class hierarchy matches the state hierarchy), and have a virtual function in classes C for each event E. Then provide methods in the relevant C for each relevant E. "Should not happen" E will trickle up to the base/root class.
Have a look at how various "state machine compilers" implement the FSMs in different languages. The better ones will target different languages and have alternative target implementations depending on the constraints.
One (old) compiler was Bob Martin's "State Map Compiler", see http://smc.sourceforge.net/SmcFaq.htm#RipOff (http://smc.sourceforge.net/SmcFaq.htm#RipOff) but there are many others.
-
Are there any articles or examples of low-level FSM implementation you would recommend? I didn't find too much in the past specific to microcontrollers, made me want to share.
Have you tried searching...? (https://www.google.de/search?q=simple+state+machine+implementation)
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 isn't the place for that debate, but interested parties can search for Gosling's 1996 Java whitepaper, and for the C++ FQA (not FAQ!).
-
@Mechatrommer - I believe switch statements are better for compiler optimization, so a large switch statement is less evil than a large group of if-else statements as far as the optimizer sees it.
you were talking about getting rid of "giant loop", you should've said getting rid of "giant if". but well, replacing giant if with giant switch is not entertaining either. so the excuse is moot. otoh an "ideal programmer" doesnt deal with a nonsense such as "compiler optimization" (oh what a troll ;D) find another good reason then i'm with you my friend ;)
One result is that C++ is an unholy mess whereas Java isn't.
am i not dreaming? what a joke of the century! :-DD
-
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 isn't the place for that debate, but interested parties can search for Gosling's 1996 Java whitepaper, and for the C++ FQA (not FAQ!).
Not sure in which direction you are going... I agree with C++ being an abomination, but what has that to do with looking at and understanding simple state machine implementations? How does the Java whitepaper fit into this topic, or was this in reference to C++ being sauerkraut?
-
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 isn't the place for that debate, but interested parties can search for Gosling's 1996 Java whitepaper, and for the C++ FQA (not FAQ!).
Not sure in which direction you are going... I agree with C++ being an abomination, but what has that to do with looking at and understanding simple state machine implementations? How does the Java whitepaper fit into this topic, or was this in reference to C++ being sauerkraut?
It was solely a response to your question about searching - or lack thereof. The C++ mob have long demonstrated a lack of understanding of what has been shown to work/fail outside the C/C++ sphere.
Neither it nor the Java whitepaper nor the C++ FQA has direct relevance to FSMs.
-
It was solely a response to your question about searching - or lack thereof. The C++ mob have long demonstrated a lack of understanding of what has been shown to work/fail outside the C/C++ sphere.
Did you notice that my question was a link you can click and that the search terms within this links are about state machines / implementations, not about C++? What are you talking about?
-
It was solely a response to your question about searching - or lack thereof. The C++ mob have long demonstrated a lack of understanding of what has been shown to work/fail outside the C/C++ sphere.
Did you notice that my question was a link you can click and that the search terms within this links are about state machines / implementations, not about C++? What are you talking about?
Oh good grief. Don't over-interpret what has been written. And please don't snip the context of the conversation - it makes it difficult for you (and others) to follow what was written.
To be extraordinarily explicit, I was amplifying your inference (that while the OP would benefit from having done some searching) by noting that many C/C++ people (probably including the OP) were too narrowly focussed on the C/C++ realm - to the extent that they are too unaware of things outside that narrow realm.
-
An external tool may be benificial but it does add complexity to maintaining the source code because there is a dependancy on an extra tool. People maintaining the software will need to learn the extra tool as well.
Perhaps a better way would be to have proper documentation and/or breaking a big statemachine in several small ones. That way someone maintaining the software can keep an eye on the big picture.
-
Java, MCU... Good one :-D
-
An external tool may be benificial but it does add complexity to maintaining the source code because there is a dependancy on an extra tool. People maintaining the software will need to learn the extra tool as well.
Very, very true. Plus there will be very little automated tool support for exploring/reasoning/checking each FSM design, and it will be difficult to recruit someone to a role that won't help them get their next job.
Of course, all that applies to the "domain specific languages" beloved of computer science wannabes that feel unfulfilled unless they are writing compilers. IMNSHO a good library is usually preferable to a DSL.
Perhaps a better way would be to have proper documentation and/or breaking a big statemachine in several small ones. That way someone maintaining the software can keep an eye on the big picture.
You can make the argument that the FSM is that documentation.
As for breaking a large FSM into smaller ones, that goes without saying, just as with large functions etc. But sometimes large FSMs are natural and/or are part of the specification being implemented.
-
Java, MCU... Good one :-D
There's Java on a wide range of extremely small MCUs... SIMS. See http://en.wikipedia.org/wiki/Java_Card (http://en.wikipedia.org/wiki/Java_Card)
-
Java, MCU... Good one :-D
There's Java on a wide range of extremely small MCUs... SIMS. See http://en.wikipedia.org/wiki/Java_Card (http://en.wikipedia.org/wiki/Java_Card)
It's used to sandbox executed third party code which is typically not a requirement in most MCU applications that allow leaner solutions.
-
Java, MCU... Good one :-D
There's Java on a wide range of extremely small MCUs... SIMS. See http://en.wikipedia.org/wiki/Java_Card (http://en.wikipedia.org/wiki/Java_Card)
and maybe you can demonstrate (open source maybe?) how FSM is implemented better in java? or in real life application performing better than c/c++?
-
Java, MCU... Good one :-D
There's Java on a wide range of extremely small MCUs... SIMS. See http://en.wikipedia.org/wiki/Java_Card (http://en.wikipedia.org/wiki/Java_Card)
and maybe you can demonstrate (open source maybe?) how FSM is implemented better in java? or in real life application performing better than c/c++?
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.
A valid and increasingly typical use-case for high-performance soft realtime systems: if all your software is written in Java and/or none of your staff know C/C++, then it would be highly suboptimal and non-performant to use C/C++ for and FSM.
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.
Don't forget that C compilers have to be so pessimal that when you implement HotSpot-style optimisation and run the code in an emulated processor, it still runs faster than the optimised C code on the same un-emulated processor. Search for HP's Dynamo project to see how and why (you can follow links from http://lambda-the-ultimate.org/node/768 (http://lambda-the-ultimate.org/node/768) )
-
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.
-
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?
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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? :-//
-
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).
-
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.
-
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 :) )
-
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.
:clap: 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)
-
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.
-
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...
-
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!
-
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.
-
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.
-
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.
-
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 (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/ (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.
-
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.
-
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.
-
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'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!
-
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 (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.
-
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();
...
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.
Thanks, all good points.
Sometimes the super loop can be less -- super. Sticking all of the logic flow in the main loop of a program is one of these things that those of us who were not formally taught programming tend to do for too long.
-
Actually it is better to stick everything in one loop. Having several concurrent threads is a major pain in the ass to get right. The phases I see with programmers is:
- put everything in one loop
- use parallel threads
- put everything in one loop but get it right this time
-
Actually it is better to stick everything in one loop. Having several concurrent threads is a major pain in the ass to get right. The phases I see with programmers is:
- put everything in one loop
- use parallel threads
- put everything in one loop but get it right this time
It depends on the application domain's requirements. Sometimes it is necessary and beneficial to have multiple threads, but they have to be used judiciously, preferably following simple design patterns. Fail to do that and you have an unholy mess.
Rule of thumb: if an application programmer uses "synchronised" "volatile" "wait" "notify" etc, then the design is probably a mess.
Rule of thumb: if an application programmer uses library components such as "fifo" "queue" "mailbox" and sets the capacities and the send/receive blocking/non-blocking characterisitics appropriately, then the implementation is probably sound.
The "Half-sync half-async" design pattern is a well-proven technique, see http://www.cs.wustl.edu/~schmidt/PDF/PLoP-95.pdf (http://www.cs.wustl.edu/~schmidt/PDF/PLoP-95.pdf)
Java makes multithreaded programs a damn sight easier than C++, since Java has the necessary language primitives enabling high quality concurrenty libraries and well-proven design patterns (see Doug Lea's concurrency classes, now part of the standrd library. C++ is in the "unfortunate" position that the language defines concurrency as a library issue, and the (Posix) libaries make use of behavious that isn't defined in the language standard. (That position might be better with the latest C++ standard, but who knows when implementations will be used in the real world).
-
Sometimes the super loop can be less -- super.
I certainly don't disagree! My point was more about what all that code translates not, not necessarily what the text file looks like. My main loops almost always to be Init phase followed by a very high level system state machine. Something you can generally follow with minimal scrolling, etc. There is not really behavioral code, other than that main switch for a state machine and function calls with descriptive names to understand what processes are in what state. If the machine grows bigger than a handful of "system" states then it needs to be re-thought.
I.E. something that you could start at main() and get a gross level understanding of where to go next. Something that you can easily see what processes are running in what state, etc.
Here is what I have generally observed.
1.) There are "software" people who obsess over what the text file(s) looks like for state machine encoding. These are the "Java people" of the world (not using this as a pejorative) who obsess over how a code looks more than it acts, use delegates and function pointers everywhere to make the text representation compact, etc.
2.) Then there are hardware people who have built state machines from raw gates or used a ROM as a state decoder. Anyone who does this or has written HDL look at the state machine design in C in a completely different way. Hardware is a lot less forgiving and doesn't give a shit about cute software paradigms. These people almost always use a switch as that IS the optimal way that a synthesize wants to see it in HDL. It is exactly how it would map to a hand wired ROM. Hardware can't crash, get funky, etc. as fixing silicon and cutting PCB traces is a lot more tough than fixing high level software.
Not to say there aren't people in the middle but those are the two bins that cover the 6-sigma in my observations/ I have always been more aligned with camp #2 but there are many CS people who do #1 as that is what they know. Neither is "right" or "wrong", it is just 2 different approaches.
Most of what I do has to fall into the category of safety certifiable and high reliability. That eliminatws 99% of the CS "fluff" from implementations. That stuff is nice in a classroom but useless when it comes to applications that simply cannot fail.
Not all behavior falls into textbook FSM implementations. That and if your system grows to a point where it takes 6-months to upgrade, there is something else wrong in the general approach. The problem needs to be rethought. This is not a problem with the choice of state machine implementation but the general solution to how the problem is solved.
-
Java makes multithreaded programs a damn sight easier than C++, since Java has the necessary language primitives enabling high quality concurrenty libraries and well-proven design patterns (see Doug Lea's concurrency classes, now part of the standrd library. C++ is in the "unfortunate" position that the language defines concurrency as a library issue, and the (Posix) libaries make use of behavious that isn't defined in the language standard.
what kind of nonsense is this? a java fanboy keeps bragging about "java built-in library" as a "java language specification"? can you differ "language's specification" with "language's standard library implementation?", or do you even know how a "language's standard library" is built? if you are incapable of making a code without a "library" (namespace or class or whatever higher level encapsulation) then we are sorry, get a life, there are still so much you need to learn, your "fast java" is not so entertaining.
-
Java makes multithreaded programs a damn sight easier than C++, since Java has the necessary language primitives enabling high quality concurrenty libraries and well-proven design patterns (see Doug Lea's concurrency classes, now part of the standrd library. C++ is in the "unfortunate" position that the language defines concurrency as a library issue, and the (Posix) libaries make use of behavious that isn't defined in the language standard.
what kind of nonsense is this? a java fanboy keeps bragging about "java built-in library" as a "java language specification"? can you differ "language's specification" with "language's standard library implementation?", or do you even know how a "language's standard library" is built? if you are incapable of making a code without a "library" (namespace or class or whatever higher level encapsulation) then we are sorry, get a life, there are still so much you need to learn, your "fast java" is not so entertaining.
Thank you for so clearly demonstrating your profound ignorance of several key points. It makes it easy for everyone to assess your contribution.
In future, would you please make your rants more entertaining.
-
Java makes multithreaded programs a damn sight easier than C++, since Java has the necessary language primitives enabling high quality concurrenty libraries and well-proven design patterns (see Doug Lea's concurrency classes, now part of the standrd library. C++ is in the "unfortunate" position that the language defines concurrency as a library issue, and the (Posix) libaries make use of behavious that isn't defined in the language standard. (That position might be better with the latest C++ standard, but who knows when implementations will be used in the real world).
I still see a lot of typical concurrency problems in Java applications. Regarding C++: you can offload the multi-threading headaches to a framework but just like Java you do need to make sure things keep happening in the correct order.
-
1.) There are "software" people who obsess over what the text file(s) looks like for state machine encoding. These are the "Java people" of the world (not using this as a pejorative) who obsess over how a code looks more than it acts,
I'm very picky about how code looks on the page -- state machine or otherwise. I think formatting is very important to readability. But I hate Java. So I thought your comment was kind of funny. But I think I know what you are trying to say. Being overly picky about looks (guilty) is one thing, but the anal retentive coding style that Java demands just drives me crazy.
But all this about using loops, state machines, threads, and every other programming pattern is silly. I mean picking one method to apply to all problems is silly. The PROBLEM you are trying to solve is what picks the programming pattern. At least if you let it. You may not recognize the ideal pattern at first, but if you find yourself writing convoluted code, or it's becoming a struggle to fit your problem to the code you are writing, then you need to rethink what you are doing.
I remember a long time ago studying recursion. I sort of got the idea but thought it was an extravagant and dangerous (stack depth problems) solution. Then, much later, I was having to write a kind of calculator. I wrote a function to do the basic four arithmetic functions in a very general way. When I had that I started running it in my head: Add 7 + 8, save the result; now return the result to caller; now divide by 3. Well, now I need to call my function again... Oh, now I'm going to have a stupid string of calls to the same function and tracking precedence is going to get hairy. How about if I just store intermediate results and re-call this function while I'm still in it? I'll just "eat" this equation completely before I ever leave the function. Oh, yeah, that's that recursion thing I studied a while back!
My data told me what solution to use. Hell, it practically begged me to use recursion. I think a lot of problems are like this, and if you learn to "listen" to your problem, it will many times give you the answer.
-
I'm very picky about how code looks on the page -- state machine or otherwise. I think formatting is very important to readability.
But all this about using loops, state machines, threads, and every other programming pattern is silly. I mean picking one method to apply to all problems is silly. The PROBLEM you are trying to solve is what picks the programming pattern. At least if you let it. You may not recognize the ideal pattern at first, but if you find yourself writing convoluted code, or it's becoming a struggle to fit your problem to the code you are writing, then you need to rethink what you are doing.
...
and if you learn to "listen" to your problem, it will many times give you the answer.
I agree with all of that.
I know when things are "going right" because my codebase becomes smaller. (Please don't mention idiots that think anything resembling "lines of code" is a good metric for progress).
-
Java makes multithreaded programs a damn sight easier than C++, since Java has the necessary language primitives enabling high quality concurrenty libraries and well-proven design patterns (see Doug Lea's concurrency classes, now part of the standrd library. C++ is in the "unfortunate" position that the language defines concurrency as a library issue, and the (Posix) libaries make use of behavious that isn't defined in the language standard. (That position might be better with the latest C++ standard, but who knows when implementations will be used in the real world).
I still see a lot of typical concurrency problems in Java applications. Regarding C++: you can offload the multi-threading headaches to a framework but just like Java you do need to make sure things keep happening in the correct order.
Oh, sure you can avoid using language and library facilites correctly, just as you can drive down the wrong side of a motorway.
The difference is that C/C++ explicitly precludes you from doing it correctly in the general case, albeit not in some ad-hoc special cases.
Don't take my word for it. Read and understand Nick Maclaren's "Why Posix Threads Are Unsuitable for C++" http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1940.pdf (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1940.pdf)
That isn't a crackpot document; Hans Boehm regards that document as an important contribution to standardisation, see http://www.hboehm.info/c++mm/ (http://www.hboehm.info/c++mm/)
I suspect that the latest C/C++ standards have improved in this respect, but how many full compilers exist and how many projects can use them due to stability and backward compatibility issues?
-
The article in the PDF is rather dramatic and focusses on dividing single tasks into multiple processes which need a tight coupling of data. Nowadays there are several ways to deal with threads in C++. Yet you need to be aware of what data belongs to which thread. Perhaps that can be offloaded as well (*) which IMHO is what the article is about: sharing data between parallel tasks. For loosely coupled tasks there isn't a problem at all.
(*) I did not look into this specifically but the article is almost 10 years old so it is reasonable to assume people got around these problems without waiting for C++ to 'evolve'.
-
The article in the PDF is rather dramatic and focusses on dividing single tasks into multiple processes which need a tight coupling of data. Nowadays there are several ways to deal with threads in C++. Yet you need to be aware of what data belongs to which thread. Perhaps that can be offloaded as well (*) which IMHO is what the article is about: sharing data between parallel tasks. For loosely coupled tasks there isn't a problem at all.
Not really. I regard multiple threads with zero inter-thread communication as a theoretical construct of no practical relevance whatsoever.
The problems are related to sharing data, not to the amount of data. If you have any communication whatsoever, then there can be intermittent problems - and problems are observed in real live code.
The author works in an environment (HPC at University of Cambridge Computing Centre) which stress tests all aspects of computation - and he has done since the 1960s. He really knows where the sore points are, and where the bones are buried.
(*) I did not look into this specifically but the article is almost 10 years old so it is reasonable to assume people got around these problems without waiting for C++ to 'evolve'.
No. The problems are fundamental and explicit.
The problems can possibly be circumvented in special cases of specific processor+memory+compiler+library + compiler switches - but I'd like to see anyone try to prove they've got all of those right.
The problems might or might not have been tidied up in the very latest standards - but who knows about the production compilers. C/C++ compilers are notoriously "bugridden" - probably because compiler writers and compiler users can and do have differing interpretation of the standards. Hell, even different compiler writers have differing interpretations!
-
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1940.pdf (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1940.pdf)
enuff said...
(https://www.eevblog.com/forum/microcontrollers/article-example-state-machine-code-for-microcontrollers/?action=dlattach;attach=138294;image)
Why Posix Threads Are Unsuitable for C++? because Posix Threads is an unholy mess.
-
Howdy,
I wanted to share a write-up I put together on a piece of code I use regularly when a microcontroller application calls for a state machine. It goes over some example state machine code and explains some basics about how state machines work. Take a look if you're interested: http://www.heptapod.com/lib/statemachines/ (http://www.heptapod.com/lib/statemachines/)
The example uses an atmega328, but the concepts could be applied to any micro that uses C. It might be a little basic if you already know this stuff, but I hope it helps any beginners or intermediate folks out there trying to get away from writing the giant while(1) loops in their event-driven microcontroller code.
Hi Jakeypoo,
I enjoyed your post / blog entry. Well done. It looks like you are learning a lot during the process. Far more than I learned reading the thread :)
Also, I just wanted to say you have my sympathies - It seems that the first rule of EEVBlogs is that when anybody is proud of their achievement others come along to say "you have done it all wrong" but never actually bother to teach what the better way is, and how or why it is better. Maybe there is a law that any programming discussion devolves into a C++ vs Java bashing thread?
I could even put up a simple "I flashed a LED with a 555" and people would endlessly comment on with gems like "oh, you should have used the CMOS parts for lower power", "oh those resistors are too high - you'll get too much noise causing jitter", "oh, are you sure that you want THAT much/little current through the LED?","Did you use a low ESR cap?", "how stable is it? You should use a crystal reference", "You can do that for 0.02c with a ATtiny, and fewer parts".
-
(*) I did not look into this specifically but the article is almost 10 years old so it is reasonable to assume people got around these problems without waiting for C++ to 'evolve'.
No. The problems are fundamental and explicit.
The problems can possibly be circumvented in special cases of specific processor+memory+compiler+library + compiler switches - but I'd like to see anyone try to prove they've got all of those right.
The problems might or might not have been tidied up in the very latest standards - but who knows about the production compilers. C/C++ compilers are notoriously "bugridden" - probably because compiler writers and compiler users can and do have differing interpretation of the standards. Hell, even different compiler writers have differing interpretations!
If the problem would be really that big we wouldn't have functioning PCs on/under our desks... IOW the problems are known and workarounds (if necessary) are in place. A lot has improved on C++ over the past 10 years (I recall the C++ mess required to program with Nokia's Symbian OS). The STL libraries also solve a lot of common programming problems.
-
(*) I did not look into this specifically but the article is almost 10 years old so it is reasonable to assume people got around these problems without waiting for C++ to 'evolve'.
No. The problems are fundamental and explicit.
The problems can possibly be circumvented in special cases of specific processor+memory+compiler+library + compiler switches - but I'd like to see anyone try to prove they've got all of those right.
The problems might or might not have been tidied up in the very latest standards - but who knows about the production compilers. C/C++ compilers are notoriously "bugridden" - probably because compiler writers and compiler users can and do have differing interpretation of the standards. Hell, even different compiler writers have differing interpretations!
If the problem would be really that big we wouldn't have functioning PCs on/under our desks... IOW the problems are known and workarounds (if necessary) are in place.
That is one of the special cases corresponding to "specific processor+memory+compiler+library + compiler switches".
A lot has improved on C++ over the past 10 years (I recall the C++ mess required to program with Nokia's Symbian OS). The STL libraries also solve a lot of common programming problems.
And, from what I can make out, introduced others.
-
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1940.pdf (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1940.pdf)
enuff said...
(https://www.eevblog.com/forum/microcontrollers/article-example-state-machine-code-for-microcontrollers/?action=dlattach;attach=138294;image)
Why Posix Threads Are Unsuitable for C++? because Posix Threads is an unholy mess.
True, but that's not the only problem with C/C++.
In C/C++ explicitly and by definition, no memory model in the C language. Anything related to that is "implementation defined" and punted to the libraries. The latest specification finally gives up on attempting to justify that gross omission by including a memory model. The success and backward compatibility are yet to be determined.
Hence the Posix (and other) libraries to do with, for example, multithreading are in an impossible position: they have to rely on language properties that are explicitly undefined and left up to the libraries to sort out. The best they can do is select a few common cases and hope programmers/users don't find the corner cases.
Memory models are very difficult; even though it was possible to start with a clean slate, Java still got it wrong and had to introduce a revised memory model! I don't fancy C/C++'s chances, but we'll see how it progresses and what crawls out of the woodwork.