Smaller enums

October 17, 2017

As you may have noticed, efficient representation of information and data structure is kind of a hobby of mine. I often look at ways I can reduce the memory footprint, and, as often, it’s the small details that are the most annoying, like, for example, enums that use up pretty much anything the compiler feels like.

Indeed, the standard does not require that the compiler uses the smallest type, but merely one that can hold all values (§7.2.6, in ISO/IEC 14882:2011(E)), so you end up with something “convenient”, that is, int. Unless, of course, you do specify storage.

Read the rest of this entry »


Medians (Part IV)

September 19, 2017

I’ve visited the median problem a couple of times already. The median is the value in the middle of a sorted list of values. If the list is already sorted, that’s not much of a problem. If it isn’t, then we must use some efficient way to do it.

Read the rest of this entry »


New Block Order

March 21, 2017

The idea of reorganizing data before compression isn’t new. Almost twenty five years ago, Burrows and Wheeler proposed a block sorting transform to reorder data to help compression. The idea here is to try to create repetitions that can be exploited by a second compression engine.

But the Burrows-Wheeler transform isn’t the only possible one. There are a few other techniques to generate (reversible) permutations of the input.

Read the rest of this entry »


Much Ado About Nothing

March 7, 2017

A rather long time ago, I wrote a blog entry on branchless equivalents of simple functions such as sex, abs, min, max. The Sing EXtension instruction propagates the sign bit in the upper bits, and is typically used in the promotion of, say, a 16 bits signed value into a 32 bits variable.

But this time, I needed something a bit different: I only wanted the sign-extended part. Could I do much better than last time? Turns out, the compiler has a mind of its own.

Read the rest of this entry »


Whatever sums your floats

January 24, 2017

While flipping the pages of a “Win this interview” book—just being curious, not looking for a new job—I saw this seemingly simple question: how would you compute the sum of a series of floats contained in a array? The book proceeded with the simple, obvious answer. But… is it that obvious?

Read the rest of this entry »


Strings in C++ Switch/Case statements

January 10, 2017

Something that used to bug me—used to, because I am so accustomed to work around it that I rarely notice the problem—is that in neither C nor C++ you can use strings (const char * or std::string) in switch/case statement. Indeed, the switch/case statement works only on integral values (an enum, an integral type such as char and int, or an object type with implicit cast to an integral type). But strings aren’t of integral types!

In pure C, we’re pretty much done for. The C preprocessor is too weak to help us built compile-time expression out of strings (or, more exactly, const char *), and there’sn’t much else in the language to help us. However, things are a bit different in C++.

Read the rest of this entry »


Size(_t) matters!

December 27, 2016

Sometime last week, a tweet from @nixCraft prompted the question, quite ironically, how do you get the maximum (largest positive) value for an integer?

max_int

Read the rest of this entry »