First Impression Fail

It is said that first impressions lasts forever. Well, I sure hope these first impressions won’t keep me from using Solaris in the future. So, yes, I decided to try out Solaris, and I downloaded the VMWare virtual machine images from Sun. First there’s the usual annoying questionnaire about who you are, what you do, why you want I to try Solaris. Everything short of my income and investment strategy.

So I download the file with what seems to have the biggest version number, but it turns out that’s only the second half of the virtual machine. And it’s a stupid tar bomb. OK, I reread the thing, and there’s no clear, visible indications that there are two parts to the tar ball and that I should download the two. Never mind that, bandwidth’s is cheap.

UEID: Unique Enough IDs

Generating unique, unambiguous, IDs for data is something we do often, but we do not always know what level of uniqueness is really needed. In some cases, we want to be really sure that two instances of the same ID identify two copies of the same object or data. In other cases, we only want to be reasonably sure. In other cases, yet, we just assume that collisions—two different objects yielding the same ID—are very unlikely, and, if the need be, we can proceed to further testing to establish equality.

There are many ways of generating IDs, each with varying levels of confidence on uniqueness and differing applications.

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?