如何用Haskell向量编写并行代码？

Question

一方面,在Haskell中Vector a似乎是用作数字数组的首选类型.甚至有一个(不完整的)矢量教程.

另一方面,Control.Parallel.Strategies主要是根据而定义的Traversable.矢量库不提供这些实例.

最小的完整定义也Traversable t应该定义Foldable和

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

我看不出如何sequenceA定义Data.Vector.Unboxed.Vector.那么,使用未装箱的向量编写并行代码的最佳方法是什么？定义一些新的临时策略,如evalVector或使用par和pseq明确或使用普通Data.Array而不是向量？

PS Plain Array可并行化,没有问题:https://gist.github.com/701888

Answer 1

这是一个黑客工作,parVector但这对我有用:

import qualified Data.Vector as V
import Control.Parallel.Strategies
import Control.Parallel
import Control.DeepSeq

ack :: Int -> Int -> Int
ack 0 n = n+1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n-1))

main = do
  let vec = V.enumFromN 1 1000
  let res = (V.map (ack 2) vec) `using` parVector
  print res

parVector :: NFData a => Strategy (V.Vector a)
parVector vec = eval vec `seq` Done vec
  where
  chunkSize = 1
  eval v
    | vLen == 0 = ()
    | vLen <= chunkSize = rnf (v 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

并运行此代码:

[tommd@Mavlo Test]$ ghc --make -O2 -threaded t.hs
... dumb warning ...
[tommd@Mavlo Test]$ time ./t +RTS -N1 >/dev/null
real    0m1.962s user    0m1.951s sys     0m0.009s
[tommd@Mavlo Test]$ time ./t +RTS -N2 >/dev/null
real    0m1.119s user    0m2.221s sys 0m0.005s

当我运行代码Integer而不是Int类型签名时:

[tommd@Mavlo Test]$ time ./t +RTS -N2 >/dev/null

real    0m4.754s
user    0m9.435s
sys     0m0.028s
[tommd@Mavlo Test]$ time ./t +RTS -N1 >/dev/null

real    0m9.008s
user    0m8.952s
sys     0m0.029s

岩石!

编辑:一个更接近你早期尝试的解决方案是更清洁(它不使用来自三个独立模块的功能)并且工作得很好:

parVector :: NFData a => Strategy (V.Vector a)
parVector vec =
  let vLen = V.length vec
      half = vLen `div` 2
      minChunk = 10
  in  if vLen > minChunk
      then do
        let v1 = V.unsafeSlice 0 half vec
            v2 = V.unsafeSlice half (vLen - half) vec
        parVector v1
        parVector v2
        return vec
      else
        evalChunk (vLen-1) >>
        return vec
  where
  evalChunk 0 = rpar (rdeepseq (vec V.! 0)) >> return vec
  evalChunk i = rpar (rdeepseq (vec V.! i)) >> evalChunk (i-1)

从这个解决方案中学到的东西:

1. 它使用Evalmonad,这是严格的,所以我们肯定会激发所有东西(相比于包装东西let并记住使用爆炸模式).
2. 与你提出的实现相反,它(a)不构造一个新的向量,这是昂贵的(b)evalChunk使用rpar和rdeepseq(我不相信rpar vec强制任何向量的元素)力量评估每个元素.
3. 与我的观点相反,slice采用起始索引和长度,而不是起始和结束索引.哎呀!
4. 我们仍然需要导入Control.DeepSeq (NFData),但我已经通过电子邮件发送了库列表以尝试修复该问题.

性能似乎与parVector此答案中的第一个解决方案类似,因此我不会发布数字.