Close

Working at Etteplan

Embedded systems programmers need to think about implementation details

This entry will go yet one step deeper into what kind of challenges embedded systems programmers need to solve, offering a very practical example. The example dates back to a time 30 years ago and has not been valid for a long time now due to the development of processors, but nevertheless demonstrates what it means to write software for an environment where not only “what” but also “how” matters. It may sound extreme and distant, but there is something in it to generalize and to make a point in today’s world, too.

Most embedded systems programming is far from being as extreme as this example, and, on the other hand, this is not related to embedded systems only. This example is actually more related to driver programming, and drivers are an essential part of any computer system, not just of embedded systems. Every time a new technology is introduced that requires new hardware, there is need for writing driver code. Nevertheless, this is about the significance of implementation details, and embedded systems programmers need to think about them more often than many other programmers do.

 

Replacing multiplications with bit shifts

In 1987, long before HD as a graphics standard was even heard of, something called MCGA was introduced and became quite popular in some applications like games. It offered a resolution of 320x200 pixels, which is worse than TV before HD, but it made drawing graphics easier than many other standards back then did.

The picture seen on the screen was represented to programmers as an array of 64000 bytes, or integers that can have value 0-255, each value corresponding to some color. The first 320 bytes represented the first line of pixels on the screen, the next 320 bytes the second line and so on. Thus, to draw a pixel, the programmer would calculate its index with formula index = y * 320 + x and then set the byte at that index to a value corresponding to the color to draw with.

The idea was very simple, but it still left room for different implementations, and the most significant detail was the implementation for the multiplication y * 320. Back then, it was significantly faster for a processor to multiply a number by a power of two – 2, 4, 8 or 16 etc. – than by just any random number. That was because computers count in binary numbers. Just like it is easy for a human to multiply a number by a power of 10 by just adding a zero at the end of it or moving the comma to the right, it is easy for a computer to multiply by a power of two by what is called bit shifting. It is technically different from multiplication, but result is the same and back then, calculation was a lot faster.

Now, because 320 is the sum of 256 and 64, multiplying by 320 is the same as multiplying by both 256 and 64 and calculating the sum of those results. The formula index = (y * 256) + (y * 64) + x produces the same result as the earlier index = y * 320 + x. The difference, from the point of view of a programmer, is that 256 and 64 are both powers of two, while 320 is not. That was not an optimization yet, though. The last step was to replace the multiplications with corresponding bit shifts, which results in formula index = (y << 8) + (y << 6) + x. Bit shift by eight to left, marked in the formula by << 8, is the same as multiplication by 256, and a bit shift by six to left, marked by << 6, is the same as multiplication by 64.

 

Why bother with optimization?

Why is it worth the effort to think about details like this, then? For a single pixel, it probably wouldn’t be, but drawing anything useful on the screen and especially having something move on the screen means drawing a lot of pixels. And, when something needs to be repeated very frequently, it usually makes sense to optimize. When the hardware is constrained in resources, it makes even more sense. In the old days, using tricks like this was an absolute necessity. Nowadays, the tricks are different and using them is not that critical, but in certain tasks, efficient use of resources is still important and worth the effort.

The value of optimization is not always apparent to the user, though. Sometimes, the advantages can be seen indirectly, as in longer battery life or a user interface that reacts a little faster, making use of the device or the software a little smoother. That kind of improvements may need to be measured for them to be seen, but once they are made visible, seeing them worth the effort may become easier.

It is said that optimization without evidence of need to optimize is always bad. That is because optimization usually takes some effort, and in practical work it means that one should first just solve the actual problem and only think about the details of implementation if it’s really necessary. At least in embedded systems programming, there is, however, another point of view too, which suggests that programmer should be aware of what is possible with the resources available and what might not be. That awareness and taking actions according to it before the hard evidence is available can be seen as a kind of optimization, too. It may be that it’s not the first or the second solution the programmer comes up with that is good enough to be the first candidate for the final solution.

 

Adding value to clients and users

The point here was to highlight a kind of challenges that programmers need to solve. Solving challenges like this is not much about understanding the needs of the user or the client’s business. It is mostly about computer engineering and computer science.  That doesn’t mean that embedded system programmers don’t need to understand the user or the client, though.

It has been said that for programmers, there are puzzles and there are problems. Problems are those challenges that the user or the client apparently needs solved, and puzzles are those technical challenges that need to be solved to make solving the problems possible. The optimization challenge described here is clearly more a puzzle than a problem.

 

Author: Antti Gärding, Embedded Software Architect at Etteplan