[Haskell-cafe] saner shootout programs

Richard Kelsall r.kelsall at millstream.com
Tue May 13 10:10:54 EDT 2008

J C wrote:
> <r.kelsall at millstream.com> wrote:
>>  Hello JC, I think you've set yourself a challenge there :) Welcome to
>>  Haskell programming. Taking a Shootout entry and playing with it is
>>  a great way to learn Haskell. The Shootout provides an example in your
>>  favourite previous language for comparison and a small well defined
>>  program with exact test results you can pit your wits against. Fame
>>  awaits you for a fast and beautiful entry. I'm still learning useful
>>  things from the Fasta benchmark. It's surprising how many interesting
>>  things you can discover in a small piece of code.
> It may be fun, but I don't think it would be meaningful. My code will
> be, most likely, slow, leaving some doubt as to whether it's slow
> because of the limitations of the compiler or my inexperience.
> On the other hand, if the experts can't help using malloc, unsafe*,
> global mutables and IO, I'll be able to conclude that this is probably
> what it takes to make Haskell run fast :-(

Don't tell the experts who wrote the current shootout entries, but the
playing field is tilted radically in favour of us beginners being able
to improve on their entries because of new versions of GHC and new
tools that have been developed since they wrote their entries.

GHC will now automatically perform many of the optimisations that used
to have to be done by hand. For example I was surprised to discover
the other day when working on Fasta that putting this plain and simple
version of splitAt

splitAt n (x : xs) = (x : xs', xs'')
                 where (xs', xs'') = splitAt (n-1) xs

in my program made it run more quickly than using the built-in version
of splitAt which I now know looks like (ug!) this

splitAt (I# n#) ls
   | n# <# 0#    = ([], ls)
   | otherwise   = splitAt# n# ls
         splitAt# :: Int# -> [a] -> ([a], [a])
         splitAt# 0# xs     = ([], xs)
         splitAt# _  xs@[]  = (xs, xs)
         splitAt# m# (x:xs) = (x:xs', xs'')
             (xs', xs'') = splitAt# (m# -# 1#) xs

because I was compiling my splitAt with -O2 optimisation as opposed
to the built-in version being compiled with -O. The extra optimisations
in -O2 are a new feature of GHC (and -O2 is slower to compile which is
why the built-in version doesn't use it, but that doesn't matter for the
shootout). You may similarly find various elaborations in the shootout
entries that were historically necessary for speed or memory reasons,
but which can now be removed because GHC or new libraries do the work
for us.

Have a go and see what happens to the speed when you change things
to make N-body more readable. I would bet money on there being simple
tweaks which will make it simultaneously faster and more readable.


More information about the Haskell-Cafe mailing list