Powers of minus one and some bit twiddling

Since the start of this year I'm employed as a postdoc on a project for designing a new domain specific language for writing dsp algorithms. The language is called Feldspar and if you want to check it out you can look at the official homepage or download it from hackage. As you can see on these pages Feldspar is a collaboration between Chalmers (where I'm employed), Ericsson and Elte University in Budapest.

There are two main goals for the design of Feldspar: first of all it should be possible to program at a very high level, close to how dsp algorithms are normally specified. Secondly, the generated code needs to be very efficient as the kind of applications that Ericsson has for dsp applications are performance critical.

I'm involved in various parts of Feldspar but one particular thing on my plate is making sure that the generated code is fast.

Recently the language has been used in a pilot project within Ericsson to implement part of the 3gpp standard (a mobile broadband standard, unsurprisingly, given Ericssons involvement). Having people using the language is tremendously useful for us language implementors as we really get a chance to see how well the language works in its intended environment.

The Feldspar code that was written in this pilot project was kept very close to the standard and was very similar to the mathematical specification of the algorithms. It's a very nice feature of Feldspar that this is possible, but it poses a challenge for us language implementers. While eyeballing some of the code I notice a little piece of code that I would like to discuss a little:

(-1) ^ v30

Just to clarify, in Feldspar this means minus one to the power of v30 and it has nothing to do with xor. v30 is just a variable name.

Powers of minus one is a common idiom in mathematics for saying that a value should change sign. If the exponent is even the result will be positive and if the exponent is odd the result is negative. This kind of thing is useful in various places and apparently also in the 3gpp standard.

However, actually performing exponentiation would in this case be ridiculously inefficient. But the question is what kind of code we should generate for this? Currently our compiler generates C so the code examples I will show from here on will be written in C.

Remember what I wrote above that the result only depends on whether the exponent is even or not. That is very easy to check, it's just the least significant bit! So we might generate the following code (assuming that the exponent is v30 as in the example above):

v30 & 1 ? -1 : 1;

This is very short and nice and most likely as good as we can hope for, at least for the kind of processors we are targeting.

However, I started programming in the 80's and I still instinctively flinch when I see branches in performance critical code. So I got curious to see if I could write the above as straight line code.

A straight line code solution which computes the above function would most likely involve some bit twiddling. I spent some time trying to come up with a solution on my own but wasn't very happy with what I managed to produce. I was aiming for a three instruction solution and my solutions were nowhere near that. So I decided to look around, maybe someone else had solved the problem before me.

Bit Twiddling Hacks to the rescue! This wonderful list of various bit twiddling tricks doesn't have anything which solves my particular problem but there is one little nugget which is close enough that I could make good use of it: "Conditionally negate a value without branching". The value that we will be negating is 1, we want to negate it depending on the least significant bit of our input value (v30 in our example above). I will not reproduce the code from Bit Twiddling Hacks, you can check it out yourself via the link. Instead I'm just going to present the final result of using that code on my particular problem (using C code):

int v; //The exponent
int r; //Will contain -1 to the power of 
int isOdd = v & 1; //Is the exponent odd?
r = (1 ^ (-isOdd)) + isOdd;

This is a fairly clever piece of code and I'm quite happy with it. However, it will compile to four instructions on typical architectures and I was really hoping for a three instruction solution. Anyone out there who knows of a shorter solution?

Using Stow

Stow

Sometimes I've found myself in the position where I would like to have access to several versions of the same programs. Maybe not all at once but at least a convenient way to switch between versions. Especially as a developer this need comes up every now and then, for instance trying to compile a piece of source code with several different versions of a compiler.

In the past when I wanted to try out an alternative version of a program I installed it in a temporary directory and ran it from there. It works but it's not terribly convenient. One has to be very careful to always specify the correct path, or chaos ensues.

So a while ago I started looking for a saner solution. This is where I came upon stow, a little command line tool for switching between different versions of the same program. I've found it quite useful, it's simple but does it the job.

However, I use stow with very irregular intervals and sometimes I forget some detail about how it works. The natural thing then is to turn to the stow manual. Unfortunately, the stow manual is not the most helpful of documents. It describes in some detail what stow does to the file system when it is invoked. While this is good to know if you want to implement your own version of stow it leaves you to infer yourself how to invoke it if you're an ordinary user.

Therefor I've written down some notes on how stow works. These notes are mostly for myself but I've put them on this blog in the hope that others might find them useful. This short user manual is by no means complete, but it cover my own usecase and I think that's the one that most users care about.

A short user manual for stow

Preliminaries

Before going in to how to use stow it is useful to know a little bit about how stow expects things to be organized.

To begin with I'm going to use a running example. Suppose you have a program called frobnitz and you would like to have several versions of it installed and be able to switch between them seamlessly.

Normally when programs like frobnitz are installed they end up somewhere under the directory /usr/local. There's where the shell looks for programs when you try to execute them on the command line. All programs are stored together in one big lump there. But stow likes things differently. It expects a new directory /usr/local/stow. This is a directory which you have to create yourself. Each version of each program will have its own directory in the /usr/local/stow directory. So, if you have versions 1.2, 1.3 and 1.4b of frobnitz installed then they will be installed in directories /usr/local/stow/frobnitz-1.2, /usr/local/stow/frobnitz-1.3 and /usr/local/stow/frobnitz-1.4b respectively.

Installing programs for use stow

The first step is to install a program that you which to have under stow's control. Using stow to control the installation of your programs is not compatible with other package managers such as those that come with your distribution. So if you have a program which is already installed via your distribution you must first uninstall it.

Recall from above that stow expects each version of each program to be in a separate directory. Installing a program into its own directory like this is typically just a matter of setting the right prefix when configuring the software. Below is a fictional example of how to install version 1.3 of frobnitz.

./configure --prefix=/usr/local/stow/frobnitz-1.3
make
sudo make install

I've seen more complicated ways of commicating with both configure and make to tell them exactly where files are expected to exist. But the above method has worked without problems for me so I'm sticking with it.

Enabling a program

Installing a program in its own directory like I showed above means that it is not automatically available from the command line and other things like man pages will not show up either. So to enable the program we have to tell stow that we want to use it. This is done by cd:ing to the stow directory and invoking stow with the program that we want to enable.

Here's how to enable version 1.2 of the frobnitz software (assuming it's already installed).

cd /usr/local/stow
sudo stow frobnitz-1.2

After executing the above commands you will have access to the program frobnitz and you will be using version 1.2.

Switching programs

The whole purpose of using stow is so that we can switch between different versions when we want to. Here's how to do that.

Following our running example, suppose you have version 1.2 of the program frobnitz enabled and you would like to switch to version 1.4b. This is done by first disabling 1.2. This is done with the delete command in stow. It might seem a little scary to invoke a command called delete but stow will never destroy things for you. After disabling version 1.2 it's a simple matter to enable 1.4b afterwards.

Here's how you switching programs is done:

cd /usr/local/stow
sudo stow --delete frobnitz-1.2
sudo stow frobnitz-1.4b

Wrapping up

It's not hard to use stow once you know the basic use cases. I hope you've found this little mini-guide useful.

There is at least one other tool which helps having multiple versions of the same program installed at once. The package manager nix can be tricked into doing this but last time I checked it involved to edit some configuration files and I prefer a tool which is a little more user friendly. It is also overkill if all you're after is the functionality that stow offers. That being said, nix looks really nice and I've been meaning to try it out. Any decade now.