Parallel "insertions" into a binary trie in Haskell

Question

I have a list of n-bit "words"

type BitWord = [Bool]

and a trie which stores the word from the top to bottom:

data Tree = Bs Tree Tree  -- Bs (zero_bit) (one_bit)
          | X -- incomplete word
          | B -- final bit of word

I have a function:

seenPreviously :: BitWord -> Tree -> (Tree,Bool)

The function steps through the bits in the BitWord, while descending through the Tree going left at a zero bit and vice versa. We return a new tree with this BitWord "merged in", along with True if we had to add subtrees at some point (i.e. the BitWord was not in the trie already) and False otherwise.

I map this function over a [BitWord], passing the Tree as state.

My question is this: Could this benefit from parallelism offered by Control.Parallel? And if so, how can I reason about laziness and evaluation only to weak head normal form, etc.?

My instinct is that I can be inserting (actually building a subtree) down a left branch while doing the same thing down the right branch, as two independent threads. Something like:

parallelMapSt :: [ BitWords ] -> Tree -> [Bool]
parallelMapSt [] _ = []
parallelMapSt (w:ws) t = let (b,t') = seenPreviously w t
                             bs     = parralelMapSt ws t'
                          in t' `par` bs `pseq` (b:bs)

The thread evaluating b is dependent on some previously sparked threads (the ones belonging to the BitWords that share some common prefix with w), but not all of them, so it would seem that there is opportunity to do work in parallel here, but I'm really not sure.

Answer 1

Why don't you just try it and see? Time the execution of the program with 1 thread and several, and see if there's a difference. Sparks in Haskell are really very cheap, so don't worry if you create a lot of them.

Answer 2

Looks like a great candidate for the use of par when traversing the tree... Much like the binary-trees benchmark. Try writing some programs on this type, and measuring the effect of par.

Answer 3

Returning whether a word was in the trie unnecessarily sequentializes your program. If you really do need this information, it will probably be difficult to parallelize efficiently.

However, if we can rephrase the problem a bit such that order and disposition of insertions doesn't matter, the problem is pretty straightforward:

import Control.Parallel

data Tree = Bs Bool         -- ^ is an empty word inserted here?
               (Maybe Tree) -- ^ '0' subtree
               (Maybe Tree) -- ^ '1' subtree
     deriving Show

insertMany :: [[Bool]] -> Maybe Tree
insertMany []  = Nothing
insertMany xss = hasEnd `par` fs `par` ts `pseq` Just (Bs hasEnd fs ts)
 where
    hasEnd = any null xss
    fs = insertMany [ xs | False : xs <- xss]
    ts = insertMany [ xs | True  : xs <- xss]

I don't have multiple cores at the moment, so I can't test this, but it should scale well. We've basically got a parallel radix sort in just a few lines -- not too shabby!