I participated in the 2007 ICFP Contest two weeks ago. I think I did pretty good for a one man team, placing 32nd.
The initial part of the task involved writing an interpreter for a string rewriting system (a string of so-called DNA). Naturally I wrote my interpreter in Haskell and of course the resulting program was terribly slow. (I should note that C++ code that I write also tends to be slow). The best times I got for processing the initial DNA string was about 10.5 minutes. This speed was barely tolerable and afterwards I spent the rest of my time working on the rest of the contest problem.
My source code is available via darcs:
darcs get --tag ICFP2007-solo-r6-entry http://r6.ca/icfp2007
Since then, I have spent some time examining my code and tweeking it in different ways to try and figure out why my code was slow, and what I could have done to speed things up. I am now ready to report my preliminary findings.
The main factor contributing to my slow code was my use of the Haskell libraries that are available for my Linux distribution. Haskell libraries built with a version of Cabal earlier than 1.1.7 do not build with optimizations. This affects current Ubuntu and Debian distributions. In particular, I decided to try my hand at using the MTL.
type DNAMonad = MaybeT (RWS () [RNA] B.ByteString)
Because the MTL library was not optimized, the monads were not available for inlining. Code using the MTL is insanely slow without if the operations are not inlined.
To fix this I patched my code to implement the monad directly. This did two things. First, it eliminated the reader part of the monad that I wasn’t using, and allowed me to layer the state, writer, and error monads in exactly the way I wanted. Second, it was optimized and inlined because I was building it myself with optimizations on.
This (local) fix alone reduces my runtime to a little under 4 minutes. However, presumably there is more that can be done. There is a lisp implementation that runs about 3 times faster than my code (although its timing didn’t include the time to write the RNA output). And rumour has it that C++ code can run it in 16 seconds.