Computing the Neutral Zone

Have you ever add to decide, you and your colleagues, where to go for lunch? Each time, it ends up being a committee, of course. It gets even worse when not only you have many colleagues, but also two offices, or two groups, at different locations. Since we work in a rather large city, we want to walk to the chosen restaurant, rather than drive, but in a way that is fair to either group.

So to settle the argument about where are the restaurants midway of both locations, we need a map, and some math.

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.

Why Validating Input so Hard in C?

Validating input from file or keyboard is probably the most difficult thing to get right in C. Not only is it difficult to get right regardless of the programming language, C really doesn’t do much to help you. There’s the standard library, mostly accessible through the two headers <stdlib.h> and <stdio.h>. However, the facilities provided by the C library are rustic at best. They haven’t aged well, and they’re clunky.

For this post, I will limit I/O validation to grabbing input from text files, whether through a redirection, pipe, file, or console input. I may discuss binary or highly structured formats like XML in a later post, but let us first limit ourselves to a few simple cases.

Stir Fried Stupid

A well structured library will contain functions that are grouped together in a same logical unit to help you perform a set of tasks more easily. This could be reading graphics files, or managing time and dates. Good libraries include just enough functions so that you have access to the complete functionality, but nothing superfluous.

Too often, libraries catch featuritis and grow large with less used functions that were added at some point to scratch a minor hitch. Worst, you discover functions hidden in a library that you’re not sure what to do with them, but sometimes, you find functions that are positively stupid. What is even more surprising is where you can find them. I found a couple in the GNU C Library.

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.

#defines are EVIL

The C (and C++) preprocessor is a powerful but dangerous tool. For sure, it helps with a number of problems, from conditional code inclusion to explicit code generation, but it has a few problems. In fact, more than a few. It is evil.

The C preprocessor (hereafter CPP) should be used with extreme care. For one thing, the CPP doesn’t know about the language it is applied on, it merely proceeds to the translation of the input using very simple rules, and this can leads to tons of hard to detect—and to fix—problems.

The Perl 6 Logo

GnuVince just showed me the new Perl 6 logo. The butterfly Camelia:

Clearly, it looks more like a logo for some kind of association for preschoolers or for a day-care center than a logo for a programming language. It’s repulsively cute. Seeying that, I joked with GnuVince that’d I rather have a logo that felt more like the hybrid, duct-taped, patchwork Perl actually is, so I drew the hippocamptopus:

My friend systemfault took the drawing of the cussing hippocamptopus and made a O’REILLY parody of it:

*
* *

Yes, yes, I know, it’s been done before:

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.

Log Watching

Very often, you have to keep an eye on a log, or maybe more than one log, and a couple of other things while a long-term simulation is running. The GNU/Linux distributions offer the program watch that allows the periodical execution of a command in the current interactive shell. While watch is convenient, you still have the problem of displaying the needed information in a terminal geometry aware way. Turns out, there are tools to query the terminal geometry and we can use them to write simple, effective, well displayed scripts.

So let us see how we can make BASH somewhat aware of the terminal it runs in.

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.