Bundling Memory Accesses (Part I)

There’s always a question whether having “more bits” in a CPU will help. Is 64 bits better than 16? If so, how? Is it only that you have bigger integers to count further? Or maybe more accessible memory? Well, quite obviously, being able to address a larger memory or performing arithmetic on larger number is quite useful because, well, 640KB isn’t all that much, and counting on 16 bits doesn’t get your that far.

But there are other advantages to using the widest registers available for computation. Often, algorithms that scan the memory using only small chunks—like bytes or words—can be sped up quite a bit using bundled reads/writes. Let us see how.

Channel Mixing and Pseudo-Inverses

Let’s say we want to mix three channels onto two because the communication device has only two available channels but we still want to emulate a three channel link. If we can afford coding, then it’s not a problem because we can build our own protocol so add any number of channels using a structured data stream. But what if we cannot control the channel coding at all? In CDs, for example, there’s no coding: there are two channels encoded in PCM and a standard CD player wouldn’t understand the sound if it was encoded otherwise.

The solution is to mix the three channels in a quasi-reversible way, and in a way that the two channels can be listened to without much interference. One possible way is to mix the third channel is to use a phase-dependant encoding. Early “quadraphonic” audio systems did something quite similar. You can also use a plain time-domain “mixing matrix” to mix the three channels onto two. Quite expygeously, let us choose the matrix:

Live Video Color Gamut

The other day—well, a year ago or so—I was invited to visit CBC’s digital TV studios in Montréal by the SMPTE Montréal. We were shown around, even in the somewhat small control rooms. Amongst all the displays, dials, monitors, and misc. blinkenlights, I noticed a small LCD display showing an hexagonal projection of the current show’s color gamut in (or maybe ?), probably for quality assessment purposes. I thought it was pretty cool, actually.

Let’s see how we can realize this projection with as little CPU time as possible.

Building a Personnal Library (part I)

Building a decent personal library is not very difficult but it can be really expensive. It doesn’t have to, you just have to know where to look for.

An Important Message

Is Python Slow?

Python is a programming language that I learnt somewhat recently (something like 2, 3 years ago) and that I like very much. It is simple, to the point, and has several functional-like constructs that I am already familiar with. But Python is slow compared to other programming languages. But it was unclear to me just how slow Python was compared to other languages. It just felt slow.

So I have decided to investigate by comparing the implementation of a simple, compute-bound problem, the eight queens puzzle generalized to any board dimensions. This puzzle is most easily solved using, as Dijkstra did, a depth-first backtracking program, using bitmaps to test rapidly whether or not a square is free of attack¹. I implemented the same program in C++, Python, and Bash, and got help from friends for the C# and Java versions². I then compared the resulting speeds.

Cargo Cult Programming (part 1)

Programmers aren’t always the very rational beings they please themselves to believe. Very often, we close our eyes and take decisions based on what we think we know, and based on what have been told by more or less reliable sources. Such as, for example, taking red-black trees rather than AVL trees because they are faster, while not being able to quite justify in the details why it must be so. Programming using this kind of decision I call cargo cult programming.

Originally, I wanted to talk about red-black vs. AVL trees and how they compare, but I’ll rather talk about the STL std::map that is implemented using red-black trees with G++ 4.2, and std::unordered_map, a hash-table based container introduced in TR1.

Generating Random Sequences (part I)

Every once in a while, we need a random sequence. Whether to test a data structure’s performance or to run probabilistic unit tests, the provided rand primitive from your favorite programming language has several limitations. First, it’s been known for a while that if most implementations of the C standard library rand() function are not very random, despite being “good enough” in great many cases. Second, and more importantly, it does not allow you to easily control the period nor to generate a permutation on , for example.

There are many methods of generating pseudo-random number sequences. Not all exhibit the same properties and, accordingly, a method may be more useful in one case and perfectly useless in another. High quality pseudo-random number generation is a notoriously hard endeavor, but there is a number of very simple algorithms that will get you out of trouble for certain specific tasks. Let us consider, for example, the example where the pseudo-random generator must generate the numbers in exactly once, in a random order, of course, in exactly draws.

The Zune Freezes: More on Unit Testing

Do you remember the epic fail that bricked the Zune a whole day on the last day of last year, a bisextile year? I described here and here how this error could have been entirely avoided using basic unit testing.

You probably remember (if you read the original post) that I first claimed that it’d take a few seconds to check all possible dates but in fact it ended up taking something like 90 minutes. This week, I come back on unit testing of a very large domain under a time constraint.

Filtering Noise (Part I)

If you own a car, you probably noticed that the speedometer needle’s position varies but relatively slowly, regardless of how the car actually accelerates or decelerates. Unless your speedometer is some variation on the eddy current meter, maybe the noise from the speed sensor isn’t filtered analogically but numerically by the dashboard’s computer.

Let us have a look at how this filtering could be done.