75. Code optimization

Optimization turns a working program into a better working program: faster, smaller or more economical. The key word is "working". Code that is not yet debugged is too early to optimize, and code that already meets its timing has no need for it.

On a microcontroller "better" more often means "smaller": Flash and RAM run out before time does. That is why this section starts with the compiler's optimization levels — and with the unexpected result that the "fast" level gives larger code than no optimization at all. Then comes what the compiler does by itself, how to help it, and why all of this pales next to the choice of algorithm.

Terms used in the documentation

Term	Meaning
bottleneck, hot spot	the part of the code where the time goes
profiler, flat profile	a tool that measures where time goes; a per-function time table
optimization level	how hard the compiler optimizes (-O0…-Oz)
loop unrolling	repeating the loop body to do fewer iterations
strength reduction	replacing an expensive operation with a cheap one
inlining	putting a function's body in place of its call
aliasing, restrict	two pointers to the same memory; a promise that this does not happen
lookup table	a table of precomputed values
code size, footprint	how much memory the code takes
premature optimization	optimizing before you know it is needed

75.1 When to optimize

The order is always the same:

1. The program works and is tested. Optimizing code that does not work means speeding up a bug.
2. A measurement showed that it does not fit — in time, in Flash or in RAM (section 73).
3. The bottleneck has been found. Almost always the time goes into a small part of the code, and guessing which part is useless — you measure it.
4. Algorithm first, everything else after it (75.7).
5. After every change, measure again and check correctness again.

If the code already keeps up, optimization is wasted time and more complicated code that someone will have to read later.

75.2 The profiler

A profiler answers the question of where the time goes. On a PC this is, for example, gprof: you build the program with the -pg option, run it, and gprof shows how much time each function got.

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
100.00      0.02     0.02        1    20.00    20.00  hot
  0.00      0.02     0.00        1     0.00     0.00  cold

The function hot got all the time, cold got nothing. It is hot that is worth optimizing, however many lines cold has.

On a chip the role of the profiler is played by a cycle counter over code regions and the RTOS per-task load statistics (section 35.3). The approach is the same: first understand where the time goes, then change something.

75.3 Compiler optimization levels

One and the same file — summing an array, copying, CRC-8, bubble sort — built with armclang at six levels:

The main finding: -O2 gave larger code than -O0, and 6.4 times larger than -Oz. It unrolls loops — instead of one addition per step it does four, to test the condition and branch less often. On a PC with a cache and gigabytes this pays off; on a chip with 64 KB of Flash it does not always.

What to choose:

And test at every level that will be used in production: a bug that appears only with optimization is almost always a missing volatile (section 3.4) or undefined behavior.

75.4 What the compiler does by itself

The compiler applies many "manual" optimization tricks without you:

Conclusions:

• there is no point in writing x >> 3 instead of x / 8 — the compiler does the same, and the code becomes less clear;
• signedness matters: signed division rounds toward zero (section 64.8), and negative numbers need a correction. If a number is never negative, declare it unsigned, and the division becomes one instruction;
• Cortex-M0 (the F0 series) has no hardware division: every a / b is a function call. In a hot loop on the F0, division is replaced with multiplication by the reciprocal or with a shift. On M3 and M4 the compiler already turns division by a constant into multiplication (section 69.9), but on M0 it lacks a multiply with a 64-bit result, so x / 10 there also becomes a call to __aeabi_uidiv. A power-of-two scale helps: then division is a shift.

More from what has already appeared in this handbook: a zeroing loop becomes a call to the library memclr (section 68.2), tail recursion becomes a loop (section 66.9), a short static inline function becomes inline code (section 71.11).

75.5 How to help the compiler

restrict is a promise that the pointers do not point to the same place:

int f(int *p, int *q)                   { *p = 1; *q = 2; return *p; }
int g(int *restrict p, int *restrict q) { *p = 1; *q = 2; return *p; }

In the first function the compiler must re-read *p from memory: what if q points to the same place, and writing the two changed *p. In the second it immediately returns one — there is no read. For buffer-processing functions, where the destination and the source are known to be different, this is a noticeable saving. But the promise must be true: if the pointers do coincide after all, the result is unpredictable.

A type the size of a register. The advice "use the smallest type", correct for 8-bit microcontrollers, does not work on ARM. The registers are 32-bit, and incrementing a uint8_t is an addition plus an extra uxtb instruction to cut the result down to a byte; for a uint32_t it is a single addition. In a loop the compiler often hides this difference by keeping the value in 32 bits, but for local variables and counters the natural choice on Cortex-M is uint32_t or int. Small types are needed where there are many of them: in arrays and structures, where they save RAM.

static on file-level functions lets the compiler inline a function or drop it if it is not needed. const on tables moves them to Flash (section 68.3). volatile only where it is needed: every access to a volatile the compiler must perform literally.

75.6 inline and the linking trap

inline int foo(void) { return 2; }
int main(void) { return foo(); }

With optimization this program builds: the call is inlined. Without optimization the linker stops — L6218E: Undefined symbol foo. By the rules of C, the word inline without static gives only an inline definition and does not create an ordinary function body to call. When the compiler without optimization decides not to inline, there is nothing to call.

The right way is static inline: it builds at any level. This is exactly how short functions in headers are written (section 71.11).

75.7 The algorithm matters most

The task: in an array every number occurs twice, and only one occurs once. Find it.

Head-on — for each element walk the whole array and look for its pair:

for (int i = 0; i < n; i++) {
    int dup = 0;
    for (int j = 0; j < n; j++)
        if (i != j && a[i] == a[j]) dup = 1;
    if (!dup) same = a[i];
}

With exclusive OR — one line: pairs cancel each other (x ^ x = 0), and the unpaired one remains.

for (int i = 0; i < n; i++) same ^= a[i];

For an array of 2001 elements: 4004001 comparisons versus 2001 operations — 2001 times less work. A measurement confirmed it: the second variant is faster by three orders of magnitude — roughly by the same factor as the reduction in operations. No optimization level and no rewriting of the first variant in registers will give that.

The second example is strlen in the loop condition:

for (size_t i = 0; i < strlen(s); i++) ...    /* strlen на каждом шаге */

Every check of the condition walks the whole string, and a loop over a string of 20000 characters takes about four hundred million steps instead of twenty thousand. The measurement: hundreds of times slower. The length is computed once before the loop.

The familiar techniques come from the same idea: iteration instead of double recursion (section 66.8), a table instead of computation — on a chip a const table spends no RAM at all — and walking a two-dimensional array by rows (section 68.7). How to evaluate algorithms in advance, without measuring, is in section 76.

75.8 Optimizing for memory

On a chip this is often more important than speed:

• the -Os or -Oz level — see the table in 75.3;
• all constant tables are const, so that they live in Flash (section 68.3);
• no printf("%f") — that is more than four kilobytes (section 74.4);
• microlib instead of the full library, if it is enough (sections 72.4 and 74.4);
• structure fields from largest to smallest (section 70.2), small types in large arrays;
• no heap: memory is allocated statically (section 72.4);
• for GCC, -ffunction-sections -fdata-sections at compile time and -Wl,--gc-sections at link time, otherwise unused functions stay in the firmware (section 77.5): the HAL UART example for the F103 from the STM32Cube package at -Os takes 16536 bytes of Flash without them, and 5864 with them;
• link-time optimization: -flto, for armclang together with the --lto option of armlink. The compiler sees the whole program at once, inlines functions across files and throws out what is not needed: the same example takes 4176 bytes instead of 5864, and with armclang it is a third smaller. Such code is harder to debug, so it is enabled in the release build, and then everything is tested again.

75.9 The cost of optimization

Optimized code is usually less clear. Therefore:

• comment why it is done this way — otherwise the next programmer will "fix" the strange code back;
• do not apply tricks everywhere, only in the bottleneck you have found;
• compare the cost: a day of work for forty milliseconds that nobody will notice is a bad deal. On a chip it sometimes happens that it is cheaper to take a part with more Flash or a higher clock than to squeeze the code for a week.

And finally: writing several statements on one line and removing spaces does not make a program faster. The compiler does not care.

75.10 Pitfalls

The firmware grew after turning on the "fast" optimization. -O2 unrolls loops; for size you need -Os or -Oz.

A function was sped up, but the program did not get faster. The function was not the bottleneck — profile first.

The code breaks only with optimization. A volatile is missing or there is undefined behavior.

x >> 3 instead of x / 8 "did not speed anything up". The compiler already makes a shift — for unsigned values.

Division in a loop on the F0 is slow. Cortex-M0 has no divide instruction.

Switched to uint8_t "for speed" and it got slower. On ARM small types need truncation to a byte.

With restrict the function returns garbage. The pointers did coincide after all: the promise was false.

Does not build without optimization: undefined symbol. inline without static.

A loop over a string is slow. strlen in the loop condition.

Optimized code was "fixed" back. There was no comment explaining why it is written that way.

75.11 Summary

• You optimize working code, after measuring, and only the bottleneck; a profiler shows where the time goes.
• -O2 unrolls loops: on one set of functions it gave 780 bytes versus 352 at -O0 and 122 at -Oz. On a chip, for size, use -Os or -Oz.
• The compiler itself turns multiplication and unsigned division by a power of two into shifts; signed division is more expensive; Cortex-M0 has no divide instruction.
• restrict removes extra reads if the promise is true.
• On ARM the natural type for local variables is 32-bit; uint8_t adds truncation.
• inline without static gives L6218E without optimization; write static inline.
• The algorithm decides the most: 4004001 comparisons versus 2001 XOR operations; strlen in the loop condition is hundreds of times slower.
• On a chip optimizing for memory is often more important than for speed.

Next: section 75а "A profiler on the chip itself: sampling the program counter by timer and through the DWT" — where the program spends its time, without markers in the code.