Haskell Nested Vector Parallel Strategy

Question

Like this related question , I would like to execute a parallel map on Vector, but in my case I have a nested Vector and I cannot get the correct estimate.

Here is what I still have:

import qualified Data.Vector as V import qualified Data.Vector.Unboxed as U import Data.Vector.Strategies import Control.DeepSeq main = do let res = genVVec 200 `using` parVector 2 print res genUVec :: Int -> U.Vector Int genUVec n = U.map (ack 2) $ U.enumFromN n 75 genVVec :: Int -> V.Vector (U.Vector Int) genVVec n = V.map genUVec $ V.enumFromN 0 n ack :: Int -> Int -> Int ack 0 n = n+1 ack m 0 = ack (m-1) 1 ack mn = ack (m-1) (ack m (n-1)) instance (NFData a, U.Unbox a) => NFData (U.Vector a) where rnf = rnf . U.toList 

gives:

 $ ./vectorPar +RTS -N8 -s >/dev/null SPARKS: 200 (17 converted, 183 pruned) Total time 1.37s ( 1.30s elapsed) $ ./vectorPar +RTS -s >/dev/null SPARKS: 200 (0 converted, 200 pruned) Total time 1.25s ( 1.26s elapsed) 

I also tried to directly modify the parVector function in vector strategies , but my attempts are clumsy and inefficient.

I understand that REPA was designed for nested workloads, but this seems like a pretty simple problem, and I would prefer not to rewrite a lot of code.

Answer 1

Note. The guilty author of vector strategies is here (this is a very small heading, seeing that it was just a hacked function that I thought others would find useful).

Your observation that parVector is incorrect in that it allows sparks to be GCed before use seems correct. The advice of SimonM means that I should do exactly what I was trying to avoid, instead of the old, create a new vector for a small fee. Knowing this is necessary, there is no reason not to change parVector to a much simpler definition:

 parVector2 :: NFData a => Int -> Strategy (V.Vector a) parVector2 n = liftM V.fromList . parListChunk n rdeepseq . V.toList 

Note that the fix given by John L only works because it “beats” the collector, forcing calculations before the collection happens.

I will change the library of vector strategies, so it is not necessary to make your source code workable. Unfortunately, this will entail the aforementioned cost of creating a new vector (usually minimal).

Answer 2

The problem is that parVector does not cause an evaluation of the elements of the vector. Each element remains thin and nothing sparkles until the vector is consumed (after being printed), which is too late for the sparks to work. You can force evaluation of each element by composing a parVector strategy with rdeepseq .

 import qualified Data.Vector as V import qualified Data.Vector.Unboxed as U import Data.Vector.Strategies import Control.DeepSeq import Control.Parallel.Strategies main = do let res = genVVec 200 `using` (rdeepseq `dot` parVector 20) print res genUVec :: Int -> U.Vector Int genUVec n = U.map (ack 2) $ U.enumFromN n 75 genVVec :: Int -> V.Vector (U.Vector Int) genVVec n = V.map genUVec $ V.enumFromN 0 n ack :: Int -> Int -> Int ack 0 n = n+1 ack m 0 = ack (m-1) 1 ack mn = ack (m-1) (ack m (n-1)) instance (NFData a, U.Unbox a) => NFData (U.Vector a) where rnf vec = seq vec () instance (NFData a) => NFData (V.Vector a) where rnf = rnf . V.toList 

I also changed your instance of NFData (U.Vector a) . Since a U.Vector is unboxed, evaluating WHNF is sufficient, and enforcing each item through list conversion is wasteful. In fact, the default definition for rnf works fine if you like.

With these two changes, I get the following

 SPARKS: 200 (200 converted, 0 pruned) 

and runtime is reduced by almost 50%. I also adjusted the block block size to 20, but the result is very similar to block size 2.