Should I refactor my C code to optimise it for an embedded microcontroller?

Question

Below is some code implemented on an 8 bit microcontroller.

The following comment was posted to another question:

As your code doesn't use the i variable, why not just while(length--) instead of the first for loop?

It suggests changing the for(..) loop for a while(..), will this make any practical difference to how optimised the code is for an embedded microcontroller?

uint32_t MyFunction(uint32_t crc, uint8_t *buffer, uint16_t length) {
    for (uint16_t i=0; i < length; i++) { 
        crc = crc ^ *buffer++; 

        for (uint16_t j=0; j < 8; j++) { 
           if (crc & 1) 
              crc = (crc >> 1) ^ 0xEDB88320; 
           else 
              crc = crc >> 1; 
        } 
    } 

   return crc; 
}

Note: I wrote this question and answered it myself after posting a comment earlier this week. That comment was upvoted but I felt I should back it up with some actual testing. Other answers would be useful, but this was intended as generic proof of a point rather than a specific question about the algorithm.

Answer 1

The classic three rules of optimization:

1. don't.
2. don't yet.
3. profile before optimizing.

It doesn't hurt to write clean tidy code in the first place but premature optimization is a waste of time and effort that could more fruitfully be spent elsewhere.

Answer 2

The first thing to consider is what needs optimising. Does the code need to take less program memory or should it run faster? Sometimes these things can both be achieved by reducing the number of instructions, however this depends on the underlying microcontroller and the number of cycles each instruction takes.

It is completely possible to generate smaller code that takes more cycles to run, especially if branches are involved.

To start experimenting it is important to isolate the smallest code portion possible. I created the simple test case below which includes the function from the question and which is portable between different microcontroller families:

#include <stdint.h>

uint32_t MyFunction(uint32_t crc, uint8_t *buffer, uint16_t length) {
    uint16_t i;
    uint16_t j;

    for (i = 0; i < length; i++) {
        crc = crc ^ *buffer++;

        for (j = 0; j < 8; j++) {
           if (crc & 1) 
              crc = (crc >> 1) ^ 0xEDB88320; 
           else 
              crc = crc >> 1;
        }
    }

   return crc;
}

int main(int argc, char** argv) {
    uint8_t data[] = "ABCDEF";
    uint32_t ret = 0;
    ret = MyFunction(ret, data, 6);
    while(1);
}

As noted in the comments on the other question the value of the variable i is never directly used, it is only ever compared to length. Therefore we could rewrite it as follows:

uint32_t MyFunction(uint32_t crc, uint8_t *buffer, uint16_t length) {
    uint16_t j;

    while (length--) {
      // .. do work ..
    }
    return crc;
}

For comparison purposes I used avr-gcc version 4.7.2 (targeting atmega8) and Microchip's XC8 1.21 (targeting PIC 18F). For XC8 I enabled PRO optimisations, for avr-gcc the arguments given were: avr-gcc -g -c -Os -Wall -mmcu=atmega8 test.c -o test-Os.

Note it is important to check that ret is not optimised away because the compiler thinks it is unused. Both variations on the C code generate the same assembly from avr-gcc. However XC8 does not notice the unused variable, therefore the code using a while(..) loop compiles to 4 bytes smaller with 2 RAM bytes saved.

As noted in a comment on this question it would also be more efficient to make j a uint8_t, as the input will never be more than 8 bits wide. Testing on XC8 shows that making this change saves another 8 bytes of program space and 1 byte of RAM. It also reduces the output generated with avr-gcc by 4 bytes and one register byte.

In conclusion it is always worth giving the compiler the best chance of generating good code, in this case by not using extra unnecessary variables and by using the smallest possible storage class. Some optimising compilers will cope better than others but both perform well if the input C code has been well thought through.

Answer 3

This sort of thing can on many processors be rewritten in a small assembly language routine that will run much faster than any possible C implementation. On a PIC, for example, the CRC calculation could be written using 72 instructions if _crc is in the currently-selected bank (code for 16F-series PICs)

    movf  _crc+1,w
    btfss _crc,0
     xorlw   0xNN  ; Would need to figure out proper value
    btfss _crc,1
     xorlw   0xNN  ; Would need to figure out proper value
    .. six more such instruction pairs
    movwf btemp+0  ; LSB of return
    movf  _crc+2,w
    btfss _crc,0
     xorlw   0xNN  ; Would need to figure out proper value
    btfss _crc,1
     xorlw   0xNN  ; Would need to figure out proper value
    .. six more such instruction pairs
    movwf btemp+1 ; Next byte of return
    movf  _crc+3,w
    .. eight more instruction pairs
    movwf btemp+2,w
    movlw 0
    .. eight more instruction pairs
    movwf btemp+3

Not the most compact thing in the world, but it would update the CRC32 for an incoming byte in 72 cycles. Alternatively, if one were using an 18F series part and could spare the code space, one could use 1Kbyte worth of tables (organized as four page-aligned 256-byte pieces). Code would then be something like:

    movf  _crc,w,b
    movwf _TBLPTRL,c
    movlw TabUpperAddress
    movwf _TBLPTRU,c
    movlw TabHighAddress
    movwf _TBLPTRH,c
    tblrd *
    movff _TABLAT,btemp+3
    incf  _TBLPTRH,c
    tblrd *
    xorwf _crc+1,w,b
    movff _TABLAT,btemp+0
    incf  _TBLPTRH,c
    tblrd *
    xorwf _crc+2,w,b
    movff _TABLAT,btemp+1
    incf  _TBLPTRH,c
    tblrd *
    xorwf _crc+3,w,b
    movff _TABLAT,btemp+2

A fair bit faster, but it would require 1Kbytes worth of data tables in addition to the code itself.