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?