Language Benchmarks

Have I mentioned Fourmilab yet? I don't think I did.

Now that I'm back at university, I keep running into a) students who haven't yet learned which languages are faster than others, and b) professors who are still stuck on the initial reputations that languages like Java got before their compilers reached a reasonable level of sophistication. As a result, I've ended up quoting the results from Fourmilab's language benchmarks several times. It's probably a bad idea for me to focus on one bechmark in floating point computation, but I'm not yet interested enough to delve further into the subject.

I guess now is my chance to pimp None Dare Call It Reason, Fourmilab creator John Walker's blog.

The closer you get to the top...

In many types of human endeavour, the better you get, the smaller the gaps are between you and your peers. In sports, for example, there are big gaps between the bad 100m runners, but the top 10 are all within a second (or less) of each other.

In programming, the closer you get to the top, the bigger the gaps get. An average programmer can easily find many peers with roughly the same abilities as himself. A great programmer often has no peers within a factor of two of his own abilities, if not more.

Don't believe me? I just got back from the 2005 ACM east-central North America regional programming contest. Teams of three programmers get one computer, eight problems, and five hours to solve them. The solutions are programs that produce the correct output for every set of input the judges care to test them with.

Here are the full results.

Out of 111 teams competing, 54 failed to solve any problems, 29 managed to solve one, 14 solved 2-3 problems, 9 solved 4-7 problems, and 5 solved all eight. Notice a pattern there? Every doubling of the number of problems solved halved the number of teams that were that good. This is a consistent pattern that appears every year. I suspect it appears in every region too.

It gets worse. As part of the contest, submissions are timed. Of the 5 teams that solved all eight problems, times ranged from 2:33 for the 1st place team to 4:56 for the 5th place team. The 1st place team was twice as fast as the 5th place team. The biggest gap in the top 5 (1hr 7min) was between the 1st and 2nd place teams. The 1st place team didn't train more or have better teachers than the 2nd place team; they were from the same school and trained together.

10,000 days and dancing links

Today I'm 10,000 days old.

I've been reading a lot of papers; the most interesting one I've run across in the past few weeks is called Dancing Links, by Knuth. It's about some of the things you can do with pointers to make your programs more efficient. Highly recommended!