Antonio Cangiano writes about how Ruby 1.9 has improved in various ways, so that the naive fibonacci algorithm is finally faster in Ruby than in Python. So I wondered how well Haskell would do at something like this, and whether we could squeeze any more performance out using some cheap parallelism. Looking at the code,

The Ruby:

    def fib(n)
      if n == 0 || n == 1
        n
      else
        fib(n-1) + fib(n-2)
      end
    end

    36.times do |i|
      puts "n=#{i} => #{fib(i)}"
    end

The Python:

    def fib(n):
       if n == 0 or n == 1:
          return n
       else:
          return fib(n-1) + fib(n-2)

    for i in range(36):
        print "n=%d => %d" % (i, fib(i))

The Haskell:

    fib :: Int -> Int
    fib 0 = 0
    fib 1 = 1
    fib n = fib (n-1) + fib (n-2)

    main = forM_ [0..35] $ \i ->
                printf "n=%d => %d\n" i (fib i)

And, since I’ve got two cores in my laptop, the Haskell annotated for speculative parallelism:

    import Control.Parallel

    fib :: Int -> Int
    fib 0 = 0
    fib 1 = 1
    fib n = l `pseq` r `pseq` l+r
        where
            l = fib (n-1)
            r = fib (n-2)

    main = forM_ [0..35] $ \i ->
                printf "n=%d => %d\n" i (fib i)

One thing that stands out to me is that Haskell looks a fair bit like the Python, and they’re all about the same “development effort”. The other startling thing is how cheap it is to turn the single processor Haskell code into one with hints on how to evaluate it in parallel. The algorithm doesn’t change, we just add parallelism hints that the compiler then uses to parallelise the code. Importantly, and unlike say, Erlang or Concurrent Haskell, we don’t have to do manual thread creation, synchronisation or communication — the compiler does all that for us!

However, the important differences emerge when we run the code: only one implementation here does type erasure (meaning no wasteful runtime type checks), produces native code, always optimises tail calls to gotos, and can do parallelism annotations

Language Time (N=36)
Ruby (1.8.5) 64.26s
Python (2.4) 25.16s
Haskell (GHC 6.8) 0.48s
Parallel Haskell (GHC 6.8) 0.42s

So parallel Haskell is around 60x Python here, and 150x faster than Ruby. And there was basically no difference in development effort required. Which high level language would you choose?

About these ads