Code Kills

After being frustrated with boring white-on-almost-black (spectro) while working with DrProject wiki files, I broke down and wrote a Vim plugin to make the syntax pretty. It will also parse most of the Trac syntax (and more should be easy to add).

Get it: http://wolever.net/~wolever/drpwiki.vim

Using it:

1. Save it to ~/.vim/syntax/drpwiki.vim (create the directory if it doesn't exist)
2. In Vim, enter `:set filetype=drpwiki`

The dead Linksys power supply

Well, not quite a 'ring' but one red LED.

A few months ago my internet decided to cut out while I was working on a project in the middle of the night, so I went through the usual diagnostics of trying to reset everything, but with no luck. Closer inspection of the router revealed that only the red diagnostic light was on, and it was dimmer than usual. I assumed my router was toast but, decided to make a few attempts to get my internet restored that night.

I can't recall how, but I eventually reached the conclusion that the power supply had crapped out, so I went looking for another 5V power supply. Fortunately I discovered another old router that had one. A bit of soldering later, I had the connectors on the power supplies swapped and voila! It worked! So my internet was back up and I could finish the work on the project.

Now that was a few months ago, so why do I bring it up now? Well, Dave mentioned he had a dead WRT54G and explained the red light just blinked. It sounded like it could be a similar problem, so we plugged it in and the red light came on rather dim -- just like mine. Chances looked good that it might be the same problem. Checking the power supply with a multimeter we found it was 5V as it should of been. Not yet convinced the power supply worked, we popped open the router and checked the voltage when under load and sure enough it was 4V... Too low to power the router. To confirm the router itself works, we temporarily hooked up the 5V from a molex connector of a computer power supply to the router and it started up normally. Problem solved! Now we just need to locate a new 5V power supply for it...

So if you have a dead WRT54G in your closet with only a faint red light showing when you turn it on, you should try another power supply and see if you can give the beast a second chance at life.

Now, while we're on the topic of routers... I feel like I should mention Tomato -- the firmware Dave and I both use. It's got the nicest interface I've ever seen on an embedded device (complete with pretty graphs and smart use of Ajax). It also boots much faster than DD-WRT (although I've heard rumors that things like VPN don't work very well).

The red light of doom

Beautiful Code: That Pesky Binary Search

I was on the subway yesterday, reading Beautiful Code. In Chapter 7, Alberto Savoia is talking about "Beautiful Tests". The code he decides to use to demonstrate beautiful testing is binary search. As he explains:

Binary search is a great example because it's so simple and yet it's so easy to implement incorrectly. In Programming Pearly, Jon Bently shares how, over the years, he asked hundreds of programmers to implement binary search after providing them with a description of the basic algorithm. He gave them a very generous two hours to write it, and even allowed them to use the high-level language of their choice (including pseudocode). Surprisingly, only about 10 percent of professional programmers implemented binary search correctly. (Beautiful Code, p. 87)

Well, I realize that there are some "professional" programmers out there who utterly incompetent... But binary search? Two hours? Pseudo code? I found that very hard to believe. So when he went on to quote Jon Bently again:

Most programmers think that with the above description [of binary search] in hand, writing the code is easy. They are wrong. The only way to believe this is by putting down the column right now and writing the code yourself. Try it. (Programming Pearls)

I didn't have any options other than putting down the book, pulling my laptop out and writing a binary search function. Two TTC stops (about 10 minutes) later, I had a tested solution.

But that's not quite fair. Chapter 4, which I read about a week ago, has binary search code very similar to the code I produced. I'm also fresh out of first-year computer science, where they teach you all sorts of boring wonderful theory.

Well, I work with a bunch of programmers... So why not see what they can do?

Well, out of the four people who wrote a binary search function, the three who vaguely remembered the algorithm were able to code it in less than 20 minutes (including testing). The fourth, who had never heard of the search before, took a little bit longer -- 40 minutes or so -- but still finished with a correct implementation.

But, wait. According to the next page of the book, none of us are correct: every one of us used this line: mid = (low + high) / 2. That could cause an integer overflow if low and high are both greater than 2³⁰. Just how big is that? Well, an array with 2³⁰ 32 bit integers would need 4 gigabytes of memory... Have you ever worked with a single, 4 gigabyte array? I know I haven't. Heck, I'd be willing to bet that 90% of programmers have never dealt with that much data (although Sun had this exact problem with Java)... So I don't think programmers were being penalized for this particular bug.

So what WERE those programmers studied by Jon Bentley doing? Well, after reading the first page of the original article, the numbers start to make a bit more sense:

The professional programmers had one hour (sometimes more) to convert the above description [of a binary search] into a program in the language of their choice; a high-level pseudocode was fine. At the end of the specified time, almost all the programmers reported that they had correct code for the task. We would then take 30 minutes to examine their code, which the programmers did which test cases. In many different classes and with over a hundred programmers, the results varied little: 90 percent of the programmers found bugs in their code (and I wasn't always convinced of the correctness of the code in which no bugs were found).

I don't know about you, but this gives quite a different impression than the description Alberto gave. This makes it seem like 90% of programmers had bugs in their untested code, and the other 10% simply weren't able to find the bugs that were, in fact, there. Now, there is a statistic I would believe.

It's just unfortunate that Alberto did not make that clear... Because the rest of the chapter, where tests are written for a binary search implementation, is about as interesting as testing can be. I just had a hard time appreciating it because I was stuck on the thought that I was better than 90% of professional programmers... Which, thank heaven, I am not.