CODEWITHSUNDEEP
haskellparallel-processingfunctional-programmingmultiprocessingbinary-tree
CnrL
CnrL

Reputation: 2589

Speeding up binary tree traversal with multiple processors Haskell (parallel)

Following the examples in Chapter 24 of "Real World Haskell" and Chapter 2 of "Parallel and Concurrent Programming in Haskell", I've managed to build the following functions for building and traversing a binary tree quickly using multiple processors.

import Control.Parallel (par, pseq)
import Control.DeepSeq

data Tree x = Empty | Node x (Tree x) (Tree x) deriving (Show, Read, Eq) 

-- Create instance of NFData for Tree data type (defining "normal form")
instance NFData a => NFData (Tree a) where
    rnf Empty = ()
    rnf (Node x l r) = rnf x `seq` rnf l `seq` rnf r

-- Recursive function to build a tree using multiple processors simultaneously
copyBoxPar :: Int -> Tree Int
copyBoxPar x
    | x <= 0 = Empty
    | x > 0  = force left `par` (force right `pseq` (Node x (left)(right)))
     where
     left = copyBoxPar (x-1)
     right = copyBoxPar (x-1)

-- Serial recursive function to count leaves in tree
countBoxes :: Tree x -> Int
countBoxes Empty = 0
countBoxes (Node x left right) = 1 + countBoxes (left) + countBoxes (right)

I can verify that using the functions above, there is a more than 2x speedup using 6 CPUs, compared to the serial equivalent.

However, I'd like to speed this up more if I can.

It seems to me that implementing a parallel version of the countBoxes function should help, but when I try to replace the definition of countBoxes with the parallel code below, I get an error "No instance for (NFData x) arising from a use of 'force'".

-- Parallel function to count leaves in tree
countBoxes :: Tree x -> Int
countBoxes Empty = 0
countBoxes (Node x left right) = force left `par` (force right `pseq` (1 + countBoxes (left) + countBoxes (right)))

Should I really expect a speedup? How can I implement this? Any other advice on streamlining this code would be appreciated.

Upvotes: 0

Views: 470

Answers (1)

Cirdec
Cirdec

Reputation: 24166

Your parallel countBoxes needs an NFData (Tree x) instance to use force on the Tree xs left and right. You can require that one exists by adding NFData x to the context for the type signature for countBoxes. 

-- Parallel function to count leaves in tree
countBoxes :: NFData x => Tree x -> Int
...

NFData x is enough to deduce NFData (Tree x) from due to your instance NFData a => NFData (Tree a).

I suggest you try running this to see how it affects performance. Perhaps a parallel countBoxes shouldn't need to be able to force an entire tree ...

Upvotes: 2

Related Questions