# [Haskell-cafe] Parallelise now! Was: Re: Possible Improvements

Don Stewart dons at galois.com
Mon Dec 3 05:20:19 EST 2007

```dons:
> Strict in the elements, lazy in the spine:
>
>     data Tree = Leaf !Int | Node Tree !Int Tree
>
>     \$ time ./A 25
>     49
>     ./A 25  14.41s user 0.03s system 99% cpu 14.442 total
>                                              ^^^^^^
>     3056K heap use.

And, finally, we can get a little speedup again over the basic
element-strict, -funboxed-strict-fields tree by parallelising
some of the traversals. Nothing great, but I didn't try very hard:

Serial code:

{-# OPTIONS -O2 -funbox-strict-fields #-}

import System.Environment

data Tree = Leaf !Int | Node Tree !Int Tree

main = do
let t = make (n*2) n
print (check t)

make :: Int -> Int -> Tree
make i 0 = Node (Leaf 0) i (Leaf 0)
make i d = Node (make (i2-1) d2) i (make i2 d2)
where i2 = 2*i
d2 = d-1

check :: Tree -> Int
check (Leaf _)     = 0
check (Node l i r) = i + check l - check r

Running:

\$ time ./A 28
55
./A 28  24.39s user 0.03s system 99% cpu 24.424 total

Ok. Now, parallelise that recursive call in 'check':

check :: Tree -> Int
check (Leaf _)     = 0
check (Node l i r) = lp `par` (rp `pseq` i + lp - rp) -- <--
where lp = check l
rp = check r

Super-simple strategy -- will register too many sparks, but what the heh...

\$ time ./B 28  +RTS -N2
55
./B 28 +RTS -N2  31.81s user 0.14s system 147% cpu 21.700 total

Pretty good for a naive strategy, and only one branch, on one line had to be modified.
Control.Parallel, yay!

-- Don
```