Haskell parMap and parallelism

Question

I have an implementation of Conway's Game of Life. I want to speed it up if possible by using parallelism.

life :: [(Int, Int)] -> [(Int, Int)]
life cells = map snd . filter rules . freq $ concatMap neighbours cells
    where rules (n, c) = n == 3 || (n == 2 && c `elem` cells)
          freq = map (length &&& head) . group . sort

parLife :: [(Int, Int)] -> [(Int, Int)]
parLife cells = parMap rseq snd . filter rules . freq . concat $ parMap rseq neighbours cells
    where rules (n, c) = n == 3 || (n == 2 && c `elem` cells)
          freq = map (length &&& head) . group . sort

neigbours :: (Int, Int) -> [(Int, Int)]
neighbours (x, y) = [(x + dx, y + dy) | dx <- [-1..1], dy <- [-1..1], dx /= 0 || dy /= 0]

in profiling, neighbours accounts for 6.3% of the time spent, so while small I expected a noticable speedup by mapping it in parallel.

I tested with a simple function

main = print $ last $ take 200 $ iterate life fPent
    where fPent = [(1, 2), (2, 2), (2, 1), (2, 3), (3, 3)]

and compiled the parallel version as

ghc --make -O2 -threaded life.hs

and ran it as

./life +RTS -N3

it turns out that the parallel version is slower. Am I using parMap incorrectly here? is this even a case where parallelism can be used?

Answer 1

I don't think you're measuring right. Your parLife is indeed a bit faster than life. In fact, on my machine (Phenom X4, 4 core,) the former only takes about 92.5% of the time the latter does, which considering you're saying you're expecting only a 6% improvement is quite good.

What is your benchmarking setup? Have you tried using criterion? Here's what I did:

import Criterion
import Criterion.Main

-- your code, minus main

runGame f n = last $ take n $ iterate f fPent
    where fPent = [(1, 2), (2, 2), (2, 1), (2, 3), (3, 3)]

main = defaultMain
    [ bench "No parallelism 200" $ whnf (runGame life)    200
    , bench "Parallelism 200"    $ whnf (runGame parLife) 200 ]

Compiled with ghc --make -O2 -o bench and ran with ./bench -o bencht.hmtl +RTS -N3.

Here's the detailed result of the report.