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

[Don Stewart]

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
        n <- getArgs >>= readIO . head
        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