3
\$\begingroup\$

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.

\$\endgroup\$
  • 6
    \$\begingroup\$ If this is on a 8 bit machine, why deliberately force J to be a 16 bit integer when it's only going to count from 0 to 7? \$\endgroup\$ – Olin Lathrop Nov 22 '13 at 21:45
  • 5
    \$\begingroup\$ Have you profiled it to see if you actually need to optimize it? \$\endgroup\$ – Renan Nov 22 '13 at 22:01
  • 6
    \$\begingroup\$ Microcontrollers usually include an instruction that decrements and jumps if equal/different than zero. Incrementing and comparing to a constant or variable involves at least one more instruction per loop. So, as a general good practice in terms of timing, make loops that use a counter that decrements to zero when finished. \$\endgroup\$ – apalopohapa Nov 22 '13 at 22:12
  • \$\begingroup\$ The only reason I wrote this is because I gave advice in another thread which I wanted to prove was worthwhile in some limited circumstances. \$\endgroup\$ – David Nov 22 '13 at 22:12
  • \$\begingroup\$ @OlinLathrop interesting point, I wonder if either XC8 or GCC spotted that and optimised it. That should be an easy catch for the compiler. \$\endgroup\$ – David Nov 22 '13 at 22:17
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Buffer CRC routines can often a bottleneck on 8-bit micros, even when written optimally. Further, an many 8-bit micros something like the quoted code is probably many slower than would be optimal code. For many purposes, C code can get close enough to assembly to not be worth further optimization, but certain kinds of loop constructs require optimizations no compiler I know of can possibly make. \$\endgroup\$ – supercat Nov 22 '13 at 22:14
  • 1
    \$\begingroup\$ To Brick's point. "[...] premature optimization is the root of all evil" per Donald Knuth. \$\endgroup\$ – Nick Alexeev Nov 22 '13 at 22:19
  • 2
    \$\begingroup\$ I really hate how far people take that Knuth comment. You should at least pay attention while you're writing code to make it reasonably efficient to start with. People quote Knuth as an excuse for their sloppy code, and get all righteous about it too. You should develop good programming practices that help you right good code. I'm not saying to disassemble and pipeline analyze everything... but as @supercat says if you're at all paying attention to your problem you would likely realize how much work your CRC algorithm is going to do. In many situations it will absolutely matter. \$\endgroup\$ – darron Nov 22 '13 at 23:01
  • \$\begingroup\$ a CRC routine on an 8 bit processor might not need to be efficient at all, or it could be absolutely critical. Without more specifics, this is NOT a good example for the OP's "generic proof" for or against optimizing it. \$\endgroup\$ – darron Nov 22 '13 at 23:03
  • 4
    \$\begingroup\$ @darron: I interpret Knuth's statement as "Optimizing before one knows where it's needed will often lead to wasting time optimizing things that don't matter rather than things [not necessarily just performance] that do. I don't think profiling is always needed; when picking between a simple O(N^3) algorithm or a complex O(NlgN) one, for example, knowing that N might reach 1000 would be a pretty strong argument against the former even without profiling, and knowing that N would seldom exceed 3 and never exceed 5 would be a strong argument against the latter. \$\endgroup\$ – supercat Nov 22 '13 at 23:23
3
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ You can optimize for other things than just speed or size. Optimizing for power efficiency is another popular option, but response time or response time consistency are others as well. \$\endgroup\$ – akohlsmith Nov 23 '13 at 6:19
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.