Being Shifty

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.

One Does not Simply Rename Into C++

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.

#defines are EVIL (part II)

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.

Is Python Slow? (Part II)

In a previous post I expressed my worries about Python being excruciatingly slow and I used a toy problem to compare the speed of Python to programs in other several languages, including C.

Of course, all kind of people complained that I couldn’t compare a dynamic, interpreted language with static, compiled languages. First, let met tell you that I sure can. First, the goal was to measure speed, and not the effects of type system of the language (although logically correlated) nor the programming paradigm: the amount of CPU used to solve a given problem was the primary (if not only) point in interest.

But to be fair to Python, I extended the tests to other interpreted, dynamic languages, such as Lua, Perl, PHP and JavaScript. I also added Pascal and Haskell in the compiled languages groups.

Failed Experiment

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!

Deep Unit Testing?

Unit testing helps you make sure that your code is working properly but the black-box approach has its limits. In fact, in a complex program with (unsurprisingly) complex behavior, black-boxing becomes a major hindrance to testing. So what are the options? There are several options, but they all seem to have their inconveniences; some violate the basic tenets of object oriented programming, some introduce additional occasions for bugs. I think that there’s no easy solution.

Radix Sort on Floating Point Numbers

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.

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.