The Zune Freezes: A Stupid, Avoidable Bug.

December 31, 2008

The few Zune users where alienated today when they discovered that their Zunes just froze during boot. Apparently, a mysterious bug.

The cause of the bug was rapidly diagnosticated. According to Itsnotabigtruck on Zuneboards, the bug can be traced back to a defective date conversion routine. I reproduce here the code for you:

year = ORIGINYEAR; /* = 1980 */

while (days > 365)
 {
  if (IsLeapYear(year))
   {
    if (days > 366)
        {
         days -= 366;
         year += 1;
       }
   }
  else
   {
    days -= 365;
    year += 1;
   }
 }

Can you see what’s just wrong about that code?

Read the rest of this entry »


The True Cost of Calls

December 30, 2008

The cost of virtual functions is often invoked as a reason to C++’s poor performance compared to other languages, especially C. This is an enduring myth that, like most myths, have always bugged me. C++ myths are propagated by individuals that did not know C++ very well, tried it one weekend in 1996, used a bad compiler, knew nothing about optimization switches, and peremptorily declared C++ as fundamentally broken. Well, I must agree that C++ compilers in the mid-90s weren’t all that hot, but in the last fifteen years, a lot have been done. Compilers are now rather good at generating efficient C++ code.

However, the cost of calls, whether or not they are virtual, is not dominated by the the call itself (getting the address to jump to and jumping) but by everything else surrounding the call, like the stack setup and argument passing. Let us debunk that myth by looking at what types of calls are available in C and C++, how they translate to machine code, and see how faster or slower they are relative to each other.

Read the rest of this entry »


The 10 (classes of) Algorithms Every Programmer Must Know About

December 23, 2008

In Tunnels of Doom!, I wrote that the disjoint sets algorithm is one of the very few algorithms every programmer should know. That got me thinking. Should? What about must? If everyone must know about disjoint sets, what other algorithms must every programmer know about?

I made a “top ten” list of algorithms and data structures every programmer must know about.

Read the rest of this entry »


Tunnels of Doom!

December 16, 2008

Æons ago, that is, in September 1982, I got my first true computer, the Texas Instrument TI-99/4A. A truly incredible machine, especially considering the era. Its CPU, a true 16 bits processor, the TMS 9900, ran at 3MHz. Even the popular TRS-80 Color Computer, Radio Shack’s 6809-based computer, ran at a mere 0.895MHz, or, if the gods were good to you, you could tweak the clock divisor and crank it up to 1.79MHz.

In addition to being my first programmable computer, the TI-99/4A sported truly nice graphics and a relatively advanced sound chip—for the era—and a number of games were developed for it. Hunt the Wumpus, Parsec, and others. But the one game that really got me interested in programming is Kevin Kenney’s Tunnels of Doom, one of the very first graphic dungeon crawler games. While not being nostalgic by nature, I returned to that game about a year ago following an unusual route. I was looking into procedural content generation, especially map generation, in relation to data compression and I remembered that the old game’s dungeons were generated randomly, yet were very well structured. I decided to get a look into it, and see if I could generate maps like his.

Read the rest of this entry »


Deriving the 1 bit = 6 dB rule of thumb

December 9, 2008

This week, a more mathematical topic. Sometime ago, we—friends and I—were discussing the fidelity of various signals, and how many bits were needed for an optimal digitization of the signal, given known characteristics such as spectrum and signal-to-noise ratio.

Indeed, at some point, when adding bits, you only add more power to represent noise in the signal. There’s a rule of thumb that say that for every bit you add, you can represent a signal with \approx 6 dB more of signal to noise ratio. Let me show you how you derive such a result.

Read the rest of this entry »


Solaris Getting Better? We’re not there yet!

December 4, 2008

Ars Technica has a review of Open Solaris 2008.11, the latest release from Sun.

The strongest point of this release is the integration in the environment (notably through Nautilus) of ZFS, the Zettabyte File System, which is a next-gen file system supporting lots of nice features, such as storage pool, transactional file system updates and advanced snapshotting. It is a contender to MurderFS ReiserFS now that Reiser‘s in jail for murder. ReiserFS is one of the very nice file systems, but its future is uncertain, which is a major bummer for me as all my Linux boxes are using ReiserFS. ZFS is its most serious contender given its features, at least if one gets around the fact that it is not released under GPL but CDDL.


Safer Integer Constants (Part II)

December 2, 2008

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 »