The compiler will not save you

12Oct13

…at least not in an embedded environment.

There’s a commonly held myth in modern software development that compilers are smarter than people at optimising code for its eventual runtime environment. By extension there’s no point in writing efficient code, because your idea of efficient code might not actually be all that efficient, and any time spent on doing that is wasted because the compiler will know better. This post is about one of those times when that’s not true. Functionally identical code can end up compiling into very different binaries, and that can lead to significant differences in resource usage on the target environment. That might not matter on a PC with a multi core multi GHz CPU and many GB or RAM, but it can make the difference between working and not working in an embedded environment – the kind of environment that the Internet of Things is being built out of.

The back story

A couple of years ago I did a simple project with my kids to make little boards that would flash their names in morse code. It used the cheap ($4.30) and popular TI MSP430 LaunchPad development kit. The code to do the morse bits was fugly but it worked.

Some time later my friend Andy Bennett asked me why I’d coded the project the way I had. The honest answer was that I’d been pretty lazy and cut’n’pasted the whole thing together, but for good measure I threw in a comment that I thought it would be easy for the compiler to digest and turn into an efficient binary for the highly constrained target environment of a low end MSP430 chip.

I’m still not quite sure whether Andy set out to prove me right or wrong, but I’m impressed by the effort and rigour that he put into his subsequent investigations. Some time later he presented his findings at OSHUG #25 (pdf slides).

The (more elegant) alternatives

Andy created three additional versions of the morse code flasher program (I’ve put all four into this Github repo – EmbeddedMorse). I think anybody with the slightest sense of smell around code would argue that all three are better than my original (#2). #1 and #3 make much better use of C data structures, #3 has some clever bit mapping of morse characters, and #4 uses a switch statement instead of many extra functions.

If the myth of compiler omnipotence held true then all four examples would have compiled down into the same binary for the MSP430.

They didn’t – it turns out that the compiler can be led astray.

A quick detour into a limited memory map

The MSP430G2211 device that I used has 2kB of Flash and 128 Bytes of RAM – so anything that’s going to change at runtime (variables) needs to fit into that 128 Bytes and everything else can be accommodated in the more generous 2048 Bytes of Flash. The actual memory map for an MSP430 device (or any other microcontroller for that matter) is a bit more complex, due to memory mapped peripherals etc., but that matters less when it comes to squeezing some code in.

Memory sections of compiled programs

A compiler will generate binary code to fit into various different sections such as .text (machine instructions), .data (static data such as constants) and .bss (space for variables).

For the compiled program to fit onto the device then .bss must go inside 128 Bytes and .text and .data combined can’t exceed 2048 Bytes.

Here’s what the compiler actually produced

Example .text .data .rodata .bss
1 391 832 156 0
2 1122 0 0 0
3 422 26 44 0
4 844 0 796 0

The first notable thing is that they’re all different – the compiler hasn’t spotted that the code is functionally identical, and it’s compiled it into different shaped binaries.

The second notable thing is that they all should work – none of the code uses any .bss, so that tiny 128 Bytes of RAM shouldn’t be an issue.

The only one that does work is #2, and it’s pretty obvious why that is – the entire compiled output is .text, which can go into flash.

It’s less clear why the other three examples don’t work:

#1 – if .data goes into RAM rather than flash then it’s clearly going to break past the 128 Byte limit

#4 – if .rodata goes into RAM rather than flash (which it totally doesn’t need to) then it will also break the 128 Byte limit

#3 – even if the .data and .rodata go into RAM then it’s only 70 Bytes, so there are 58 Bytes left. In theory that should be plenty, but in practice… some further analysis needed to figure out why it breaks.

Conclusion

Compilers aren’t as smart as people make out. Functionally identical source code can lead to very different binaries, and that can matter a lot in a constrained environment.

I didn’t know any of this when I wrote my initial implementation, and it’s just good luck that I picked an approach that worked first time. If it hadn’t then I might have done battle with the compiler for some time, or I might have given up and found an easier platform to get it working on.



2 Responses to “The compiler will not save you”

  1. Thanks for writing this up Chris!

    When I first saw your morse flasher, I was pretty sure that you were right: I set out to see if I could make an interesting interview question out of it!

    For example 3, you’re right, it only takes 70 bytes of RAM which is well under the 128 that the micro appears to have. I think during the presentation I just waved my hands and said that this was tricky because RAM is also consumed by the runtime stack and so whether it actually worked would depend heavily on how deeply nested the functions were and how much data they passed around. For my 3W LED controller on ATTiny I’d started to have problems when I’d gotten to 70 of 128 bytes.

    Thanks again: it’s a great writeup!


  1. 1 Learning to Code | Chris Swan's Weblog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: