EEVblog Electronics Community Forum
Electronics => Microcontrollers => Topic started by: Warhawk on May 15, 2018, 11:52:20 am
-
Hello Everyone,
I don't do programming for living but I've already done quite a few embedded applications. Today, I'd like to ask you how you typically design your state machines? I am not talking about the code but about the design. Two main questions are:
- When do you execute "state" code?
Do you use entry and exit events?
When I talk to my friends, who do embedded programming professionally, they always execute the state code right before the code exits the state. This is probably due to simplicity when using the switch-case statement.
Various topics on the internet often talks about enter and exit action for every single state. Does this have any benefits or caveats? In my opinion it does not make much sense and it opens the door for bugs.
One bonus question:
- Moore vs Mealy - does this make any difference, when it comes to embedded ?
Thanks for any comments and thoughts :-)
-
The academically pure 'Finite State Machine' gets somewhat watered down for embedded programming vs digital logic designs (where they must be kept 'pure' to work properly).
For example. entry and exit events are actually transitional states in a 'pure' FSM design, that are passed through very quickly:
case state_wait_entry:
do entry stuff.
state = state_wait;
break;
case state_wait:
do waiting stuff
if(exit_condition)
state = state_wait_exit;
break;
case state_wait_entry:
do exit stuff.
state = state_whatever_next;
break;
But because this is such a common pattern entry and exit functions are added:
...
case state_wait:
if(last_state != state)
do entry stuff.
do waiting stuff
if(exit_condition) {
do exit stuff.
next_state = state_wait_exit;
}
break;
...
last_state = state;
state = next_state;
For embedded programming FSM paradigm it is mostly used to avoid operations that would block for a long time, and to help handling asynchronous events like interrupts.
For embedded programming the Moore vs Mealy concepts make little sense... even in HDL they are 'ideals' and can get somewhat mixed..
-
I don't think it matters much.
The reason for the state machines, is to spead the execution over time. Say you have a code:
void task() {
do_a;
while(c) {
do_b;
}
do_c;
}
The problem is that you need to run many different tasks at the same time and sequential execution will not work well. Thus, you create processing functions for each of your tasks. Each processing function advances the corresponding task by a little then yields the execution so other tasks could work too. You then create a super loop which moves through all the tasks and gives opportunity to each. In the simplest way:
while() {
process_task_one();
process_task_two();
process_task_thee();
}
Now, we have to crump our sequencial execution piece by piece into the single function which will be called repeatedly. There's number of ways to do it, which are called state machines, while, in fact, they're not FSMs. The most common way:
void process_task_one() {
switch (state) {
case STATE_IDLE:
break;
case STATE_START:
do_a();
state = STATE_LOOP;
break;
case STATE_LOOP:
if (c) {
do_b();
} else {
state = STATE_STOP;
}
break;
case STATE_STOP:
do_c();
state = STATE_IDLE;
return;
}
}
Now setting the state to STATE_START will execute the sequence, so you start your task as:
int start_task_one() {
if (state != STATE_IDLE) return 0; // already running
state = STATE_START;
return 1;
}
But you can do it in a multitude of other ways as well. For example, you can represent the state by a function pointer:
void (*process_task_one)();
void process_start() {
do_a();
process_task_one = &process_loop;
}
void process_loop() {
if (c) {
do_b();
} else {
process_task_one = &process_stop;
}
}
void process_stop() {
do_c();
process_task_one = &process_idle;
}
void process_idle() {
}
Whether you have a formal entry/exit code, or how you set your states is completely immaterial. The relationship with theoretical FSMs is not of foremost importance neither. The only requirement is that the processing is fast enough and it does the same as the corresponding sequential code would do. These are the two aspects you need to concentrate on.
-
I don't think it matters much.
The reason for the state machines, is to spead the execution over time. Say you have a code:
That is just one (fairly trivial) use for a state machine, they are used for controlling any state based function irrespective of whether an RTOS is used or not.
-
Depends on the input. As far as i understood it, if the source does not debounce or denoise ideal you might have it easier to debug a Moore machine than a Mealy machine.
I however do not see an added value in additional entry and exit conditions when the transition itself can be described as a state of its own.
-
State machines are also an excellent way to document how a device works, especially if in simplified form.
(That is, not all states need to be described; but for mission-critical or safety sensitive devices, I believe state machines to be the best way to describe the correct operating procedures. Even if the device does not internally have a state machine at all.)
-
Flat state machines run out of steam when the transition diagrams get more complex. When the state machine gets complex enough, a hierarchal state machine may be easier solution for comprehension, creation, debugging and maintenance. The downside is that actual implementation of the the state machine engine will be more complex.
Here is an article showing a complex state transition diagram which would be quite challenging to be implemented using typical flat implementation: https://accu.org/index.php/journals/252 (https://accu.org/index.php/journals/252)
The article has also links to (Miro Samek's) https://www.state-machine.com/ (https://www.state-machine.com/) which has good articles on state machines and embedded systems design in general.
-
If my state machine gets larger than about two pg-dn keypresses, I split it into an HSM. Just a rule of thumb. :-+
-
I always though that the main benefit of a state machine is that the applicable code for the particular state is contained in one spot and the exclusion of unnecessary code is easily recognized as belonging to the other states.
-
I always though that the main benefit of a state machine is that the applicable code for the particular state is contained in one spot and the exclusion of unnecessary code is easily recognized as belonging to the other states.
Since my primary use of FSMs is for FPGAs, I tend to think of them as organizing a sequence of operations. In CPU terms: Instruction Fetch state, Instruction Decode state, Operand Fetch state, Operation state, Store Result state, rinse and repeat. Clearly some instructions will skip states, eg, an operand fetch may not be required or maybe the result doesn't need to be stored (in memory) RISC type CPU.
Or a short group of states to implement a handshake request/grant type of operation. Contention for memory, perhaps.
From my point of view, FSMs aren't so much to isolate the code but rather to enforce a sequence of operations.
But, yes, FSMs can make code a lot easier to understand as everything that needs to be done in one state is right there, not spread all over the place.
-
I always though that the main benefit of a state machine is that the applicable code for the particular state is contained in one spot and the exclusion of unnecessary code is easily recognized as belonging to the other states.
That is indeed a major consideration and benefit which is valuable in a professional context.
FSMs significantly ease:
- seeing that all possible combinations have been considered and dealt with, even if that is a "should not happen therefore panic" state/event
- modification and enhancement - you can see exactly what code to touch and can can see that touching it doesn't affect other state/events
- semi-automated verification and validation
- live logging and fault-finding - simply keep a compact representation of event-state history, to be dumped if necessary
- timing responsiveness, so you can prove the system's slowness is due to somebody else's stuff, not yours
- asynchronous and highly parallel systems, using the "half-sync-half-async" design pattern
Don't implement FSMs via nested if-then-else/case statements; over time those become impossible to maintain/enhance.
-
My approch is generally stacked switch / case statements. Where ISRs may toggle flag checks to enter or exit.
Each switch / case holds the states for a given task, kept as self contained as possible. Next layer up might be overall task, e.g. network layer, then top level is conditional layer for what tasks need to have there state run.
Its generally mixed in with other non fsm code for me, but for external interfacing it keep the code hard to break. Not to mention you can make the exception cases do logging and put the device in a safe state.
-
My approch is generally stacked switch / case statements.
I've seen that destroy a profitable product line. The idiots allowed it to become an unmaintainable mess over the years. Yes, the world isn't ideal, and while original designers might have good taste, those that come after them often don't - and business idiots don't care about long-term technical debt.
One technique I've seen employed successfully with a 2D table of function pointers to the actions, one dimension being the current state the other being the event.
Another scalable and maintainable technique is for each state to be a class, and each event to be a virtual method within the class; the method contains the action. The top level class is fully-populated all event metiods, with the body being either "should not happen" or "do not care" as appropriate. That allows hierarchical state machines with the minimum code in each state, but still to have simple event timing statistics plus state/event logging.
-
One technique I've seen employed successfully with a 2D table of function pointers to the actions, one dimension being the current state the other being the event.
That has the great virtue of being compact, efficient and easily verified. It's also very easy to modify. It's very hard for me to see why anyone would do anything else. With the initialization of each state and the event table for each state well commented, it's easy to understand. It's a direct translation of the state diagram topology to working code.
-
One technique I've seen employed successfully with a 2D table of function pointers to the actions, one dimension being the current state the other being the event.
That has the great virtue of being compact, efficient and easily verified. It's also very easy to modify. It's very hard for me to see why anyone would do anything else. With the initialization of each state and the event table for each state well commented, it's easy to understand. It's a direct translation of the state diagram topology to working code.
Exactly.
However, the class-based mechanism has some advantages, particularly w.r.t.
- hierarchical FSM descriptions (e.g. Harel/UML StateCharts)
- conciseness of common/default actions (i.e. in a super state/class)
- strong compile-time checking
- optimal interaction with an IDE's browse / show callers / command completion features
The last two really require a strongly typed language without macros.
-
One technique I've seen employed successfully with a 2D table of function pointers to the actions, one dimension being the current state the other being the event.
I just wanted to +1 this idea; I've used it and it is really fantastic.
For those playing along, here's an intro that I just found since my code isn't really share-able:
http://blog.mbedded.ninja/programming/general/control-methodology/a-function-pointer-based-state-machine (http://blog.mbedded.ninja/programming/general/control-methodology/a-function-pointer-based-state-machine)
..and then in the comments, the author makes a case for a simple RTOS to manage tasks instead of a big state machine. Also a pretty valid point if you've got the space.
-
One technique I've seen employed successfully with a 2D table of function pointers to the actions, one dimension being the current state the other being the event.
That has the great virtue of being compact, efficient and easily verified. It's also very easy to modify. It's very hard for me to see why anyone would do anything else. With the initialization of each state and the event table for each state well commented, it's easy to understand. It's a direct translation of the state diagram topology to working code.
On a very small scale, I used the function pointers approach some years back. It's clean! I would make the pointers and the table CONST using whatever scheme was appropriate. The last thing I want is the ability to change the transition table. That would be a lot like self-modifying code and we got out of that business decades ago.
The idea of transition tables and function pointers first came up in a compiler course I took in grad school.
https://www.amazon.com/Compiler-Construction-Digital-Computers-David/dp/047132776X (https://www.amazon.com/Compiler-Construction-Digital-Computers-David/dp/047132776X)
BTW, the book is typeset on a line printer. Very unusual for a hardbound book.
-
I'm glad i saw this thread.
I've always implemented state machines either graphically (on PLCs) or by a/multiple switch/case
I agree that they can become a mess to mantain.. especially when you have a switch inside a switch... argh! (this was a poor design choice and i was in a hurry to get a workable prototype. it's being rewritten to be less confusing to read and therefore debug.)
I never thought of using a function pointer matrix.. maybe because i never use them? but it's an interesting approach and i will read on :)
in a side note, do you know of any software that takes a state machine (whitten preferably in C) and translates it into a graph.. and vice-versa?
It seems it could be a great tool to verify if your code matches your intentions.
-
Apparently there are a number of programs for dealing with state machine graphs. Google for 'state machine graphing editor'
-
I love pointers tables.
The first time I came up with this topology was when designing menus with subemenus inside other menus on 2x16 lcd. :-DD
For each menu item I had a seperate function and menu items grouped into tables according to subemenu.
When there was a level change between submenus I was updating the main table pointer to point to the table for the specific submenu.
It was bigger than simple ifs or switch but it was a piece of cake to add/remove/modify options in any level.
-
When there was a level change between submenus I was updating the main table pointer to point to the table for the specific submenu.
It was bigger than simple ifs or switch but it was a piece of cake to add/remove/modify options in any level.
... and thus the OOP was born :)
-
I've always implemented state machines either graphically (on PLCs) or by a/multiple switch/case
I agree that they can become a mess to mantain.. especially when you have a switch inside a switch... argh! (this was a poor design choice and i was in a hurry to get a workable prototype. it's being rewritten to be less confusing to read and therefore debug.)
Yes; that's the usual trajectory :( Seen that too many times, but always managed to avoid it myself (sometimes after serious "discussions").
in a side note, do you know of any software that takes a state machine (whitten preferably in C) and translates it into a graph.. and vice-versa?
It seems it could be a great tool to verify if your code matches your intentions.
There are many that go from FSM diagram or FSM text to executable C.
Going the other way would require that the C has been written in a sane manner (starting with no macros!) and probably using a specific set of design patterns. If you are expecting something to work well with arbitrary C (e.g. nested case statements!), then you are expecting to have solved several seriously intractable problems :)
-
For graphs in general, I use Graphviz (https://www.graphviz.org/). You describe the nodes and the edges in a simple Dot language, and it lays it out for you. There is a gallery (https://www.graphviz.org/gallery/) of examples, but I think this one (https://graphviz.gitlab.io/_pages/Gallery/directed/traffic_lights.html) might be relevant here, as its Dot source (https://graphviz.gitlab.io/_pages/Gallery/directed/traffic_lights.gv.txt) is particularly simple. Graphviz does have several different layout engines, and they have quite a few knobs you can adjust, to get the kind of a diagram you want. The engines can display the graph in a window, or generate an image file; I prefer mine in SVG format.
-
Interesting discussion here. I am happy to see it.
The problem I see with the table-based FSM implementation is function pointers. I was told that the critical-safety development environment does not practically allow pointers to any functions. This is probably due to static code analysis.
Some years ago (damn, already 5) I found a set of neat macros for FSM in C. I could not find the original article except this blog post:
https://contrarymotion.net/2008/02/12/some-code-snippets-for-a-simple-c-state-machine/comment-page-1/
Attached is the file I found in my archive.
I hope this helps.
-
I was told that the critical-safety development environment does not practically allow pointers to any functions.
This kind of babble is totally meaningless, and this particular "rule" is a just a constantly recurring urban myth, and while some organization somewhere could internally follow it, it doesn't make it a sane general rule to follow. Developing code for any safety-critical system requires really deep understanding, never random hearsay "rules of thumb", especially with really poor rationale.
What the heck is even "the critical-safety development environment" :-//
I often fail to see the critique about C macro play, and use macros quite a bit. But this fsm_macros.h thing kind of opened my eyes. This is pure horror. And what's the purpose? Hide a few characters of trivial, self-documenting code away, under weird macro names that do not follow any C syntax, and that expand to {} blocks that are supposed to connect to each other in very specific ways, so that if you do any mistake (while writing code that no longer follows basic C syntax), you'll most likely inadvertly generate code that does something completely unexpected.
-
I was told that the critical-safety development environment does not practically allow pointers to any functions. This is probably due to static code analysis.
I'd be interested in seeing this mentioned in any of the well known guidelines for safety-critical software (such as MISRA-C or some IECxxx or DOxxx standards). As I already mentioned, dynamic memory allocation is usually not recommended (or sometimes even banned), but function pointers? That doesn't ring a bell. But many companies have their own set of rules, and some even recommend against using pointers altogether. Of course this is all wishful thinking, and would make a middle-sized C project a real mess with global variables everywhere. Not pretty and unmaintainable. :palm:
Decent static analysis tools can infer a whole lot of things from the source code, even with function pointers. Very intricate designs that would be hard to do static analysis on can benefit from dynamic analysis tools, which are usually pretty expensive (LDRA has this kind of tools for instance), but very effective.
-
What the heck is even "the critical-safety development environment" :-//
Siwastaja, I am not a native English speaker. Neither you are (based on the flag). I was referring to firmware development for safety-critical applications. ::)
As I mentioned in the first post - I do not program professionally. Embedded software is just my hobby and I am simply interested in different techniques, code snippets and patterns. This is the reason why I said "I was told..." :-X I got this information from colleagues developing railway automation for a quite known German company with a green logo 8)
I wish Jack Ganssle joined the thread. Hearing his opinion and practical experience would be interesting.
-
If all the pointers are initialized at compile time, I don't think there would be any issues. Not to say it might not violate the rules some PHB declared.
From a practical perspective, why would one do anything other than initialize the table at compile time and declare it CONST? If you are really paranoid, keep a CONST copy of the table and reinitialize ii if the watchdog timer goes off.
OOP is just loads of tables of function pointers, one for each object. This is why xclock now has an 80 MB footprint in core. Inheritance is just named COMMON and GOTO with fresh lipstick.
A reading suggestion:
Safer C: Developing Software for High-integrity and Safety-critical Systems
Les Hatton
McGraw-Hill 1995
Les founded Programming Research Ltd which produces a line of static code analyzers. Les has since left PRL, but has been active in safety critical code audits and such.
-
Thanks for the tip.
I will just add the following link: https://www.misra.org.uk/forum/viewtopic.php?t=240 (https://www.misra.org.uk/forum/viewtopic.php?t=240)
It seems that I may have been misinterpreting the "pointer to a function is a no-go" for years. I understand this that as long as the function pointer is const type, the world is safe.
-
If all the pointers are initialized at compile time, I don't think there would be any issues. Not to say it might not violate the rules some PHB declared.
From a practical perspective, why would one do anything other than initialize the table at compile time and declare it CONST? If you are really paranoid, keep a CONST copy of the table and reinitialize ii if the watchdog timer goes off.
For those CPUs executing code out of flash, the compiler will put the table in flash if it is declared CONST. That pretty much prevents the possibility of a pointer getting changed.
If it isn't automatically placed in flash, it is possible to force the linker to put it there anyway.
-
If all the pointers are initialized at compile time, I don't think there would be any issues. Not to say it might not violate the rules some PHB declared.
From a practical perspective, why would one do anything other than initialize the table at compile time and declare it CONST? If you are really paranoid, keep a CONST copy of the table and reinitialize ii if the watchdog timer goes off.
For those CPUs executing code out of flash, the compiler will put the table in flash if it is declared CONST. That pretty much prevents the possibility of a pointer getting changed.
If it isn't automatically placed in flash, it is possible to force the linker to put it there anyway.
An excellent point and one of the many reasons I prefer C for most things. It's easy to understand the rules and what will actually happen. Of course, for numerical work FORTRAN is better. Lex, yacc, awk and MATLAB/Octave all have their places too.
-
An excellent point and one of the many reasons I prefer C for most things. It's easy to understand the rules and what will actually happen.
Er, no. Or at least only at a superficial level.
As merely one set of examples of how developers have been demonstrated to be confused, have a look at https://queue.acm.org/detail.cfm?id=3212479 and its references.
Of course, for numerical work FORTRAN is better. Lex, yacc, awk and MATLAB/Octave all have their places too.
Er, yes :)
-
As merely one set of examples of how developers have been demonstrated to be confused, have a look at https://queue.acm.org/detail.cfm?id=3212479 and its references.
Regarding that article I agree with the first comment "This is an excellent troll and strawman argument.".
For those who don't want to take the time to read it, here is a summary:
Old computers supported C.
Modern computers all support C.
Modern computers are complex.
Modern computers have issues.
Therefore continued support for C is the cause of everything that is wrong with computers today (incl Specter & Meltdown).
(Author must be one of those functional programming types)
-
I prefer switch/case for state machines. The compiler will generally implement with jump table. You ALWAYS have to trap the possibility of an invalid state so I generally find it cleaner than a function pointer table. The minute you need logic for an invalid value for your state value, you might as well use a case structure. There might be an esoteric method in C to trap invalid function pointers but I generally avoid the super elegant solutions.
I always implement functions for transition logic. I generally have 1 high level system state machine with state machines for each individual process in the main loop. I have tried just about every approach and this always seemed to be the best low energy approximation to a good design.
-
You ALWAYS have to trap the possibility of an invalid state
Why? Unless you calculate your states, which is relatively rare, you assign the values directly or draw them from some sort of table. In either case, the probability of getting an invalid state is slim to none.
-
You ALWAYS have to trap the possibility of an invalid state
Why? Unless you calculate your states, which is relatively rare, you assign the values directly or draw them from some sort of table. In either case, the probability of getting an invalid state is slim to none.
It is more than likely that somebody will code "state++;" to move onto the next state. Works fine until somebody else removes a state from the middle of a chain of states. Also, table driven state machines are quite common, at least in "programming 201" implementations.
One nice feature of using a state machines you can put the state variable into a buffer, so when debugging or looking at crash dumps you can see what states preceded the current one. Very handy.
-
There are many that go from FSM diagram or FSM text to executable C.
Going the other way would require that the C has been written in a sane manner (starting with no macros!) and probably using a specific set of design patterns. If you are expecting something to work well with arbitrary C (e.g. nested case statements!), then you are expecting to have solved several seriously intractable problems :)
the idea is that provided i can trust this C->Graph converter, because it needs me to write code in a certain (hopefully better) manner, i can then look at the graph and be confident i didn't make stupid mistakes. then with the graph it's easier to read and analyze.
I drew the graph of my previously mentioned task, after the frankensteining.. it's a bit of a mess, while being still logical
I like the states table idea.
I like the array of states trace idea, for debugging.
-
As merely one set of examples of how developers have been demonstrated to be confused, have a look at https://queue.acm.org/detail.cfm?id=3212479 and its references.
Regarding that article I agree with the first comment "This is an excellent troll and strawman argument.".
For those who don't want to take the time to read it, here is a summary:
Old computers supported C.
Modern computers all support C.
Modern computers are complex.
Modern computers have issues.
Therefore continued support for C is the cause of everything that is wrong with computers today (incl Specter & Meltdown).
(Author must be one of those functional programming types)
OK, here's an example of the problem, from that article (read the article for the details)...
"According to the results of the survey, 36 percent were sure that they would be, and 29 percent didn't know. Depending on the compiler (and optimization level), it may or may not be. This is a fairly trivial example, yet a significant proportion of programmers either believe the wrong thing or are not sure."
That's an indication that C is part of the problem; I prefer tools that are part of the solution.
Regrettably C/C++ is littered with such things. I remember the triumphant announcement of the first C/C++ compiler that fully implemented the standard - 6 years after the standard was published. That was in the mid-noughties, so presumably it was the '99 standards.
-
I prefer switch/case for state machines. The compiler will generally implement with jump table. You ALWAYS have to trap the possibility of an invalid state so I generally find it cleaner than a function pointer table. The minute you need logic for an invalid value for your state value, you might as well use a case structure. There might be an esoteric method in C to trap invalid function pointers but I generally avoid the super elegant solutions.
You'll have to explain that in words of one syllable.
Since you have to initialise every element of the array (statically at compile time if you have any sense) then you simply "fill in" every state/event with a valid function pointer. Many such pointers are likely to be to "panicAndHalt()" or "defaultIgnore()".
If you are worried about an index being out of bounds, then use your compiler to do the error checking and/or only allow the next state to be chaned in a function that checks array bounds. If that isn't sufficient then you shouldn't be using a language which can cast a car into a sandwich.
-
You ALWAYS have to trap the possibility of an invalid state
Why? Unless you calculate your states, which is relatively rare, you assign the values directly or draw them from some sort of table. In either case, the probability of getting an invalid state is slim to none.
It is more than likely that somebody will code "state++;" to move onto the next state. Works fine until somebody else removes a state from the middle of a chain of states. Also, table driven state machines are quite common, at least in "programming 201" implementations.
If that is a problem that you can't overcome, then firstly you shouldn't be using C/C++ for that project, and secondly you have bigger problems (even if you don't realise it yet).
One nice feature of using a state machines you can put the state variable into a buffer, so when debugging or looking at crash dumps you can see what states preceded the current one. Very handy.
Yes, that is very valuable in design, comissioning, operation, and maintenance. Adding events into the buffer can also be a help.
-
OK, here's an example of the problem, from that article (read the article for the details)...
"According to the results of the survey, 36 percent were sure that they would be, and 29 percent didn't know. Depending on the compiler (and optimization level), it may or may not be. This is a fairly trivial example, yet a significant proportion of programmers either believe the wrong thing or are not sure."
That's an indication that C is part of the problem; I prefer tools that are part of the solution.
No, it was trick question.
The question impiled by the article
You have a structure that is allowed (by the standard) to be padded to a convenient size for the compiler. You create an instance of that structure. You zero the structure. You then set some of the elements of the structure to non-zero values. Is the value of the padding now guaranteed to be zero? Yes / No / Don't know
No matter which answer you pick, you are wrong. Pick one and I'll prove the opposite to you (with code).
It is unfair as me asking you "Could you write a program in (your preferred language) to calculate how many fairies can dance on the head of a pin?".
-
OK, here's an example of the problem, from that article (read the article for the details)...
"According to the results of the survey, 36 percent were sure that they would be, and 29 percent didn't know. Depending on the compiler (and optimization level), it may or may not be. This is a fairly trivial example, yet a significant proportion of programmers either believe the wrong thing or are not sure."
That's an indication that C is part of the problem; I prefer tools that are part of the solution.
No, it was trick question.
The question impiled by the article
You have a structure that is allowed (by the standard) to be padded to a convenient size for the compiler. You create an instance of that structure. You zero the structure. You then set some of the elements of the structure to non-zero values. Is the value of the padding now guaranteed to be zero? Yes / No / Don't know
No matter which answer you pick, you are wrong. Pick one and I'll prove the opposite to you (with code).
That's very revealing because, if you think about it, what you claim to be able to do is simply impossible.
Hint: you might be able to make your point for one compiler with one target machine with one set of compiler flags - for one version of that compiler (because C compilers/linkers can and do change the code they emit).
-
OK, here's an example of the problem, from that article (read the article for the details)...
"According to the results of the survey, 36 percent were sure that they would be, and 29 percent didn't know. Depending on the compiler (and optimization level), it may or may not be. This is a fairly trivial example, yet a significant proportion of programmers either believe the wrong thing or are not sure."
That's an indication that C is part of the problem; I prefer tools that are part of the solution.
No, it was trick question.
The question impiled by the article
You have a structure that is allowed (by the standard) to be padded to a convenient size for the compiler. You create an instance of that structure. You zero the structure. You then set some of the elements of the structure to non-zero values. Is the value of the padding now guaranteed to be zero? Yes / No / Don't know
No matter which answer you pick, you are wrong. Pick one and I'll prove the opposite to you (with code).
That's very revealing because, if you think about it, what you claim to be able to do is simply impossible.
Hint: you might be able to make your point for one compiler with one target machine with one set of compiler flags - for one version of that compiler (because C compilers/linkers can and do change the code they emit).
I'll bite....
This will ALWAYS have zeros in the padding (The 'Yes' example):
int main(int argc, char *argv[])
{
struct padded s;
int i;
printf("'s' is %i bytes of memory\n", (int)sizeof(s));
/* Clear structure*/
memset(&s,0,sizeof(s));
/* Set some values */
s.a = 0xAA;
s.b = 0xBBBBBBBB;
printf("Byte dump:\n");
for(i = 0; i <sizeof(s); i++) {
printf("%02x ",((unsigned char *)&s)[i]);
}
printf("\n");
return 0;
}
Is very likely to have random junk in the padding, as it depends on things we have no knowledge of (The "Don't know" example)
#include <stdio.h>
#include <memory.h>
struct padded {
unsigned char a;
unsigned int b;
};
int main(int argc, char *argv[])
{
struct padded s;
int i;
printf("'s' is %i bytes of memory\n", (int)sizeof(s));
/* Clear structure*/
s.a = 0;
s.b = 0;
/* Set some values */
s.a = 0xAA;
s.b = 0xBBBBBBBB;
printf("Byte dump:\n");
for(i = 0; i <sizeof(s); i++) {
printf("%02x ",((unsigned char *)&s)[i]);
}
printf("\n");
return 0;
}
And finally this proves that even when you zero out every fields in a structure the padding are not guaranteed to be zero (The "No" example):
#include <stdio.h>
#include <memory.h>
struct padded {
unsigned char a;
unsigned int b;
};
int main(int argc, char *argv[])
{
struct padded s;
int i;
memset(&s,0xFF,sizeof(s));
printf("'s' is %i bytes of memory\n", (int)sizeof(s));
/* Clear every field in the structure*/
s.a = 0;
s.b = 0;
/* Set some values */
s.a = 0xAA;
s.b = 0xBBBBBBBB;
printf("Byte dump:\n");
for(i = 0; i <sizeof(s); i++) {
printf("%02x ",((unsigned char *)&s)[i]);
}
printf("\n");
return 0;
}
I now challenge you to find a compiler and a set of options that breaks *any* of these examples.
Of course on some architectures and/or switches padding will not be needed. I assume that with no padding present the question is invalid - you can't say anything about the value of padding when the padding doesn't exist.
-
I tend to implement very small, 2D state machines just by a step counter.
It seems that I may have been misinterpreting the "pointer to a function is a no-go" for years. I understand this that as long as the function pointer is const type, the world is safe.
Every function call at link time is already equivalent to a constant function pointer - for statically linked libraries. Does that imply dynamically linked libraries are forbidden?
The question impiled by the article
You have a structure that is allowed (by the standard) to be padded to a convenient size for the compiler. You create an instance of that structure. You zero the structure. You then set some of the elements of the structure to non-zero values. Is the value of the padding now guaranteed to be zero? Yes / No / Don't know
No matter which answer you pick, you are wrong. Pick one and I'll prove the opposite to you (with code).
How is the padding (gaps between fields) of a structure changed by changing values inside the structure at runtime? Why should the padding length therefore become zero?
Accessing raw memory and disabling compiler checks might allow to write to the pad bytes (if the compiler included them at all) which are to be allocated by the memory management, but that would also not change the length of the padding, only it´s content.
-
The question impiled by the article
You have a structure that is allowed (by the standard) to be padded to a convenient size for the compiler. You create an instance of that structure. You zero the structure. You then set some of the elements of the structure to non-zero values. Is the value of the padding now guaranteed to be zero? Yes / No / Don't know
No matter which answer you pick, you are wrong. Pick one and I'll prove the opposite to you (with code).
How is the padding (gaps between fields) of a structure changed by changing values inside the structure at runtime? Why should the padding length therefore become zero?
Accessing raw memory and disabling compiler checks might allow to write to the pad bytes (if the compiler included them at all) which are to be allocated by the memory management, but that would also not change the length of the padding, only it´s content.
Sorry for the confusion - not the quantity of padding (which is fixed at compile time, and depends on architecture, #pragmas, compiler options and so on), but the values held in that padding (e.g. the bytes that would be written to a file if you wrote the structure to a file with "fwrite()").
-
Yeah, thanks, i stumbled over "Is the value of the padding now guaranteed to be zero?" ... it means the content of pad bytes, not their length.
However, no one guaranteed their existence, cause... it depends on the alignment of the structure.
-
There's a whole embedded OS and graphical IDE for state machines over here: http://www.state-machine.com/ (http://www.state-machine.com/)
-
An excellent point and one of the many reasons I prefer C for most things. It's easy to understand the rules and what will actually happen.
Er, no. Or at least only at a superficial level.
As merely one set of examples of how developers have been demonstrated to be confused, have a look at https://queue.acm.org/detail.cfm?id=3212479 and its references.
Of course, for numerical work FORTRAN is better. Lex, yacc, awk and MATLAB/Octave all have their places too.
Er, yes :)
Sadly, I would not disagree about the knowledge level of the generic programmer. My general observation is that the entire compile, link, execute cycle is magic to most for any language, even K&R C or C89.
I'm not the generic programmer. I have copies of the language standards and refer to them whenever needed. I *never* call a library function without checking the argument types and orders unless it's a function I just used a few minutes earlier. I also have and have read several books on compiler optimization and "Computer Architecture: A Quantitative Approach" by Patterson and Hennessy. I've only read the first 3 eds. of the latter as I've not had a serious project since the 4th ed came out. But it would be the first thing on my To Do list if I were tasked with a high performance programming assignment.
Programmers have even less of a clue what C++ does. In fact, I assert that no one understands C++. However, I shall not bother with my canonical example. Suffice it to say that I can present a trivial code example which will require reading all the source code, the language standard *and* the compiler implementation notes to figure out what one line does.
I read language and processor manuals for entertainment for many years. I am what Fred Brooks described as a "language lawyer".
For example, section 8.3.5 of the F77 standard says "upon return from a function or subroutine, named COMMON may be undefined". This language was inserted into the standard at the behest of Burroughs so that they could state that the new Burroughs 5000 had an F77 compliant compiler. That machine was one of the first stack based machines and so far as I know the only machine that implemented a tagged architecture. Every memory location had bits that stored the type of value stored at that address.
When the first RISC machines came out, I spent a lot of time explaining to people what they needed to do to make their code work. I've also done little stunts such as demonstrate passing data between functions without using globals or arguments by exploiting the order in which automatic variables appeared in the stack frame.
Curiously, I've never seriously used F95 and later. Copies of the standard are expensive and I've never found a decent book on modern FORTRAN that explained what the underlying memory map and structure was. Of course, that is in part because I can seamlessly move between C89/99 and F77. I got a 6x speedup in a program by having C create a table of F77 function pointers and addresses on the first call and then executing the table after the first call. This was a big deal with users who were processing 100 million line ASCII files.
-
It is more than likely that somebody will code "state++;" to move onto the next state.
Cannot do "state++" if state is a function pointer.
-
As merely one set of examples of how developers have been demonstrated to be confused, have a look at https://queue.acm.org/detail.cfm?id=3212479 and its references.
Regarding that article I agree with the first comment "This is an excellent troll and strawman argument.".
(...)
Pretty much so. This article has been posted to the comp.lang.c newsgroup and has elicited a fair amount of posts.
Attention whores (whether this is done on purpose or not) live on this kind of negative-sided, fallacious articles, that unfortunately tend to generate a lot more traction than constructive ones.
-
It is more than likely that somebody will code "state++;" to move onto the next state.
Cannot do "state++" if state is a function pointer.
Sure, but state could just be an integer indexing a function pointers' table.
-
It is more than likely that somebody will code "state++;" to move onto the next state.
Cannot do "state++" if state is a function pointer.
"stateIndex++", should you have insufficient taste to do that.
-
As merely one set of examples of how developers have been demonstrated to be confused, have a look at https://queue.acm.org/detail.cfm?id=3212479 and its references.
Regarding that article I agree with the first comment "This is an excellent troll and strawman argument.".
(...)
Pretty much so. This article has been posted to the comp.lang.c newsgroup and has elicited a fair amount of posts.
Attention whores (whether this is done on purpose or not) live on this kind of negative-sided, fallacious articles, that unfortunately tend to generate a lot more traction than constructive ones.
I wonder what proportion of C programmers read comp.lang.c. ?
I wonder whether those that do are more competant than the majority of C programmers?
The difference between theory and practice is that in theory there is no difference, whereas...
-
An excellent point and one of the many reasons I prefer C for most things. It's easy to understand the rules and what will actually happen.
Er, no. Or at least only at a superficial level.
As merely one set of examples of how developers have been demonstrated to be confused, have a look at https://queue.acm.org/detail.cfm?id=3212479 and its references.
Of course, for numerical work FORTRAN is better. Lex, yacc, awk and MATLAB/Octave all have their places too.
Er, yes :)
Sadly, I would not disagree about the knowledge level of the generic programmer. My general observation is that the entire compile, link, execute cycle is magic to most for any language, even K&R C or C89.
A distressingly high proportion of candidates I've interviewed can't even begin to describe what a compiler emits for a simple function call with arguments. Any handwaving pseudocode answer would be sufficient, but they can't manage that. Nonetheless, they do find employment as C programmers
Programmers have even less of a clue what C++ does. In fact, I assert that no one understands C++.
And that included the people designing and specifying C++ templates. They thought they did until their noses were very publicly rubbed in their ignorance. They refused to believe their own C++ template language was itself Turing-complete.
While I disagree with the use of "discovered" in this statement...
"Historically TMP is something of an accident; it was discovered during the process of standardizing the C++ language that its template system happens to be Turing-complete"[1]
it does indicate that the tool itself was beyond its designers comprehension.
[1]https://en.wikibooks.org/wiki/C%2B%2B_Programming/Templates/Template_Meta-Programming#History_of_TMP
<Snipped sensible observations>
-
OK, here's an example of the problem, from that article (read the article for the details)...
"According to the results of the survey, 36 percent were sure that they would be, and 29 percent didn't know. Depending on the compiler (and optimization level), it may or may not be. This is a fairly trivial example, yet a significant proportion of programmers either believe the wrong thing or are not sure."
That's an indication that C is part of the problem; I prefer tools that are part of the solution.
No, it was trick question.
The question impiled by the article
You have a structure that is allowed (by the standard) to be padded to a convenient size for the compiler. You create an instance of that structure. You zero the structure. You then set some of the elements of the structure to non-zero values. Is the value of the padding now guaranteed to be zero? Yes / No / Don't know
No matter which answer you pick, you are wrong. Pick one and I'll prove the opposite to you (with code).
That's very revealing because, if you think about it, what you claim to be able to do is simply impossible.
Hint: you might be able to make your point for one compiler with one target machine with one set of compiler flags - for one version of that compiler (because C compilers/linkers can and do change the code they emit).
I'll bite....
This will ALWAYS have zeros in the padding (The 'Yes' example):
Sigh. I've omitted your code which indicates that you didn't understand the hint, let alone the point.
-
Regarding structure padding: the ISO C standard states it clearly:
When a value is stored in an object of structure or union type, including in a member object, the bytes of the object representation that correspond to any padding bytes take unspecified values.
Meaning you can't count on padding bytes having any specific value.
Compiler writers can do pretty much what they want with padding bytes, since it's unspecified.
If you memset() the whole structure with zero, of course padding bytes will get zeroed out. It's just block memory access. But once you write to any struct member again, the padding bytes may or may not keep their zero value. The underlying processor architecture may modify the padding bytes for any reason, and the compilers are not supposed to care.
-
A distressingly high proportion of candidates I've interviewed can't even begin to describe what a compiler emits for a simple function call with arguments. Any handwaving pseudocode answer would be sufficient, but they can't manage that. Nonetheless, they do find employment as C programmers
The set of skills to get the job is different from the set of skill to do the job, often even opposite.
It may bot be obvious with programmers. A more intuitive example is presidential elections. The set of skills necessary for election complain is almost entirely opposite to what a good president needs to do the job.
-
Regarding structure padding: the ISO C standard states it clearly: When a value is stored in an object of structure or union type, including in a member object, the bytes of the object representation that correspond to any padding bytes take unspecified values.
Meaning you can't count on padding bytes having any specific value.
Compiler writers can do pretty much what they want with padding bytes, since it's unspecified.
If you memset() the whole structure with zero, of course padding bytes will get zeroed out. It's just block memory access. But once you write to any struct member again, the padding bytes may or may not keep their zero value. The underlying processor architecture may modify the padding bytes for any reason, and the compilers are not supposed to care.
Sounds like a potential security vulnerability in that it may allow bits of highly secret information to leak into unexpected places where protecting access is not considered.
-
It is more than likely that somebody will code "state++;" to move onto the next state.
Cannot do "state++" if state is a function pointer.
Sure, but state could just be an integer indexing a function pointers' table.
I guess function pointers are not only more flexible, faster and use less memory compared to the tables, function pointers are also safer.
-
There are myriads of other potential ways of hiding stuff in memory, and unless your software permanently checks whether any memory area has been modified unexpectedly (using CRCs for instance, but even so, the CRCs could be compromised in the right way), you have no real means of controlling this if the areas in question are not protected anyway.
You still have a portable way of forcing padding bytes to zero.
Every time you write to a struct member, zero out the following padding bytes after the write (dummy bytes between this member and the next member) with a call to memset(). You can use offsetof() to get the index of each member inside the struct. Granted it would be cumbersome, but it works. You could then also check if the padding bytes have changed values by accessing them as bytes, again using offsetof() to compute the pointer to the padding bytes, and compare them to zero. This should do the trick in a fairly portable way, but you'd still be in a kind of gray area. Here we're assuming that only writes to struct members could be the cause of modification of padding bytes. This assumption is reasonable. But you may encounter some platform that still can't guarantee that padding bytes' values are retained even if no write occurs. It's probably very unlikely, but you have no guarantee.
-
You still have a portable way of forcing padding bytes to zero.
How about you arrange the structure members so that there's no padding necessary. This is very easy to do and doesn't take any time at all.
Even if you can't avoid padding, you can always add reserved structure members where the padding would be.
-
You still have a portable way of forcing padding bytes to zero.
How about you arrange the structure members so that there's no padding necessary. This is very easy to do and doesn't take any time at all.
Even if you can't avoid padding, you can always add reserved structure members where the padding would be.
That's right :)
But it's not that portable, though. Struct member alignment depends on the target platform and possibly compiling options. So you can't really devise a struct arrangement that guarantees no extra padding at all in all cases, unless you force struct alignment (which in turn can be problematic on some platforms that don't allow unaligned memory access).
That said, you don't necessarily have to be perfectly portable if you intend not to and you document it properly, especially for embedded stuff. In this case, I would suggest doing what you said AND forcing struct alignment with '__attribute__((aligned(xx))' (with GCC) or the more pervasive #pragma pack(xx) which still happens to work with most compilers. Thus you'll guarantee proper alignment and no padding.
-
You still have a portable way of forcing padding bytes to zero.
How about you arrange the structure members so that there's no padding necessary. This is very easy to do and doesn't take any time at all.
Even if you can't avoid padding, you can always add reserved structure members where the padding would be.
That's right :)
But it's not that portable, though. Struct member alignment depends on the target platform and possibly compiling options. So you can't really devise a struct arrangement that guarantees no extra padding at all in all cases, unless you force struct alignment (which in turn can be problematic on some platforms that don't allow unaligned memory access).
That said, you don't necessarily have to be perfectly portable if you intend not to and you document it properly, especially for embedded stuff. In this case, I would suggest doing what you said AND forcing struct alignment with '__attribute__((aligned(xx))' (with GCC) or the more pervasive #pragma pack(xx) which still happens to work with most compilers. Thus you'll guarantee proper alignment and no padding.
Avoiding padding is trivial on everything I've ever used which was pretty much every participant in the Unix wars.
You allocate members from largest to smallest. If you do that no padding is required and the structure is portable across everything.
-
A distressingly high proportion of candidates I've interviewed can't even begin to describe what a compiler emits for a simple function call with arguments. Any handwaving pseudocode answer would be sufficient, but they can't manage that. Nonetheless, they do find employment as C programmers
Not to be argumentative, but for applications-level programmers writing for a high-level operating system (Windows, Unix), I have to ask: who cares and why does it matter?
(Sure, for embedded stuff, where stack and register space are limited, it kinda matters, and the Keil C51 manual has some detail on what it assembly code it creates for specific conditions.)
-
Avoiding padding is trivial on everything I've ever used which was pretty much every participant in the Unix wars. You allocate members from largest to smallest.
That works only as long as you do not need a new version of the library, with added members in the same structure, to be backwards compatible with older binaries. (So, basically, stuff in the standard C library, or used between userspace and the kernel.)
On the other hand, the only structure that I am aware of that has been sensitive to padding bytes, is struct sigaction. Rather than relying on e.g. struct sigaction act = {0}, it should be cleared to zero using e.g. memset(&act, 0, sizeof act). Quite possibly its usual implementation via union and preprocessor macros is a culprit... All the other structures seem to have explicit "padding" members that can be reused for future extension, like struct stat64 on most systems.
-
A distressingly high proportion of candidates I've interviewed can't even begin to describe what a compiler emits for a simple function call with arguments. Any handwaving pseudocode answer would be sufficient, but they can't manage that. Nonetheless, they do find employment as C programmers
Not to be argumentative, but for applications-level programmers writing for a high-level operating system (Windows, Unix), I have to ask: who cares and why does it matter?
(Sure, for embedded stuff, where stack and register space are limited, it kinda matters, and the Keil C51 manual has some detail on what it assembly code it creates for specific conditions.)
When run times are measured in tens of thousands of CPU days, everything matters. I wrote a seismic processing code which used a double stride through the array and temporary variables for the A and B portions of the stride because it got me a 5% speedup on a DEC Alpha which at the time was faster than x86 by a factor of 5x. This also was the only instance in my life where i used a computed GOTO in FORTRAN. That saved me a long it-then-else with the attendant conditional delays.
In the end, what matters most is what type of problem are you solving.
In high performance computing you worry about every detail of the processor and compiler. Small changes in code or machine can have very large impacts upon performance. You study the hardware, the compiler and the program and then run test cases to find the best solution.
-
But it's not that portable, though. Struct member alignment depends on the target platform and possibly compiling options. So you can't really devise a struct arrangement that guarantees no extra padding at all in all cases, unless you force struct alignment (which in turn can be problematic on some platforms that don't allow unaligned memory access).
It is not portable in theory, but in practice if you align 64-bit members to 8-byte boundaries, 32-bit members to 4-byte boundaries and 16-bit members to 2-byte boundaries (all relative to the beginning of the structure), and then round up the size of the structure (by adding reserved items), you won't need any padding.
-
A distressingly high proportion of candidates I've interviewed can't even begin to describe what a compiler emits for a simple function call with arguments. Any handwaving pseudocode answer would be sufficient, but they can't manage that. Nonetheless, they do find employment as C programmers
Not to be argumentative, but for applications-level programmers writing for a high-level operating system (Windows, Unix), I have to ask: who cares and why does it matter?
(Sure, for embedded stuff, where stack and register space are limited, it kinda matters, and the Keil C51 manual has some detail on what it assembly code it creates for specific conditions.)
There are myriad other questions in the same vein that are applicable to "high level programmers", such as "what caches there are in the system you have used, and what are their principal characteristics", "what is a two phase commit, and why is it necessary", "where have you used/seen an FSM" etc etc etc.
The answers to such questions indicate whether the candidate understands theory and how it informs/shapes practice, whether they are curious about technology or simply time-serving sheep. That's enlightening.
-
A distressingly high proportion of candidates I've interviewed can't even begin to describe what a compiler emits for a simple function call with arguments. Any handwaving pseudocode answer would be sufficient, but they can't manage that. Nonetheless, they do find employment as C programmers
Not to be argumentative, but for applications-level programmers writing for a high-level operating system (Windows, Unix), I have to ask: who cares and why does it matter?
(Sure, for embedded stuff, where stack and register space are limited, it kinda matters, and the Keil C51 manual has some detail on what it assembly code it creates for specific conditions.)
When run times are measured in tens of thousands of CPU days, everything matters. I wrote a seismic processing code which used a double stride through the array and temporary variables for the A and B portions of the stride because it got me a 5% speedup on a DEC Alpha which at the time was faster than x86 by a factor of 5x. This also was the only instance in my life where i used a computed GOTO in FORTRAN. That saved me a long it-then-else with the attendant conditional delays.
In the end, what matters most is what type of problem are you solving.
In high performance computing you worry about every detail of the processor and compiler. Small changes in code or machine can have very large impacts upon performance. You study the hardware, the compiler and the program and then run test cases to find the best solution.
Well said.
From my experience I'll add high-availability telecoms systems.
For example, I've seen other people come an almighty cropper (with two companies CEOs in contact about it) because they didn't understand sufficient theory and practice to be able to ask the salesman necessary pointed questions about a disc system's operation and its effects on performance.
-
Regarding structure padding: the ISO C standard states it clearly: When a value is stored in an object of structure or union type, including in a member object, the bytes of the object representation that correspond to any padding bytes take unspecified values.
Meaning you can't count on padding bytes having any specific value.
Compiler writers can do pretty much what they want with padding bytes, since it's unspecified.
If you memset() the whole structure with zero, of course padding bytes will get zeroed out. It's just block memory access. But once you write to any struct member again, the padding bytes may or may not keep their zero value. The underlying processor architecture may modify the padding bytes for any reason, and the compilers are not supposed to care.
Even the technical correct answer to the question "Will any padding be filled with zeros?" is "I do not know", it is ambiguous.
Does it mean "I am ignorant of the answer to the question" or is it "I cannot make any assumption about the values of padding, it may or may not be filled with zeros, so the answer isn't yes or no".
It is a trick question.
-
"It is implementation defined." is the strictly correct answer. I'm not going to look it up in the standard, but I am highly sensitized to the "implementation defined" and "undefined" clauses. Padding is one of them.
I was offered a job at Digital Switch as CASE tools lead for a 600 person group. A 15 minute conversation with the hiring manager in a borrowed cubicle in another building followed by a meeting with an HR flack to discuss salary. I never met or even saw anyone I would be working with.I initially accepted, but after going through the drug testing and a bunch of other BS I got cold feet and backed out. I felt very much like a lamb being led to slaughter to satisfy the hiring manager's superiors. This was not long after the big SS7 meltdown in the 90's.
The thing I find sad is I wrote a couple of 15,000 line libraries which included a parser built with lex and yacc and the FORTRAN calling C calling FORTRAN table of function pointers. It ran in operation without any maintenance for about half the 15-16 years it was in use. The first year the system it was deployed I wrote the release notes. We had fewer than a dozen user submitted bug reports. By the time the company merged to form a super major there were almost no bug reports at all. Most of the work was done by me and one other contractor. He suggested we have a regression test facility, so I built one which we ran every time the system was built. Any time we wrote a piece of code the next activity was to create a basic test suite and compile and test on a couple of systems. The whole thing was a port of scientist written code from VMS to Unix. Ulimately it would compile on 6 systems, Sun, SGI, IBM, DEC, Intergraph and HP. The only #ifdefs were for byte sex and RECL=. Initial port was SunOS 4.1.1 and Intergraph CLIX, a very bare bones (15 or 16 character file names) Sys V implementation. The IBM took a month or two because the IBM compiler would not allow branching into conditionals. The HP port took 2-3 weeks. I did the Ultrix and Irix ports in about 4 hours on an idle afternoon. The official stance was it was supported on any platform that that the business affiliate would pay for validating the test suite. That did a marvelous job of cutting off people complaining about the "lack of support" on whatever systems they had bought.
-
I have always found the switch/case way of implementing a state machine kind of a hack.
I know you are all C fanboys but I personally like the async-await pattern (C#/TypeScript) very much (as an example).
It implements a state machine in the background to keep track of to where execution was progressed.
So in that light I seldom write naked switch/case state machines and although I try to avoid macros like the plague, in this case they enable a cleaner syntax. The state machine becomes a task that codes the functionality as sequential list of statements. (https://github.com/obiwanjacobi/atl/blob/master/Source/Code/Arduino%20Libraries/ATL_Process/examples/Task/CounterTask.h)
[2c]
-
I have always found the switch/case way of implementing a state machine kind of a hack.
I know you are all C fanboys but I personally like the async-await pattern (C#/TypeScript) very much (as an example).
It implements a state machine in the background to keep track of to where execution was progressed.
Switch/if-then-else is adequate for very simple FSMs, but rapidly becomes incomprehensible and unmaintainable.
The half-sync half-async design pattern (by wiatever name :) ) is indeed very powerful, comprehensible and scalable in terms of performance. However it is completely language independent and does not favour "Microsoft's Java", even if Microsoft does use it a lot in their frameworks built on top of their language.
-
It’s also resource hungry on low powered devices, not to mention adding even more indeterminism for real time systems.
But then, if you’re writing in C# under CLR, you won’t be doing deterministic real time systems, let alone on resource limited platforms.
-
It’s also resource hungry on low powered devices, not to mention adding even more indeterminism for real time systems.
But then, if you’re writing in C# under CLR, you won’t be doing deterministic real time systems, let alone on resource limited platforms.
I used the C# reference as an example for how async/await works. Not suggesting to use it in a project with any set of requirements. Hobby stuff and Proof of Concept or just tinkering is another matter.
Although the idea and mechanism are language independent, a language integrated implementation does make it sooo much nicer.
Also there is nothing wrong with abstraction or indeterminism (assuming you mean roughly the same as abstraction-ism with that).
C and C++ are abstractions or do you code in ASM? :horse:
Any good library is an abstraction. I think you should be careful to chuck things on the "too expensive" (resources/learning curve/etc.) wagon and not consider it any further. It may not be more expensive that you trying to do it yourself.
Also, It may be worth the cost of using more resources for having more readable (understandable/maintainable) code. Depends.
Perhaps only a very small portion of the code needs to be close to the metal...?
-
Also, It may be worth the cost of using more resources for having more readable (understandable/maintainable) code. Depends.
You need to put this into perspective.
If you live in a country where everyone is sober, a statement that small quantity of alcohol is good for your health might be a great wisdom. However, in a country where everyone is totally and completely drunk all the time, the same statement would be just a lame excuse, a good advice would be to drink less.
With so much bloat everywhere (which, by the way, makes code less readable and less maintainable), a sensible advise would be to bloat less.
-
I used the C# reference as an example for how async/await works. Not suggesting to use it in a project with any set of requirements. Hobby stuff and Proof of Concept or just tinkering is another matter.
Although the idea and mechanism are language independent, a language integrated implementation does make it sooo much nicer.
In what way are they integrated into the language and why is that helpful?
In my experience having them (or their primitives) implemented as library classes/functions is sufficient.
-
Also, It may be worth the cost of using more resources for having more readable (understandable/maintainable) code. Depends.
You need to put this into perspective.
If you live in a country where everyone is sober, a statement that small quantity of alcohol is good for your health might be a great wisdom. However, in a country where everyone is totally and completely drunk all the time, the same statement would be just a lame excuse, a good advice would be to drink less.
With so much bloat everywhere (which, by the way, makes code less readable and less maintainable), a sensible advise would be to bloat less.
Like I said it depends. First what you call bloat I call convenience (for instance) - so that's all a matter of opinion. What type of project, what skill-level the devs have, what legacy the company has etc. All I am saying is: think! Do not assume, do not discard ideas until you really understand them, try out new things (how will you grow?) and see if they fit. So speak of moderation in a drunk crowd and speak of experimenting in a sober crowd.
Using a higher level of abstract (lets assume more overhead) may be a valid choice when the problem is not in the real-time-ness of the solution but in the complexity of its logic (for instance).
(back to the topic)
Like the state-machines: the flow of actions can get from non-obvious to really confusing with if/then/else or switch/case implementations. Not separating the code under a case out into a function worsen the issue and may yield switch statements of several 100 lines.
I would not consider it bloat to have a mechanism/library/language feature to make that sort of code more readable even if it is not more performant (assuming no requirements exist that inhibit this choice).
----
I used the C# reference as an example for how async/await works. Not suggesting to use it in a project with any set of requirements. Hobby stuff and Proof of Concept or just tinkering is another matter.
Although the idea and mechanism are language independent, a language integrated implementation does make it sooo much nicer.
In what way are they integrated into the language and why is that helpful?
In my experience having them (or their primitives) implemented as library classes/functions is sufficient.
I would assume a language integrated feature works more bug-free than a library and the resulting syntax reads more natural.
"so much nicer" is beyond sufficient ;D
-
I used the C# reference as an example for how async/await works. Not suggesting to use it in a project with any set of requirements. Hobby stuff and Proof of Concept or just tinkering is another matter.
Although the idea and mechanism are language independent, a language integrated implementation does make it sooo much nicer.
In what way are they integrated into the language and why is that helpful?
In my experience having them (or their primitives) implemented as library classes/functions is sufficient.
I would assume a language integrated feature works more bug-free than a library and the resulting syntax reads more natural.
"so much nicer" is beyond sufficient ;D
I wouldn't assume that; my experience would lead me to believe the opposite.
Every time a "feature" is added to a language it will interact with all the other features - probably in unanticipated ways. Start by considering the interaction between templates and exceptions in C++, then have a look at home-grown DSLs (domain specific languages).
Contrast that with solid easily defined language plus libraries with a decent modern IDE.
-
(back to the topic)
Like the state-machines: the flow of actions can get from non-obvious to really confusing with if/then/else or switch/case implementations. Not separating the code under a case out into a function worsen the issue and may yield switch statements of several 100 lines.
I would not consider it bloat to have a mechanism/library/language feature to make that sort of code more readable even if it is not more performant (assuming no requirements exist that inhibit this choice).
Excellent example.
Someone creates a state machine which is too big and unmanageable. I don't think the effect may be measured by the number of lines - few hundred lines is not that bad, depending on the way it is all organized, even few thousand may net be bad. On the other hand, 50 lines may be enough to create a mess. The case statement for a state machine is reminiscent of the Spaghetti code of old ages, and if you don't think well, your state machine can turn into a mess very quickly. Assume this happens - you created a state machine which is unmanageable (happened to me few times). This is already a bloat. The solution to this is to simplify the design - may be use different set of states, may be use hierarchy, may be avoid the state machine at all, may be re-think your data structure. At any rate, you need to throw away the mess, re-think it and re-do it in simpler, more efficient and more manageable way. This is a sad situation, but you should've thought of this before.
What people do instead? They try to preserve the mess while changing the form - using libraries, creating tables, may be using function pointers, may be switching to C++. These things may be useful, but it is possible to create/maintain a mess with any of these. Somehow, changing the algorithms and logical structure of "already working" solution looks like impossible task. On the other hand, using a library (or similar) which may magically organize the messy project looks easy. They try to preserve the worthless existing codebase as if it was their flash and blood. So, libraries get added, languages switched. This adds more bloat, but doesn't really clean the mess - may be ever so slightly.
We all know where it all moves - more libraries, RTOS, bigger MCU, FPGA - things keep snowballing - there's actually no end. And what is it all for? To perform a task which can be done on tiny little MCU with much simpler code and much less of development time? If you ask, they'll tell you that all this bloat simplifies (sic!) their work and make time-to-the-market way shorter and the extra-cost of the hardware doesn't matter. What else you expect them to say?
-
It´s often that people don´t understand that their model just changed from one dimensional to multidimensional and try to compensate by adding a mess to the one dimensional state machine.
-
It´s often that people don´t understand that their model just changed from one dimensional to multidimensional and try to compensate by adding a mess to the one dimensional state machine.
What do you mean by "multidimensional" in this context? The two dimensions are "states" and "events" :)
It is often beneficial to split one large FSM into multiple smaller FSMs each with independent states and events between the smaller FSMs. But I wouldn't call that "multidimensional", I'd call it "good engineering taste" :)
-
It’s also resource hungry on low powered devices, not to mention adding even more indeterminism for real time systems.
But then, if you’re writing in C# under CLR, you won’t be doing deterministic real time systems, let alone on resource limited platforms.
I used the C# reference as an example for how async/await works. Not suggesting to use it in a project with any set of requirements. Hobby stuff and Proof of Concept or just tinkering is another matter.
Although the idea and mechanism are language independent, a language integrated implementation does make it sooo much nicer.
Also there is nothing wrong with abstraction or indeterminism (assuming you mean roughly the same as abstraction-ism with that).
C and C++ are abstractions or do you code in ASM? :horse:
Any good library is an abstraction. I think you should be careful to chuck things on the "too expensive" (resources/learning curve/etc.) wagon and not consider it any further. It may not be more expensive that you trying to do it yourself.
Also, It may be worth the cost of using more resources for having more readable (understandable/maintainable) code. Depends.
Perhaps only a very small portion of the code needs to be close to the metal...?
It’s about using the right tool for the job. The time definite real time systems that I work on pretty much rule out anything that rely on JIT compilation or garbage collection. These tend to demand process responses well into the sub millisecond region, and event responses down to sub 10us and less, for example in my case digitally controlled SMPS and mixed signal RF.
At the UI, sure, whatever floats your boat, the event mechanism underlying most application UIs is nothing but a state machine. I will caveat that, though, and address the interminable end user frustration of random hangs while the runtime goes off and does some housekeeping.
As an aside, with my enterprise software hat on, I’ve still yet to have demonstrated anywhere where JIT compilation offers a real overall benefit, usually it’s the opposite, and it’s not unusual to have to force precompilation to improve response times.
-
The time definite real time systems that I work on pretty much rule out anything that rely on JIT compilation or garbage collection. These tend to demand process responses well into the sub millisecond region, and event responses down to sub 10us and less, for example in my case digitally controlled SMPS and mixed signal RF.
If you are worried about such hard real-time systems, then you also have to be aware of all the effects of all the various caches knocking around. Best if they don't exist or are turned off.
-
The time definite real time systems that I work on pretty much rule out anything that rely on JIT compilation or garbage collection. These tend to demand process responses well into the sub millisecond region, and event responses down to sub 10us and less, for example in my case digitally controlled SMPS and mixed signal RF.
If you are worried about such hard real-time systems, then you also have to be aware of all the effects of all the various caches knocking around. Best if they don't exist or are turned off.
Indeed, and “it depends”. Randomly performing JITs and garbage collection is very different in magnitude terms compared to L1 cache (as opposed to a disk backed virtual memory).
An end user can usually be expected to wait for a couple of hundred milliseconds for a response. A control loop for a switch mode power supply not so much.
JIT latency is why Microsoft realised in the relatively early days of .NET that they needed to provide NGEN to precompile code. There’s probably a similar thing in Java, but I’m not a recent aficionado.
-
The time definite real time systems that I work on pretty much rule out anything that rely on JIT compilation or garbage collection. These tend to demand process responses well into the sub millisecond region, and event responses down to sub 10us and less, for example in my case digitally controlled SMPS and mixed signal RF.
If you are worried about such hard real-time systems, then you also have to be aware of all the effects of all the various caches knocking around. Best if they don't exist or are turned off.
Indeed, and “it depends”. Randomly performing JITs and garbage collection is very different in magnitude terms compared to L1 cache (as opposed to a disk backed virtual memory).
An end user can usually be expected to wait for a couple of hundred milliseconds for a response. A control loop for a switch mode power supply not so much.
JIT latency is why Microsoft realised in the relatively early days of .NET that they needed to provide NGEN to precompile code. There’s probably a similar thing in Java, but I’m not a recent aficionado.
Java relevant GCs (there are many :) ) are remarkably good for "soft" realtime system running on multicore machines - certainly good enough for telecom applications. They are an order of magnitude better than almost all the program-specific GCs reinvented poorly by people that only know C/C++ - for a start, the Java GCs work reliably!
Anybody that uses Java for hard realtime systms needs re-educating. Unfortunately so do too many young C/C++ programmers.
I looked at C# once, just before it was released, Anders Hejlsberg the C# designer came and gave us a talk about it. The overwhelming response was "proprietary Java-lookalike without the advantage of dynamic compilation and with the disadvantage of having 'unsafe' bits". Nobody bothered to do anything with it, as far as I know.
I've never had reason to change that opinion, just as I never bothered to learn Delphi.
-
What do you mean by "multidimensional" in this context? The two dimensions are "states" and "events" :)
It is often beneficial to split one large FSM into multiple smaller FSMs each with independent states and events between the smaller FSMs. But I wouldn't call that "multidimensional", I'd call it "good engineering taste" :)
I mean, if coming from a simple form, like a status only represented by a number (one dimension) and events that cause transition between states (jump on the number line, i would not call that a dimension), the transition itself takes some time, but there can only be one status active at any given time.
It then depends if the state machine is implemented in an absolute form (no memory of the last active state) or one that is relative to the last state it was in.
Imho only the latter form allows to add conditions that would lead to two mutually exclusive states (but based on the same event), you kind of add a layer on top of that and are not in a single dimension anymore.
You might be able to flatten it again, by extending the conditions to huge terms and segmenting the number line, which is often impractical and leads people to lose oversight and make errors.
-
I had forgotten what this discussion was about, since these refer to posts a week old. It would have helped if you included the context instead of removing it; this forum isn't stackexchange :)
Anyway, here's the full context:
It´s often that people don´t understand that their model just changed from one dimensional to multidimensional and try to compensate by adding a mess to the one dimensional state machine.
What do you mean by "multidimensional" in this context? The two dimensions are "states" and "events" :)
It is often beneficial to split one large FSM into multiple smaller FSMs each with independent states and events between the smaller FSMs. But I wouldn't call that "multidimensional", I'd call it "good engineering taste" :)
I mean, if coming from a simple form, like a status only represented by a number (one dimension) and events that cause transition between states (jump on the number line, i would not call that a dimension), the transition itself takes some time, but there can only be one status active at any given time.
Transitions are assumed to be instantaneous; if not then there is an intermediate state.
It then depends if the state machine is implemented in an absolute form (no memory of the last active state) or one that is relative to the last state it was in.
Imho only the latter form allows to add conditions that would lead to two mutually exclusive states (but based on the same event), you kind of add a layer on top of that and are not in a single dimension anymore.
You might be able to flatten it again, by extending the conditions to huge terms and segmenting the number line, which is often impractical and leads people to lose oversight and make errors.
That is either "spaghetti code" or some form of primitive neural network :) It isn't what is meant by a Finite State Machine!
That kind of nonsense can materialise if people are undisciplined. The best discipline is to represent the FSM in one of the many formal diagrams that have been designed over the decades, e.g. Harel StateCharts. Then the FSM can be translated, possibly automatically, into an executable language source code. XLSC. A decent executable language and use of design patterns will help prevent fools from directly modifying the XLSC in ways that are incompatible with a decent, predictable, comprehensible FSM.
But ultimately there is no way of making something foolproof, because fools are so damn ingenious.