Forums

Questions re Coding Efficiency

Started by MaxMaxfield 3 weeks ago18 replieslatest reply 3 weeks ago75 views

I just received an email from someone saying that his commercial coding experience started with a programmable calculator with 512 bytes of memory -- he wend on to say that for the purposes of efficiency, the sequence in which a set of 'if' statements is written should be based on expectation of occurrence. I'm assuming that we are talking about mutually exclusive tests here -- do you agree?

Also, now I come to think about it, I seem to recall reading somewhere that if the if() itself has multiple conditions like xxx AND yyy AND ZZZ and the first one fails *left-to-right), the code generated by the compiler doesn’t bother evaluating the rest -- similarly for xxx OR yyy OR zzz if the first one passes (left-to-right) the compiler doesn’t bother evaluating the rest -- is this true? If so, if you were trying for extreme efficiency, would you try to organize things so that the most common condition was tested first, or...?

Do you have any other efficiency-related points like this you'd care to share?

[ - ]
Reply by DKWatsonMarch 30, 2021

If you examine the asm created by the compiler you will recognize that multiple if/then, nested if and switch statements are executed sequentially and as such the first satisfied condition causes a jmp over the remaining tests. I wouldn't suggest that this makes code more efficient as it begs a definition for what is efficient, the amount of code remains the same unless the precompiler dumps conditions that will never be met. In embedded applications however, if there is some knowledge of likelihood, the conditions most likely to occur should be tested first as this will result in faster code.

[ - ]
Reply by MaxMaxfieldMarch 30, 2021
"In embedded applications however, if there is some knowledge of likelihood, the conditions most likely to occur should be tested first as this will result in faster code." Thanks for the feedback.
[ - ]
Reply by SpongeboBSineWaveMarch 30, 2021

These days where I usually have lots of flash for code, I try to optimize more for speed rather than size.

For something like a pile of "IF" or "CASE" statements, I will use function pointers so that the search for the proper case doesn't have to take time rippling down the list to find the right one.

I only do this when there are lots and lots of search possibilities.

If I was using a small processor with 512 bytes of code space, I would probably just write in assembler but not sure exactly how I would parse a bunch of IF statements.

What would others do ?  I suppose it totally depends on how complicated the code is.

[ - ]
Reply by MaxMaxfieldMarch 30, 2021
I love having lots of Flash and RAM ... but I also used to enjoy working within tight resource constraints.
[ - ]
Reply by mrfirmwareMarch 30, 2021

Then I recommend you try using https://godbolt.org/ and watching what if-else vs switch vs function pointers yields for your chosen compiler and optimization flags.

And to be clear, short circuit evaluation is most definitely run-time, not compile-time. I did not mean to imply the latter.

[ - ]
Reply by DilbertoMarch 30, 2021

Me too!     :-)

[ - ]
Reply by mrfirmwareMarch 30, 2021

I'd say don't worry about optimizing until you need to worry about optimizing. When you are out of code or data space then you need to worry about getting small. When you can't make your timing deadlines you need to worry about getting faster.

But, in general, there's no loss of readability in putting your known-to-be-more-common cases first in an if-else ladder or similarly with C short-circuit rules that you alluded to. I'm just not sure that's going to save you all that much time at run-time.

When things get really tight I usually start increasing the optimizer level and inspecting the assembler output. Maybe I can do slightly better coding directly in assembler if the optimizer isn't doing it for me. These are very rare situations that usually need to be done only when you're on a woefully under-spec'd CPU and have to get something working on it because that's the job.

[ - ]
Reply by MaxMaxfieldMarch 30, 2021

Hi there -- on the one hand I totally agree -- on the other hand, I'm trying to stay prepared in case I fall through a time-slip and find myself circa 1950 in which case I want to be at the top of my game so I can cash-in on what little I know LOL

[ - ]
Reply by DilbertoMarch 30, 2021

"That's my philosophy also"

[ - ]
Reply by CustomSargeMarch 30, 2021

Howdy, not certain "compiler" is right here. The compiler better evaluate / translate every possible path, since it isn't around at runtime. An interpreter probably does function this way. Classic "it was in the last place I looked" DUH - no I kept looking After I found it.

My projects are 90+% assembler - they're small and speed always seems to be a concern. That and I do stuff a compiler wouldn't allow.  G.H.  <<<)))

[ - ]
Reply by MaxMaxfieldMarch 30, 2021
I hadn't even thought about a compiler-interpreter twist on things -- thanks for sharing.
[ - ]
Reply by igendelMarch 30, 2021

Within a single if statement, most compilers will default to a "lazy evaluation" of the conditions - e.g. if the operator is an OR and the first (leftmost) condition evaluates to True, the second condition won't be evaluated at all because we already know the final outcome. There's usually a compiler directive you can set to determine this behavior if you have to.

With switch statements, it's more complex. A very very senior programmer once told me how his team tweaked and recompiled the C compiler itself to make sure it evaluated cases in the desired order. They did this to optimize a super time-sensitive high-speed network packet thingy. So it can matter, but it's not a generic all-purpose optimization.

[ - ]
Reply by dnjMarch 30, 2021

If you are asking about the "if" statement evaluating left to right in an single expression, you are correct. You can check the validity of a pointer (in C, for instance) and then check a value in the same expression.

if ((p != NULL) && (p->value == 8))

is valid. The first "false" discontinues the evaluation

Using OR || leads to the opposite - the first "true" allows acceptance

Some people shy away from "switch" statements (still in the C vernacular) and choose to use cascading "if" statements. Depends upon style, I guess. I like to use "switch" statements for finite state machines (use them all of the time) because they are more organized and easier to slip in a new state without worrying about where parentheses go.

Depending upon the situation, a completely different approach can result in a more elegant solution (always go for the elegant solution).

For instance, I had a situation where I was presented a raw value of some unit of measure. Let's say volume. So, it might be metric i.e., CC or Liter, or it might be imperial, i.e., ounce, teaspoon, tablespoon, cup, pint, quart, gallon. I needed to take that value and indicators of the current unit of measure and convert it to the other. I marveled that the code was written as a bunch of nested "if" statements. First a cascade of "if" statements to decide what the incoming units were and then a bunch of "if" statements of the required units inside of those. "Marveled" is not the right word. It was a lot more harsh than that. The elegant solution is to have a two dimension table of scale factors. Rows are indexed by the incoming units. Columns are indexed by the outgoing units. The code was a matter of multiplying the raw value by the scale factor from the table. That is coding efficiency. Looking past the brute force simple solution and being elegant. 

[ - ]
Reply by MaxMaxfieldMarch 30, 2021
"'Marveled' is not the right word..." LOL
[ - ]
Reply by RallygoerMarch 30, 2021

Maveled is that the lighting used for the eyes of a paranoid android??

Or would that be MarveLED

[ - ]
Reply by MaxMaxfieldMarch 30, 2021

I think MarvinLED for a paranoid android (https://en.wikipedia.org/wiki/Marvin_the_Paranoid_...)

[ - ]
Reply by KocsonyaMarch 30, 2021

At least in C and derived languages the && operator is specified to stop evaluating as soon as the first condition is false and similarly, the || operator does that after the first condition is true. That is not up to the compiler, it is specified in the language standard and has always been.

Now that is not true for & and | in an expression. For example:

bool test1( void ), test2( void );

if ( test1() & test2() ) { ... 

the compiler must call both functions (the order is not specified, though) because functions can have side effects and the compiler cannot just willy-nilly decide not to execute them. However, if the expression is something like this:

bool flag1, flag2;

if ( flag1 & flag2 ) { ...

the compiler can, if it wants to, skip the evaluation of flag2 if it finds flag1 to be 0 (or vice versa) because the end result is indistinguishable from actually carrying out the bitwise and-ing and test.


[ - ]
Reply by MaxMaxfieldMarch 31, 2021

Very interesting -- thanks for your feedback -- Max