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.
Bit blenders: Move bits around quite a bit
August 12, 2008Efficient 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
August 5, 2008Modern 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?