Can't seem to get `par` working appropriately with lists

Hopefully an easy one here; after reading Don Stewart's blog posts about parallel Haskell and with a shiny new quad-core cpu begging for a workout, i thought I'd give Haskell a try. I've also been meaning to write a ray-tracer, so I started with that. I've got the initial ray-tracer working, and am now looking to parallize it. I tried using the `par` function to evaluate things in parallel, but I couldn't get it to work with lists. I simplified my problem down into the following 2 test cases: (there are two fibonacci functions to ensure haskell treats them as 2 independent computations to be spread across 2 cores) test1.hs: import Control.Parallel fib1 n = if n == 0 then 0 else if n == 1 then 1 else fib1 (n-1) + fib1 (n-2) fib2 n = if n == 0 then 0 else if n == 1 then 1 else fib2 (n-1) + fib2 (n-2) main = do print $ (fib2 37 `par` fib1 37) + (fib2 37) compilation & testing: luke@Sonata:~/mcls$ ghc -O2 -threaded --make test1 [1 of 1] Compiling Main ( test1.hs, test1.o ) Linking test1 ... luke@Sonata:~/mcls$ time ./test1 +RTS -N1 48315634 real 0m5.856s user 0m5.816s sys 0m0.004s luke@Sonata:~/mcls$ time ./test1 +RTS -N2 48315634 real 0m3.450s user 0m6.734s sys 0m0.024s As expected, running it with 2 cores is substantially faster. Doing almost the same thing, but with lists, doesn't seem to have any significant speed difference: test2.hs: import Control.Parallel fib1 n = if n == 0 then 0 else if n == 1 then 1 else fib1 (n-1) + fib1 (n-2) fib2 n = if n == 0 then 0 else if n == 1 then 1 else fib2 (n-1) + fib2 (n-2) fiblist1 n = [fib1 x| x <- [1..n]] fiblist2 n = [fib2 x| x <- [1..n]] main = do print $ zipWith (+) (fiblist2 37 `par` fiblist1 37) (fiblist2 37) compilation & testing: luke@Sonata:~/mcls$ ghc -O2 -threaded --make test2 luke@Sonata:~/mcls$ time ./test2 +RTS -N1 [2,2,4,6,10,16,26,42... ...405774,18454930,29860704,48315634] real 0m15.294s user 0m15.196s sys 0m0.013s luke@Sonata:~/mcls$ time ./test2 +RTS -N2 [2,2,4,6,10,16,26,42... ...405774,18454930,29860704,48315634] real 0m15.268s user 0m15.169s sys 0m0.013s I've tried using bang patterns in various places, but to no avail. Any ideas? Luke Andrew.

Luke Andrew wrote:
import Control.Parallel
fib1 n = if n == 0 then 0 else if n == 1 then 1 else fib1 (n-1) + fib1 (n-2) fib2 n = if n == 0 then 0 else if n == 1 then 1 else fib2 (n-1) + fib2 (n-2)
main = do print $ (fib2 37 `par` fib1 37) + (fib2 37)
"fib2 37" won't be shared. You're telling ghc to calculate fib2 37 once, in parallel, throw it away, and then calculate it again. Try: let f1 = fib1 37 f2 = fib2 37 in print $ (f2 `par` f1) + f2 Jules

Luke Andrew wrote:
main = do print $ zipWith (+) (fiblist2 37 `par` fiblist1 37) (fiblist2 37)
compilation & testing:
luke@Sonata:~/mcls$ ghc -O2 -threaded --make test2
luke@Sonata:~/mcls$ time ./test2 +RTS -N1 [2,2,4,6,10,16,26,42... ...405774,18454930,29860704,48315634]
real 0m15.294s user 0m15.196s sys 0m0.013s
luke@Sonata:~/mcls$ time ./test2 +RTS -N2 [2,2,4,6,10,16,26,42... ...405774,18454930,29860704,48315634]
real 0m15.268s user 0m15.169s sys 0m0.013s
This is due to lazyness: 'fiblist2 37' does not evaluate the whole resulting list, so the thread spawned by 'par' will almost immediately return. Take a look at Control.Parallel.Strategies, the 'parList' combinator is probably what you need here. To get a feel what this 'strategies' stuff is all about, it is a good idea to read (or at least skim over) the accompanying paper, just google for "Algorithm + Strategy = Parallelism". Cheers Ben

ben.franksen:
Luke Andrew wrote:
main = do print $ zipWith (+) (fiblist2 37 `par` fiblist1 37) (fiblist2 37)
compilation & testing:
luke@Sonata:~/mcls$ ghc -O2 -threaded --make test2
luke@Sonata:~/mcls$ time ./test2 +RTS -N1 [2,2,4,6,10,16,26,42... ...405774,18454930,29860704,48315634]
real 0m15.294s user 0m15.196s sys 0m0.013s
luke@Sonata:~/mcls$ time ./test2 +RTS -N2 [2,2,4,6,10,16,26,42... ...405774,18454930,29860704,48315634]
real 0m15.268s user 0m15.169s sys 0m0.013s
This is due to lazyness: 'fiblist2 37' does not evaluate the whole resulting list, so the thread spawned by 'par' will almost immediately return.
Take a look at Control.Parallel.Strategies, the 'parList' combinator is probably what you need here. To get a feel what this 'strategies' stuff is all about, it is a good idea to read (or at least skim over) the accompanying paper, just google for "Algorithm + Strategy = Parallelism".
or 'rnf' on the result. rnf x `par` y is the basic "fully strict" strategy.
participants (4)
-
Ben Franksen
-
Don Stewart
-
Jules Bean
-
Luke Andrew