Jeffrey Nonken's Bare Metal Blog

Thanks for all the nice comments about my last post. It’s really gratifying to get so much praise so early.

I wanted to add a few thoughts. Kermit Derren says:

I was studying something else about this on another blog… Your position on it is diametrically contradicted to what I read earlier.

He’s not criticizing me, I left out some context, go back and read the whole comment. For that matter, neither am I criticizing him. It’s just that his comment made me think a little. I can’t comment directly on the other blog, not having read it (he didn’t provide a link). I want to emphasize that it’s possible that the other blogger is right, and that I’m also right, because what your priorities are depends very much on the situation.

My aforementioned former colleague who saved two bytes wasn’t so much misguided as he was just blindly following what he’d learned early in his career. He used to work in an industry where the resources were so thin and the timing so critical that the people who wrote the code knew every detail about every operation by heart, including all affected flags, any side-effects, and how many cycles they took to run. If there were any undocumented features they doubtless knew about those as well and used them. To these people finding two extra bytes was like discovering a new seam in what they thought was a played-out mine.

I’ve never lived in that world myself, though I’ve been closer than I am now. When you’re working in sub-1K memory space your priorities are different, believe me. So while I don’t know what the blog entry actually said, I’m willing to believe that an apparent disagreement might be due to a contextual difference. Then again, maybe he really believes that saving resources is a higher priority than writing clear, maintainable code in all circumstances. Until and unless Kermit shares the link I’m reduced to guesses.

Now… since I wrote “Optimize This!” I’ve watched my own habits more closely. I’ve found myself doing the very thing I’ve criticized — re-using variables with more of a thought to saving RAM (that I usually don’t need to save) than to program clarity. When I catch myself doing that of course I immediately repent and fix the problem. Hopefully I’ll break that habit soon and instill some better habits.

We are all of us hypocrites to some degree, and I am no exception, but I like to try not to be when I can help it.

A few days ago I had a programming situation where I had three conditions, each of which would cause a behavior (send a message) but were mutually exclusive (I can only send one at a time). I assigned each flag as a bit in a byte, with the higher priority as the higher value bit. Working in assembly there are a couple ways to do this:

• An if-then-else that tests each bit and decides whether to execute the associated code.
• A jump table that depends on the value of the byte. It will of course double in size each time I add a bit.

For only three flags I had eight values, so I made it a jump table. Jump tables are pretty fast. Then I discovered two more conditions, which meant that now I had thirty-two possible combinations that started to make the jump table look a bit daunting to create and maintain.

My first reaction was to make two jump tables and therefore two decisions, to keep the ROM usage down. Then I remembered my post and stopped to actually evaluate my situation. Once I thought it through the answer was obvious. I was using about 1/4 of my total ROM so far in a project that was mostly written. 48 extra bytes (two per jump) wasn’t going to make a dent in that, it was easier to maintain a single table than two tables plus glue logic, and it would take exactly the same number of execution cycles to deal with a 32-jump table as an 8-jump table. Instead of, say, three times as many cycles, if not more, if both tables were executed. As far as generating the table goes, well, I put it together using one of my favorite tools — Excel (or an open source alternative — usually Open Office or Gnumeric). This made generating redundant entries (and counting them) and re-arranging priorities much simpler to do without making mistakes (once I had the equations fine-tuned, of course).

Of course writing the Excel equations can take more time than just writing the bloody thing by hand, but it’s less tedious and, as I mentioned, less prone to making mistakes — especially when I change things around, because if I design the spreadsheet well enough, I can change things around and the table just automatically gets fixed.

In any case, I was much happier with the result.

I really like using a spreadsheet for generating (and sometimes maintaining) lists of things. You can, for example, generate the lookup table for a curve, including DB (Define Byte) statements and tabs and comments if need be, in Excel and then copy/paste the result directly into your source code. If you make a change it just re-calculates and you just copy/paste again. Excel has some nice table lookup functions too, string manipulation, and decimal/hex conversion. You don’t really need to be an expert — learn a few tricks and you’re halfway there. I depend a lot on the built-in help and on web searches when I’m trying to learn a new feature, but none of it is difficult. Read this article by Joel Spolsky called “The Process of Designing a Product”. About halfway down he talks about discovering that people mostly use Excel to keep lists. It’s certainly true in my case, and I’m glad they focused on that functionality as a result.

“And what do you really do?” said Tiffany.

The thin witch hesitated for a moment, and then:

“We look to… the edges,” said Mistress Weatherwax. “There’re a lot of edges, more than people know. Between life and death, this world and the next, night and day, right and wrong… an’ they need watchin’. We watch ‘em, we guard the sum of things.”

We programmers need to watch the edges, too. Different edges, perhaps, but nevertheless there’re a lot of edges, more than people know.

Back in the ’90s I was administrating a backup system with about 180 client computers. One day it started going wonky. (I don’t remember in what fashion.) I couldn’t figure out why, so naturally I called tech support.

After I described the problem, the support tech said, “What did you change?” I didn’t change anything. “You must have changed something, it was working before and it’s not working now. What have you changed in the last few days?” Certainly the code didn’t change, and it obviously worked, so the fault must lie in the customer. He was very insistent and barely polite.

We did not solve the problem during that phone call.

Two days later an upgrade came out. It seems that when the catalog file grew over 2GB it started having problems. The upgrade fixed that problem. (I don’t remember, but I’ll bet it extended it to 4GB. If you run the numbers I think you’ll find that 2GB is exactly the same as the highest value you can fit into a signed 32-bit integer. What a coincidence!)

What did I change in those few days? Depends on your point of view; all I changed was the amount of data in the catalog, and that was by running the system exactly as I had been. Really I didn’t change anything, but things did change, and the program simply couldn’t keep up.

It’s a perfect illustration of edge conditions that we all should watch. Can the index overflow a word? Will the size of that value really, really work for all eternity, or just for the foreseeable future? Watch out for statements like “Nobody will EVER fill that up!” I heard that in 1982 about 5 megabyte hard drives. Nobody will ever fill that up. Heh. Now you can buy 5 terabytes for a few hundred dollars and carry it around in a couple decent-sized coat pockets. It won’t be long before you can buy it in a single drive for under $100. And nobody with any sense will tell you that you’ll never fill it up.

One very typical programming error is called an off-by-one error, which usually happens when you’re working with zero-based indexes and one-based sizes and lose track of which is which. You can consider this a kind of edge condition; it certainly causes edge-condition-type errors. You can easily copy one too few or one too many items, or simply index past the end of your data. By one. Or never quite reach it. By one.

It’s easy to find those edges in small embedded systems where you typically use as small a variable as you can get away with. I use single-byte words all the time. How often do I use 32-bit integers? Pretty gosh darn seldom. But 32-bit signed integers are the default for the C++ compiler I use for PC programming. It’s actually more efficient to let it default to 32-bit integers than to use bytes, because the native word on the Pentium-class processor is 32 bits. Using anything smaller just makes the system work harder, and it will probably allocate 32 bits anyway because it wants things to align nicely. You probably have to tell it to pack your structs if you want to use them outside the program.

It’s enough to make an 8-bit processor guy cry (for envy) into his special sheep liniment.

What really tends to sneak up to you, though, and bite you on the backside is when you convert or calculate or otherwise change from one word size to another. This happens often when you try to have two different sized systems talking to each other, though of course it can also happen within your small system. It also happens when you get sloppy programmers writing code that uses the minimum needed (but different) size for each variable and then willy-nilly does calculations and copies and indexes back-and-forth without even bothering to cast anything. Of course this guy uses a low warning level when he compiles. And then he leaves the job and you’re left trying to figure out why the code is so buggy. Or rather, why it’s buggy is obvious, but you have to find and kill the bugs.

My current job is all about PC-based flight simulator software exchanging data with simulator hardware that’s based on 8-bit micros. Fortunately most of the actual data are flowing from the hardware to the flight sim software; most of the time the data are going from 10 bits to floating point, and the probability of messing up the scaling is much, much higher than the possibility of losing your high bits.

On the other hand, some of the controls don’t use the full range of the sensors and so must be calibrated. Since the sensor in this case is probably a cheap potentiometer, the wires pick up noise, there’s noise on the power supply, noise introduced by the multiplexers, and noise in the A/D conversion, the value tends to jump around a little. So even the most careful calibration won’t guarantee that the incoming value will never exceed my calibrated limits unless I’m really fanatical or add some padding. Which I don’t really want to do  in this case.

What’s that all mean? It means the incoming data will probably exceed my edges, eventually. In this case I simply check the value against the end-points, and if it’s out of range I rail it.

But I do check.

“But there’s magic, too. You’ll pick that up. It don’t take much intelligence, otherwise wizards wouldn’t be able to do it.”

It’s not enough to be a wizard. You need to be a witch, and look to the edges.

Mostly when I write code these days I write in assembly language on 8-bit systems. And I like it. That’s how sick I am.

I was working on a project and needed a small function written. I knew what it needed to do, but I wasn’t sure how to do it. My colleague did know how to do it, so I asked him to write it for me, figuring it would be easier to wrap my head around something I could see, and it would get done more quickly this way.

This (now former) colleague used to write gaming software and firmware. We’re not talking PS3 or XBox here, we’re talking the old stuff, a couple K (if that) of ROM and a handful of bytes of RAM with no performance to speak of animating games on video. These guys used to know not only every instruction of the CPU but the number of bytes and number of cycles every instruction took, what flags were affected for every operation, and so on. They practically lived inside the machines. I don’t know if he himself was that intense but he was at least very close, and worked with the guys who were.

So I got the function back and started studying it. The first thing I asked was, “What is ‘cs’?” cs was the name of a two-byte checksum used in virtually all our code (most projects were similar, so derived from each other). He was using cs and cs+1 in several places. “It’s a counter,” he said, “obviously” he didn’t quite say. “cs is a checksum. Why use that instead of creating a new variable?” “Well, it saved two bytes.”

I was incredulous. “Colleague,” said I, “this part has 256 bytes of RAM and we’re using about 120, less than half. Why on Earth did you need to save two bytes?”

He didn’t really have an answer. He’d never bothered to check; saving two bytes was as automatic as breathing to him. When I write code I ask myself, ‘Will this work, is it maintainable, what comments should I add, how should I name the labels, how does it fit in with the rest of the code, is it efficient’, stuff like that. When he writes code the only question he asks is ‘Can I save two bytes?’

Re-using variables that are out-of-scope is a time-honored tradition, necessary when your resources are extremely scarce, and fraught with danger. It is far too easy to think a variable is being used in two disjoint scopes when in fact the scopes overlap in unexpected ways. Doing it when it’s required is a necessary evil. Doing it when you have mostly-finished code that’s using less than half the RAM is inexcusable.

But that wasn’t his only crime. In assembler it’s very easy to attach multiple labels to the same address. Yes, part of the problem was re-using variables when it wasn’t necessary. But another part was using variable names that made no sense. To him, maintainable code is code he wrote. He knows how it works, therefore it’s obvious how it works, therefore it’s maintainable. But when I started to study the code I saw “cs” and thought “checksum” because that’s what that variable was. Even when I knew it was a counter it was hard for me to shift paradigms. What was worse was that he was using both bytes of cs as two different counters in that code, and they both had the same label with a different offset. Even given his passion for saving two bytes he should have added new label names to those bytes and used the related labels. (And added a comment that he was re-using cs.)

I created two appropriately-named variables and altered the code accordingly. Suddenly the code was quite simple to understand, given that I already knew what it was supposed to do. It went from opaque to clear that easily.

Books like Code Complete will point out that optimizing first is counter-productive. And they have a point.

• When you’re writing the code, you don’t really know where the bottlnecks are. Oh, you can make an educated guess, but it’s amazing how often those guesses are completely off the mark.
• It’s more important to get the code working first. Optimizing bad code just means it will be wrong with fewer resources, except the time you spent optimizing it. Now you have to fix the code, and chances are it will break the optimization you’ve performed. It may even get thrown out. And it’s even possible that you broke it by optimizing it!
• Any programmer with experience will know that a lot of their code will be radically changed or even thrown out before the project is finished. Even if it works perfectly as written, what’s needed may change.

So the lesson is: get it working first. Optimize later.

Which is great advice. But what if you’re working on a tiny processor with few resources? If the code doesn’t fit, it doesn’t matter if it’s right. It can’t work!

This is one of the places where general programming advice doesn’t quite fit in the embedded world. Mind you, it’s not wrong. It’s just not quite the black-and-white area it is when you have a PC with virtually unlimited resources.

So when you’re writing code for small processors you get into certain habits. Despite my outrage at my colleague’s mindless need to save resources we quite positively had more than enough of, I do understand it. It’s just that it should not have been mindless. He should have stopped to consider: I can save two bytes here. But do I need to? Should I? The answer being a resounding NO this time. …And had we been tight on RAM, then it might have been worth doing.

It’s a constant background hum, thinking about where to save a byte or two, what is the fastest way to do this, can I re-use the common part of this code by jumping into the middle, and so on. And sometimes I run out of something and have to optimize or find another way to do it.

There’s a funny psychological twist to that, too. I’ll be going along, resisting temptation to optimize as I write, and then run out of ROM. Then I’ll have to spend time optimizing so it will fit — and I’ll resent that time spent, feeling bitter about not having done the optimization in the first place, and if I had, see? I wouldn’t have to do this — completely forgetting the fact that I’m now only using time I’d previously saved by not optimizing prematurely.

Do I have any specific advice? I’m not really sure I do. The balance depends on a lot of factors, not the least of which is how much room do you have vs. how big is the project? Mostly I would be inclined to repeat what I’ve already said, some of which is really just channeling folks with more experience than I. Don’t automatically optimize from the start. Try to keep the code elegant. Think about it as you go, keep it in the back of your mind. Don’t be afraid to throw code away. Don’t be afraid to go back and tighten up or re-write code.  Accept that if you can’t optimize the code to fit, maybe there just isn’t room for the functionality. Or maybe there is using the old techniques, but is it worth making code that’s impossible to maintain?

Generally the highest cost in software development is maintenance. Spend a bit of time up front to make the code clean and elegant and you’ll save time down the road.

Don’t save two bytes at the cost of clarity and robustness just because you can.