What the Happy Hacking Keyboard should have been

The Quest for the Perfect Hacking Keyboard is indeed an eternal one. Over the years, I had great many keyboards and most of them went the way of the dodo. Recently, despite not having other Apple products, I tried the (wired) thin Apple aluminum keyboard. As I prefer very thin keyboard over thick ones, and laptop-style keys to the big M Type keys; it was a very good match. However, after a while, I got unnerved by the extra, useless keypad. In short, the keyboard is too long: as I am right handed, it’s always somehow in the way of the mouse so I started looking for a better keyboard. Again.

So I got the Apple aluminium keyboard, wireless version.

Your Automatisms Betray You

Yesterday someone dropped on the IRC channel where my fellow programmers, computer enthusiasts, and I hang out to get help to find a bug. He uses one of the paste sites (like pastebin.ca, pastebin.com, or rafb.net), pastes his piece of offending code, and so we get a look at the code. Of course, I go over the short program, notice a mistake in the scanf but it took me a full two minutes to notice the loop:

for (c=0; c++; cwe don’t read what’s actually written, but what we think is written, unless we pay the utmost attention to the code—what we should be doing anyway, but do not always. Usually, you zero in on that kind of bug rapidly, as you guide your search from the bug’s symptoms which leads you to defect’s approximate location. If you’re like me—write a little, test a lot—you find those bugs right away most of the times. However, even if you zero in rapidly, you still get a coarse-grained location: module, class, function.

Ad Hoc Compression Methods: Digram Coding

Ad hoc compression algorithms always sound somewhat flimsy, but they still have their usefulness whenever the data you have to compress exhibits very special properties or is extremely short. Universal compression algorithms need a somewhat lengthy input to adapt sufficiently to yield good compression. Moreover, you may not have the computing power (CPU speed, RAM and program space) to implement full-blown compressors. In this case also, an ad hoc algorithm may be useful.

Digram (bigram, digraph, bigraph) coding is one of those ad hoc algorithms. Digram coding will compress text (or any source, really) by finding pairs of symbols that appear often and assigning them codes corresponding to used symbols, if any.

Let us see in detail what digram compression is, and how effective it really is.

__MODULE_DEBUG_TOOLS__

Yesterday, at least at the time I am writing this entry, I spoke about the Zune and its time bug that caused so many of the devices to just freeze on boot. It its clear that this bug is the result of poor testing (in addition to a poor implementation of a conversion using loops rather than explicit divisions and moduli) and this week, I’d like to tell you about one of my tricks to debug code.

Throwing in More Hardware?

In a recent blog entry, Jeff Atwood makes the case that “hardware is Cheap, Programmers are Expensive”, basically arguing that in a lot of cases, it’s cost-efficient to add cheap, faster, hardware to a performance problem rather than investing time to actually enhance the code at the algorithmic and implementation level.

I do, however, disagree with him on many points.

Honni soit le Hongrois

The original Hungarian notation is due to Charles Simonyi who invented it sometimes while he was working at Xerox Palo Alto Research Center—the Xerox PARC that gave us the mouse and the first graphical user interfaces. The basic principle of Hungarian naming convention is to prefix the variables with one or many particles, encoding alternatively its type or its intend. This lets programmer write prgszNames as a variable name, which is perfectly legible to one well versed in Hungarian; however, but looks mostly like gibberish to just anyone else.

I recently changed my mind about the Hungarian naming convention. I don’t think it’s that stupid anymore.

The Zunes Freezes: Update!

The faulty code was leaked some time last week, and I’ve looked at it, and, well, it’s surprisingly clean (despite the obvious defect and how they should’ve found it before releasing it (see here)).

Have a look at the ConvertDays routine.

The Zune Freezes: A Stupid, Avoidable Bug.

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?

The True Cost of Calls

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.

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

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.