The C99 <stdint.h> header provides a plethora of type definition for platform-independent safe code: int_fast16_t, for example, provides an integer that plays well with the machine but has at least 16 bits. The int_fastxx_t and int_leastxx_t defines doesn’t guarantee a tight fit, they provide an machine-efficient fit. They find the fastest type of integer for that machine that respects the constraint.

But let’s take the problem the other way around: what about defines that gives you the smallest integer, not for the number of bits (because that’s trivial with intxx_t) but from the maximum value you need to represent?

Read the rest of this entry »

Single-Pointer Doubly-Linked Lists


Old computer science books aren’t perceived as being of much use, since everything is so much better now. Of course, that’s not entirely true, especially when we are interested in the techniques used in the days where 32KB core memory was “a lot”. Leafing through one such book, Standish’s 1980 Data Structure Techniques, I found a method of maintaining doubly-linked lists using only one pointer. Let’s see how it works!


Read the rest of this entry »

Python References vs C and C++


As I’ve mentioned before, my new job will ask me to program more in Python than C++, and that’s some what new for me. Of course, I’ve criticized Python’s dismal performance on two occasions, getting me all kind of comments (from “you can’t compare performance like that!” to “use another language then” passing by “bind to external high-performance libraries”).

But it seems that my mastery of Python is still quite inadequate, and yesterday (at the time of writing, anyway) I discovered how Python’s by-reference parameters work. Unlike C or C++ that use explicit syntax to specify what kind of object we’re dealing with (either by value, pointer, or by reference), Python is a bit sneaky.

Read the rest of this entry »

Scary Code


If you code a lot in a week, you’re bound to make some (possibly) amusing typos. Almost every time, the typo is detected by the compiler and an error is issued, but sometimes you manage to (mis)type valid code! And I recently make one of those typo and I started wondering how far we can push this idea in writing really, really, really, really ugly code.

Read the rest of this entry »

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.

AMD Phenom

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.

Read the rest of this entry »

#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.

Read the rest of this entry »

Safer Integer Types (part III)


A few days ago (again at the time of writing, but since I accumulate and schedule posts for a weekly release, that may already mean a few months ago) a friend was a bit nonplussed by the fact that an expression such as:

int x;
unsigned int y;

if (x+y<0)

was simply never true. At first, you’re thinking “how can this be?” because you’re trying to find values of x and y that, summed together, are obviously negative. That is, without counting on the surprising integer promotion/integral conversion system of C and C++.

Let us see what’s going on exactly.

Read the rest of this entry »

Safer Integer Constants (Part II)


In C and C++, the behavior of integer promotions is not the same whether we use signed integers or unsigned integers. In bit twiddling hacks, it is not immediately apparent that it is a problem that may lead to unexpected result whenever code is ported to a different architecture. This is a recurring topic whenever I discuss portability with friends. Very often, they argue that if it works on Windows and 32 bits x86 Linux, that’s pretty much all there is to it.

Of course, I couldn’t disagree more. I have learned the hard way.

Read the rest of this entry »

Safer Float Types


This week, we’ll be following last week’s post, where we looked at type-safe integer constants, with floating point constants, that is, float and double.

Read the rest of this entry »

Safer Integer Constants


Consider the following short C (or C++) program:

const int thingy=123123123123;

Depending on your compiler, the above code may succeed, fail, produce a warning, or be accepted quietly and result in undefined behavior, which is extremely bad.

Read the rest of this entry »