How to write parallel code with Haskell vectors?

Question

One one hand, in Haskell Vector a seems to be the preferred type to use as an array of numbers. There is even an (incomplete) Vector Tutorial.

On the other hand, Control.Parallel.Strategies are defined mostly in terms of Traversable. Vector library doesn't provide these instances.

The minimal complete definition of Traversable t should also define Foldable and

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
sequenceA :: Applicative f => t (f a) -> f (t a)

I don't see how sequenceA can be defined for Data.Vector.Unboxed.Vector. So, what is the best approach to writing parallel code with unboxed vectors? Defining some new ad hoc strategies like evalVector or using par and pseq explicitly or using plain Data.Array instead of vectors?

P.S. Plain Arrays are parallelizable without problems: https://gist.github.com/701888

Answer 1

1) As you probably know, vector is a product of the DPH work that has proven harder than the researchers initially expected.

2) Unboxed vectors can't divide up the work for individual elements across multiple CPUs.

3) I'd be a lot more hopeful for boxed vectors. Something like:

using (map (rnf . (vec !)) [0..V.length vec - 1]) (parList rdeepseq)

Or maybe you can avoid constructing the list and using parlist. I think just assigning parts of the array is sufficient. The below code is likely broken, but the concept of making your own parVector using rnf and dividing the vector in half until it is a single element (or some tunable chunk size of elements) should work.

parVector :: Strategy (Vector a)
parVector = let !_ = eval vec in Done vec
  where
  chunkSize = 1
  eval v
    | vLen == 0 = ()
    | vLen <= chunkSize = rnf (v ! 0) -- FIX this to handle chunks > 1
    | otherwise = eval (V.take half v) `par` eval (V.drop half v)
    where vLen = V.length v
          half = vLen `div` 2