如何提升Twistree哈希实现的并行化效率？

以下是一段接收惰性ByteString（可来自文件或其他数据源）并执行哈希计算的Haskell代码。当前hash函数已实现h2与h3的并行计算，待二者完成后调用compress2。经测试，compress2、compress3操作分别耗时289µs、763µs，占程序总耗时的42.5%和56.0%，而输入分块仅占1.4%。现寻求进一步提升该哈希实现并行化程度的方案。

import qualified Data.ByteString as B
import qualified Data.ByteString.Lazy as BL

compress2 ::
  UArray (Word8,Word8) Word8 ->
  UArray Int Word8 ->
  UArray Int Word8 ->
  Int ->
  UArray Int Word8
compress2 sbox buf0 buf1 sboxalt = compress sbox buf sboxalt where
  (beg0,end0) = bounds buf0
  (beg1,end1) = bounds buf1
  len = end0 + end1 + 2 - beg0 - beg1
  buf = listArray (0,len-1) (elems buf0 ++ elems buf1)

compress3 ::
  UArray (Word8,Word8) Word8 ->
  UArray Int Word8 ->
  UArray Int Word8 ->
  UArray Int Word8 ->
  Int ->
  UArray Int Word8
compress3 sbox buf0 buf1 buf2 sboxalt = compress sbox buf sboxalt where
  (beg0,end0) = bounds buf0
  (beg1,end1) = bounds buf1
  (beg2,end2) = bounds buf2
  len = end0 + end1 + end2 + 3 - beg0 - beg1 - beg2
  buf = listArray (0,len-1) (elems buf0 ++ elems buf1 ++ elems buf2)

data Twistree = Twistree
  { sbox    :: UArray (Word8,Word8) Word8
  } deriving Show

compressPairs :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> [UArray Int Word8]
compressPairs _ [] = []
compressPairs _ [x] = [x]
compressPairs sbox (x:y:xs) = ((compress2 sbox x y 0) : compressPairs sbox xs)

hashPairs :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> UArray Int Word8
hashPairs _ [] = undefined -- can't happen, there's always at least exp(4)
hashPairs _ [x] = x
hashPairs sbox x = hashPairs sbox (compressPairs sbox x)

compressTriples :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> [UArray Int Word8]
compressTriples _ [] = []
compressTriples _ [x] = [x]
compressTriples sbox [x,y] = [compress2 sbox x y 1]
compressTriples sbox (x:y:z:xs) = ((compress3 sbox x y z 1) : compressTriples sbox xs)

hashTriples :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> UArray Int Word8
hashTriples _ [] = undefined -- can't happen, there's always at least exp(4)
hashTriples _ [x] = x
hashTriples sbox x = hashTriples sbox (compressTriples sbox x)

linearTwistree = Twistree linearSbox

-- | Creates a Twistree with the given key.
-- To convert a String to a ByteString, put "- utf8-string" in your
-- package.yaml dependencies, import Data.ByteString.UTF8, and use
-- fromString.
keyedTwistree :: B.ByteString -> Twistree
keyedTwistree key = Twistree sbox where
  sbox = sboxes key

hash :: Twistree -> BL.ByteString -> UArray Int Word8
hash twistree stream = par h2 $ par h3 $ compress2 (sbox twistree) h2 h3 2 where
  blocks = blockize stream
  h2 = hashPairs (sbox twistree) (exp4_2adic : blocks)
  h3 = hashTriples (sbox twistree) (exp4_base2 : blocks)

并行化优化方案 #

1. 并行化compressPairs与compressTriples的列表处理 #

当前compressPairs和compressTriples是递归串行生成压缩后的列表，可通过Control.Parallel.Strategies库为列表元素添加并行计算策略，让每一轮的压缩操作同时执行：

import Control.Parallel.Strategies

compressPairs :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> [UArray Int Word8]
compressPairs _ [] = []
compressPairs _ [x] = [x]
compressPairs sbox (x:y:xs) = result `using` parList rseq
  where result = compress2 sbox x y 0 : compressPairs sbox xs

compressTriples :: UArray (Word8,Word8) Word8 -> [UArray Int Word8] -> [UArray Int Word8]
compressTriples _ [] = []
compressTriples _ [x] = [x]
compressTriples sbox [x,y] = [compress2 sbox x y 1]
compressTriples sbox (x:y:z:xs) = result `using` parList rseq
  where result = compress3 sbox x y z 1 : compressTriples sbox xs

这样每一轮生成的压缩结果都会被并行计算，而非等待前一个元素处理完成。

2. 用parMap并行处理每一轮的压缩对/三元组 #

将compressPairs和compressTriples的逻辑改为先拆分列表为对/三元组，再用parMap并行处理所有分组：

compressPairs sbox xs = processed ++ remaining
  where
    (pairs, remaining) = splitIntoPairs xs
    processed = parMap rseq (uncurry (compress2 sbox 0)) pairs
    splitIntoPairs [] = ([], [])
    splitIntoPairs [x] = ([], [x])
    splitIntoPairs (a:b:rest) = ((a,b):ps, rs) where (ps, rs) = splitIntoPairs rest

compressTriples sbox xs = processed ++ remaining
  where
    (triples, remaining) = splitIntoTriples xs
    processed = parMap rseq (\(a,b,c) -> compress3 sbox a b c 1) triples
    splitIntoTriples [] = ([], [])
    splitIntoTriples [x] = ([], [x])
    splitIntoTriples [x,y] = ([], [x,y])
    splitIntoTriples (a:b:c:rest) = ((a,b,c):ts, rs) where (ts, rs) = splitIntoTriples rest

这种方式能让同一轮的所有压缩操作完全并行，最大化利用多核资源。

3. 细粒度并行化compress内部的数组操作 #

如果compress函数的逻辑允许，可将合并后的数组拆分为多个独立段，并行处理后再合并结果。也可以替换UArray为支持并行操作的数组类型，比如Data.Array.Parallel.Unboxed，利用其内置的并行操作优化数组计算效率。

4. 并行化hashPairs与hashTriples的递归轮次 #

当前hashPairs和hashTriples是串行执行每一轮压缩，可在每一轮压缩完成后，对新生成的列表立即应用并行策略，让多轮压缩的部分操作重叠执行：

hashPairs sbox x = hashPairs sbox (compressPairs sbox x `using` parList rseq)
hashTriples sbox x = hashTriples sbox (compressTriples sbox x `using` parList rseq)

内容的提问来源于stack exchange，提问作者Pierre Abbat