The Right Tool

On his blog, Occasionally Sane, my friend Gnuvince tries to make a case for Python as a first programming language. He presents Python with a series of bullets, each giving a reason why Python is a good choice. While I think it may be a good choice pedagogically, it may not be a good pragmatic choice when someone is learning a programming language to find a job, as one of his reader commented.

But I think that betting on a sole language to base a programming career on is about as silly as someone mastering only the hammer looking for a construction job. His limited skills might not permit him to find a job, and even if he finds one, he may be confined to menial, unchallenging tasks. To push the tool analogy further, another workman that masters a wide array of tools will probably be more solicited and appreciated in his work-group, and be lead to more and more complex tasks, and more responsibilities within his group. Programming is very much the same: sometimes, it just takes something else than a hammer, and the right guy for the job is the guy that has the largest toolbox—the one with the Torx screwdriver set.

Optimizing boolean expressions for speed.

Minimizing boolean expressions is of great pragmatic importance. In hardware, it is used to reduce the number of transistors in microprocessors. In software, it is used to speed up computations. If you have a complex expression you want to minimize and look up a textbook on discrete mathematics, you will usually find a list of boolean laws and identities that you are supposed to use to minimize functions.

Debouncing using Binary Finite Impulse Reponse Filter

In digital systems, we expect input signals to be noise free, but that is not always realistic. For example, let us think about an embedded device with a series of push buttons. The user interacts with the device by pressing the buttons, and we would expect, quite naively, that the micro-controller receives either one or zero depending on whether the button is pressed or not.

However, when the user presses a button, there is a short time during which the micro-controller cannot tell for sure whether the button is pressed or not. During this short time, the mechanical switch under the button establishes the contact and (electronic) noise is read. To the micro-controller, this noise appears as a short burst of random ones and zeroes between the button-not-pressed state (or zero) and the button-is-quite-pressed state (or one). The micro-controller has to decide through that burst of random bits when—and if—the button is pressed. The same thing occurs when the button is released.

The noise from the contact is usually somewhat smoothed by a small capacitor-based circuit called a debouncer. The debouncer makes sure that the signal rises smoothly from 0 (not pressed) to 1 (pressed). But even with a debouncing circuit, the signal must go through a phase where its level isn’t quite zero nor quite one, and the micro-controller’s I/O port may read either levels; resulting in multiple, rapid contacts instead of a single, longer, contiguous contact. Naturally, this situation must be avoided; if not by hardware, by software.

Bit blenders: Move bits around quite a bit

Efficient bit manipulation is often found at the lower levels of many applications, let it be data compression, game programming, graphics manipulations, embedded control, or even efficient data representations, including databases bitmaps and indexes.

In some cases, one might rely on the often limited features of one’s favorite language—C++ in my case—to manipulate bits. In C++ (and in C), there are bit-fields that allow you to define how a piece of memory will be chopped up in regions each having a specific number of bits. Bit-fields can bring you only so far as to describe how bits are mapped onto a chunk of memory; they are of little or no help when you need to efficiently move bits around in a somewhat complicated fashion.

Branchless Equivalents of Simple Functions

Modern processors are equipped with sophisticated branch prediction algorithms (the Pentium family, for example, can predict a vast array of patterns of jumps taken/not taken) but if they, for some reason, mispredict the next jump, the performance can take quite a hit. Branching to an unexpected location means flushing the pipelines, prefetching new instructions, etc, leading to a stall that lasts for many tens of cycles. In order to avoid such dreadful stalls, one can use a branchless equivalent, that is, a code transformed to remove the if-then-elses and therefore jump prediction uncertainties.

Let us start by a simple function, the integer abs( ) function. abs, for absolute value, returns… well, the absolute value of its argument. A straightforward implementation of abs( ) in the C programming language could be

inline unsigned int abs(int x)
 {
  return (x<0) ? -x : x;
 }

Which is simple enough but contains a hidden if-then-else. As the argument, x, isn’t all that likely to follow a pattern that the branch prediction unit can detect, the simple function becomes potentially costly as the jump will be mispredicted quite often. How can we remove the if-then-else, then?