[This is a local copy of a story that I originally posted to Kuro5hin.org in 2001. This version contains a few typographical corrections and editorial improvements. If you find the story interesting, you may also want to read the original story and the follow-on discussion.]
Yesterday, I submitted my entry to the Fourth ICFP Programming Contest. During the twenty-some hours that I hacked on my entry over the contest’s three days, I made a lot of stupid mistakes and re-learned some important lessons that I thought I had learned a long time ago.
To make sure that the lessons stay in my brain this time, I’m sharing them with you. I also did a few things right, and I might as well share those as well.
If you think you might need to hack under time pressure some day — or if you just want to laugh at my expense — read on.
Background
The ICFP Programming Contest is an annual programming competition held before the International Conference on Functional Programming. The motivation for the contest is to spread the word about functional programming (FP).
The FP community thinks that functional programming is cool, but most other folks couldn’t care less about FP or are ignorant of its existence altogether. So, how to convince the unbelievers? Like so:
-
Hold an international programming contest,
-
Invite anybody and everybody to enter, in teams of any size,
-
Let them use their choice of language(s) and tools to hack for 72 hours on a Challenge Task,
and -
Hope that when the smoke clears and all the entries are judged, the entrants who used FP in their solutions will rise to the top, demonstrating just how darn cool FP is.
Or something like that.
In any case, I entered last year as “Team Functional Beer,” but, owing to a horrible scheduling mistake, didn’t have the opportunity to compete. This year, I vowed to myself, I would put the contest dates on my calendar before promising the very same dates to help two people move into two separate homes on totally opposite sides of glorious Pittsburgh. (In last year’s contest, I didn’t do much hackin’, but I sure did do a lot of packin’ (and liftin’ and carryin’), which as any person with a sore back will tell you, isn’t nearly as fun.) Which brings us to the first lesson:
Lesson 1: Don’t forget about the contest!
[Yes, I’m a moron.]
Okay, so I didn’t forget that painful lesson this year. But, I did forget what I now refer to as Lesson 2:
Lesson 2: Invest more time in planning than just putting the dates on the calendar.
I should have, for instance, recruited friends to join me. I did try to impose upon one friend a few days before the contest, but he couldn’t make it, and I just gave up on recruiting. That was a mistake. It turns out that I could have saved several hours of misspent contest time by having somebody double-check my work, especially to confirm that my understanding of the Challenge Task was correct. I didn’t build a team, and I suffered for it.
About the Challenge Task
The first thing you need to know about the Challenge Task is that it is highly non-trivial. Past Tasks were playing board games (against other entries), optimizing NPC rules for an adventure game (equivalent to a problem in compiler theory), and ray-tracing scenes described in a purely-functional scene-description language. The tasks were designed to provide equal opportunity for both imperative and functional programmers, keeping the contest fair for folks in either camp.
This year’s Task was no different. The challenge was to write an optimizer for a fictional markup language (SML/NG) that could convert one marked-up document (the input) into an equivalent yet smaller document (the output). Here, equivalent was defined to mean that when each document is rendered into a sequence of “decorated characters” according to a set of devious rules, the same sequence would result for each. In other words, you can change the original document all you want, but you cannot change its meaning. If you change the meaning, you’re out of the competition.
In short, correctness comes first. Then degree of optimization (how much the original document was reduced). And then speed (there is a time limit).
SML/NG Optimizer 3000, Iron Chef Style
That’s what I named my entry, which reveals a lot about how darn goofy I am. Out of kindness, I won’t share the README file, which is even goofier. It’s for your own good. Trust me.
At the outset, I established my strategy:
- Always produce output, even if it’s identical to the input (which is correct by definition, and prevents you from getting eliminated for correctness problems when your optimizer otherwise comes up with jack squat.)
- Prepare for catastrophic failure. I used a wrapper program to ensure that if my optimizer crashed, I could at least return the input document as output.
- Test, test, test! I didn’t want to waste my time on bug hunts, so I adopted the policy of not building upon any module of code until I was confident of the code’s correctness.
- Drink espresso. Unfair advantage? Perhaps. But when you’re dealing with a vessel as leaky as my brain, you’ve got to fill it with something.
A deficiency in the list brings us to the next lesson:
Lesson 3: Try, as part of your Grand Master Strategy, O Sage-like CoderBoy, to glance at the Challenge Task before jumping behind the keyboard. (In other words, understand the problem before solving it.)
I kept a log of my activities during the contest, and here’s the initial sequence of events:
- Thu 11:00 EDT. Downloaded challenge task, sent it to the printer, and jumped into the shower. Exited shower, dressed. Read description. [Why I didn’t shower and dress before the contest is a mystery that can only partially be explained by lack of caffeine.]
- Thu 11:30 EDT. Started project with parser.
So, doing the math, it would seem that in the space of thirty scant minutes, I managed to get the Task, print it out, shower, dress, read the entire excruciatingly detailed specification – all of seven 10-point typeset pages – and decide, as the next course of action, that it would be logical to begin writing a parser Right Freakin’ Now.
Sad but true. Later, on the final day of the contest, I ripped out the parser and replaced it with a new one. Had I studied the Task more closely at the outset, I might have realized that the input documents would always be correct (meaning that I could eliminate error-detection) and a few other things that would have lead to a much simpler design. The new parser ran about six times faster than the original and consumed less stack space. I wish I had written it in the first place.
This mistake cost me about two and a half hours, or 10% of my total coding time. How many more optimizations could I have worked into my program had that time not been wasted?
Lesson 4: Test early, test often.
This one I got right. Early on I decided to invest a substantial portion of my time on correctness. I wrote the optimizer in Haskell, so I benefited from Haskell’s wicked-powerful type system, which catches a lot of problems all by itself, and then I used QuickCheck, an automatic testing tool, to further automate away the pain of testing. Here are a few examples from my log that show how a tool like QuickCheck can be your best friend in a tight coding corner:
- Thu 17:13 EDT. QuickCheck is revealing that something is going wrong with either the Parser or my Show instances.
- . . .
- Thu 17:37 EDT. QuickCheck to the rescue! QuickCheck found a test case that falsified my RoundTrip property for Show->Parse->Show, and I was able to hand-feed that case to my parser to determine the error.
- . . .
- Fri 12:19 EDT. My naive optimizer is done. Not so fast, QuickCheck spotted a corner case that causes the optimizer to discard untagged text at the end of a document. Oops.
QuickCheck found these problems and more, many that I wouldn’t have found without a massive investment in test cases, and it did so quickly and easily. From now on, I’m a QuickCheck man!
Two tales of measurement
I once read in an engineering text the following quotation (although I don’t know who said it):
Lesson 5: “Measure. For what you cannot measure, you cannot control.”
Throughout my coding adventure, I made two kinds of measurements that helped me invest my time where it made the most difference. This turned out have a big payoff, as I will share.
The first kind of measurement was profiling. The Glasgow Haskell Compiler comes with some great profiling tools to pinpoint where your program is spending its CPU cycles and allocating its memory. I didn’t waste my time wondering where my cycles were going, I told the profiler to tell me, and it did. For example, I noticed that my program’s run time was proportional to the square of the input document’s size. Since some of the input files were going to be 5 MB, that was a serious problem.
How long did it take to find the problem’s source? The log tells the tale:
- Sat 22:53 EDT. Okay, I’m not sure if it’s the parser. I do know that the overall running time is about O(N^2) with an input of size N. Time to use GHC’s profiling options to pinpoint the trouble.
-
Sat 22:57 EDT. Profiling located the culprit: showsDoc!
COST CENTRE MODULE %time %alloc showsDoc Document 86.1 83.8 dm' Meaning 5.2 10.6 docParser Parse 4.3 2.2 mkTagParser Parse 1.7 2.8
Note that it took just four minutes to turn on the profiling options and find the problem. That’s what I call Return On Investment)
The second kind of measurement was output quality. I wanted to know how well my optimizer was performing. A quick Perl script told me what I wanted to know. At first, my optimizer reduced random documents by about 30%:
AVERAGE REDUCTION = 30%
10% ********
20% **************************************
30% ************************************************************
40% **********************************
50% ********************************
60% **********************
70% ****************************
80% ************
90% ************
100% **************************************************************Then I made a change regarding whitespace handling in my optimizer that I thought would lead to smaller documents, but did it really? The measurements told me it did, and I kept the change:
AVERAGE REDUCTION = 37%
10%
20% ****
30% ****
40% **************
50% ********************************************
60% **********************************************
70% ************************
80% ************
90% **********
100% ****************************************************I used this tool throughout development to tell me which optimizations were worth keeping, and which ought to be left behind. Without it, I would have been guessing and probably would have wasted a lot of time making worthless “improvements.”
A brief word about time, and your brain
More than once, I caught myself staring at code or poking at the keyboard for what seemed hours, all without doing anything productive. It’s not that I’m really that slow; rather, my brain was fried. In one case, a problem that I had struggled with for an hour or so before going to bed turned out to be easy to solve in the morning. The problem didn’t become simpler overnight, but it seemed that way because my morning brain was rested and ready to tackle hard problems. I wish I had gone to bed an hour earlier that night!
Lesson 6: Take breaks, your brain needs them.
I have learned this lesson before, but I forgot it for the contest. More often than not, I coded beyond the point of stupidity. I nearly drooled on the keyboard once.
And then, idiot that I am, I decided to pull an all-nighter before the contest deadline. That was particularly stupid because I accomplished only about fifteen minutes of real work as I “coded” away many hours that would better have been spent on sleep. I had asked my brain to perform in ways that it was unwilling to perform, and it let me suffer for it.
I am certain that I will forget this lesson just in time for next year’s contest. It’s so me.
The final lesson
The final lesson was another that I miraculously got right, but just barely. Foggy-eyed at 4 AM on Sunday morning, I almost snatched defeat from the jaws of victory. The final lesson:
Lesson 7: Have fun!
The ICFP Programming Contest is, most of all, a good way to have a bunch of fun. Early on Sunday morning, I almost forgot that important bit of truth, as I coded into near oblivion. But then I remembered why I write code in the first place – because I love to code. The lightbulb went on: I stopped coding, went to bed, and dreamed happy coding dreams.
Heed my words, lest ye suffer
Learn from my mistakes, remember the lessons that I forgot, and you too may dream happy coding dreams. Otherwise, you are doomed to learn the hard way: from your own mistakes.
[ Visit the Team Functional Beer ICFP 2001 Programming Contest Page ]