Category: Uncategorized

  • Holy Shmoly, GHC Haskell 6.8 smokes Python and Ruby away! And you can parallelise it for free

    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?

  • No monadic headaches: multi-core concurrency is easy in Haskell

    Over on Good Math, Bad Math, MarkCC writes about Erlang and Haskell:

    Haskell systems don’t, in general, parallelize well. They’re particularly bad for the kind of very coarse thread-based concurrency that we need to program for on multi-core computers, or distributed systems.

    I suspect Mark hasn’t written much multicore concurrent Haskell code, as he resorts to the usual “monads are hard” argument, rather than offering example code. However, here in the real world, concurrent programming in Haskell is pretty much identical to Erlang, though with nicer syntax, in a more modern language.

    Importantly, there are no monadic headaches involved (monads don’t even enter the picture). And the results often out-perform Erlang (and most other languages), due to native code compilation with type erasure, and better data structure support, provided by Haskell libraries (particular for strings) simply not available in Erlang.

    So let’s look at the basic tools at our disposal here are:

    Starting first with a look at the Erlang code. Mark starts with an introduction to syntax:

        -module(map).
        -export(map/2, two/1).
    
        map(F, []) -> [];
        map(F,[Car|Cdr]) ->
           NewCar = apply(F, [Car]),
           NewCdr = map(F,Cdr),
           [NewCar|NewCdr].
    
        two(X) -> 2*X.

    Which looks a bit like an antique Haskell, with funny numbers instead of a type system (in the export list). Rewriting in Haskell:

        module Map (map, two) where
    
        map _ []     = []
        map f (x:xs) = f x : map f xs
    
        two = (2*)

    Ok, so simpler and cleaner (I mean, really, using `apply’ for function application!?)

    Now, let’s look at the Erlang for forking a simple process, that receives messages in a loop:

        -module(echo).
        -export([start/0, loop/0]).
    
        start() ->
          spawn(echo, loop, []).
    
        loop() ->
           receive
              {From, Message} ->
                 From ! Message,
                 loop()
           end.

    This translates directly to Haskell’s forkIO and MVars for communication: We just launch the main thread here, which forks a second Haskell thread, which in turn sits receiving messages and printing them:

        main = do
            box <- newEmptyMVar
            forkIO (echo box)
    
        echo c = forever $ do
            msg <- takeMVar c
            print msg

    ‘spawn’ maps to ‘forkIO’, and Erlang’s builtin message passing maps to a communication mechanism of your choice in Haskell. We chose MVars here, but you could also have gone with

    To run such a threaded Haskell program across multiple cores (this coarse gained, multicore concurrency Mark talks about), we need to nothing more than compile in the SMP runtime:

        $ ghc -threaded -O Concurrent.hs

    Now that’s compiled to real native code, on an smp parallel runtime! We can run this over as many cores as we have, and GHC will schedule threads across the cores:

        $ ./a.out +RTS -N2

    There are no monadic headaches. Concurrent and parallel multicore programming in Haskell is simple, efficient and easy!

    Since its so easy, and has such little impact on the structure of your Haskell programs, you can start speculatively supporting multicore hardware: your Haskell program will utilise as many real cores as it needs, without needing to recompile and modify the code. Just change the value of `N’, and throw around forkIO liberally, much as you would in Erlang.

    So let’s do something useful with this, how about a little program that computes primes and fibonacci numbers? We’ll just fork processes to compute prime numbers and fibonacci numbers, and have the main thread lazily print results as they’re found:

        import Control.Concurrent.Chan
        import Control.Concurrent
    
        -- Fork some computation processes, print their results
        main = do
            primes <- run primes
            fibs   <- run fibonacci
            mapM_ print $ zip primes fibs
    
          -- fork a process, return any messages it produces as a list
          where
            run f = do
                c <- newChan
                l <- getChanContents c
                forkIO (writeList2Chan c f)
                return l
    
        -- A function to compute primes
        primes = sieve [2..]
            where
               sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
    
        -- A function to compute fibonacci numbers
        fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

    Very importantly, we see our computational processes are just pure Haskell code, and our main function is some IO skin, as usual. This is almost identical to code you would write ignoring concurrency: nothing scary is needed to write parallel Haskell!

    Compiling this with the parallel runtime:

            $ ghc -threaded -O Server.hs

    And running it on across 2 cores:

        $ time ./Z +RTS -N2
        (2,0)
        (3,1)
        (5,1)
        (7,2)
        (11,3)
        (13,5)
        (17,8)
        (19,13)
        (23,21)
        (29,34)
        (31,55)
        (37,89)
        (41,144)
        (43,233)
        (47,377)
        (53,610)
        (59,987)
        (61,1597)
        (67,2584)
        ^C interrupted

    Easy! The key points to take away:

    • parallel and concurrent code is easy in Haskell, much as in Erlang
    • multi-core concurrency is well supported, out of the box
    • concurrent Haskell is damn fast

    And most importantly, there are no monadic headaches!