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?


Read the rest of this entry »

The Perfect Instruction Set

December 28, 2010

The x86 architecture is ageing, but rather than looking for re-invention, it only saw incremental extensions (especially for operating system instructions and SIMD) over the last decade or so. Before getting to the i7 core, we saw a long series of evolutions—not revolutions. It all started with the 8086 (and its somewhat weaker sibling, the 8088), which was first conceived as an evolutionary extension to the 8085, which was itself binary compatible with the 8080. The Intel 8080’s lineage brings us to the 8008, a 8 bits of data, 14 bits of address micro-processor. Fortunately, the 8008 isn’t a double 4004. The successors of the 8086 include (but the list surely isn’t exhaustive) the 80186, the 80286, the 80386, first in the series to include decent memory protection for multitasking, then the long series of 486, various models of Pentium, Core 2 and i7.

So, just like you can trace the human lineage to apes, then to monkeys, and eventually to rodent-like mammals, the x86 has a long history and is still far from being perfect, and its basic weakness, in my opinion, is that it still use the 1974 8080 accumulator-based instruction set architecture. And despite a number of very smart architectural improvements (out of order execution, branch prediction, SIMD), it still suffers from the same problems the 8085 did: the instruction set is not orthogonal, it contains many obsolete complex instructions that aren’t used all that much anymore (such as the BCD helpers), and that everything has to be backwards compatible, meaning that every new generation still is more of the same, only (mostly) faster.

But what would be the perfect instruction set? In [1], the typical instruction set is composed of seven facets (to which I add an eighth):

Read the rest of this entry »

Being Shifty

July 27, 2010

Hacks with integer arithmetic are always fun, especially when they’re not too hard to understand (because some are really strange and make you wonder what the author was thinking when he wrote that). One such simple hack is to replace divisions or multiplies by series of shifts and additions.

However, these hacks make a lot of assumptions that aren’t necessarily verified on the target platform. The assumptions are that complex instructions such as mul and div are very slow compared to adds, right shifts or left shifts, that execution time of shifts only depends very loosely on the number of bit shifted, and that the compiler is not smart enough to generate the appropriate code for you.

Read the rest of this entry »

One Does not Simply Rename Into C++

July 13, 2010

Programming is in many ways more art than science—I do not want to start that debate in this post—in that you need more than mere functionality and correctness to have great code. For code to be great, it has, amongst other things, to be beautiful in that strange, vague, language-specific way.

As you know, this blog is C and C++-centric. Those are the two main languages I use both for personal and for professional projects. I resisted the transition from Pascal to C a long time, for many reasons. One was that at that time C compilers were flimsy, while we had a couple of really great Pascal compiler, such as Turbo Pascal—quite the upgrade from my Apple II’s USCD Pascal. Another was that I found C just ugly, clunky, and primitive; it was terse and inelegant. But over the years, I learnt to like the way C gives you pretty good control on what code is generated—not that you can predict right down to the assembly instructions what the compiler will generate; but you still have a very good idea if you understand even vaguely the underlying machine.

Read the rest of this entry »

#defines are EVIL (part II)

June 29, 2010

In a previous post I discussed some aspects of the C preprocessor (hereafter the CPP) that are evil. Turns out that this week, I had another problem related to a bad usage of the CPP. It didn’t take long to fix, but I can understand why it could be long to figure out.

And while the bug was caused by a careless use of the CPP, I think there’s a couple of simple things we can do to help avoid these.

Read the rest of this entry »

Failed Experiment

May 11, 2010

Experiments do not always work as planned. Sometimes you may invest a lot of time into a (sub)project only to get no, or only moderately interesting results. Such a (moderately) failed experiment is the topic of this week’s blog post.

Some time ago I wrote a CSV exporter for an application I was writing and, amongst the fields I needed to export, were floating point values. The application was developed under Visual Studio 2005 and I really didn’t like how VS2005’s printf function handled the formats for floats. To export values losslessly, that is, you could read back exactly what you wrote to file, I decided to use the "%e" format specifier for printf. Turned out that it was neither lossless nor minimal!

Read the rest of this entry »

Radix Sort on Floating Point Numbers

March 9, 2010

Phimuemue, in a recent post (at the time of writing, anyway) present his variation on sorting floating point values using radix sort. His implementation wasn’t dealing with the pesky sign bit so I offered a slight modification to his algorithm as a comment on his blog. But for some reason, he did not allow to post it.

So I’ll present my solution here.

Read the rest of this entry »