时间戳

首页 > 解决方案 > Data.Set 成员并行查找

haskell - Data.Set 成员并行查找

问题描述

我正在尝试使用以下代码中的函数在 Data.Set 中进行并行（多核）查找member：

import           Control.Parallel.Strategies (parMap, rpar)
import qualified Data.Set as S

cntSeq :: S.Set Int -> [Int] -> Int
cntSeq set xs = foldl (\c x -> c + (mmbr set x)) 0 xs
  where
    mmbr st x | S.member x st = 1
              | otherwise = 0

cntPar :: Int -> S.Set Int -> [Int] -> Int
cntPar n set xs =
  let
    chnks = chunksOf n xs
    tr = transpose chnks
  in sum $ parMap rpar (cntSeq set) tr

但似乎cntPar实际上并没有从多核中受益。

如果我只用常规列表查找替换 Set ，则并行版本的加速非常重要。

我需要用类似-threaded选项的东西重新编译 Data.Set 吗？

（顺便说一句，我确实意识到这intersection将是一个选项，只是我对并行化集合查找感兴趣——这只是不同问题的简化版本。）

标签： haskell

解决方案

您不需要重新编译Data.Set。-threaded使用标志编译最终程序并使用+RTS -N或类似方式运行它就足够了。

但是，您的测试用例的一个大问题是，我相信执行时间完全由xs列表chunksOf的遍历支配transpose。您看到了列表查找的不同之处，因为它们非常慢，但是任何实际大小的集合查找都太快了，您无法观察到任何好处。

另外，作为一个旁注，parMap rpar并没有真正的意义。 parMap已经并行触发了计算，因此rpar是多余的（并引入了一些额外的微不足道的开销，因为它可能会重新触发计算）。相反，使用，这是一种通过将每个元素评估为 WHNF ( ) 来parMap rseq并行计算列表元素 ( ) 的策略。parMaprseq

要查看一些好处，您可以尝试以下操作。这会传入列表列表以定义避免遍历（甚至可能实际创建）列表的块。在我的 16 核机器上编译-O2 -threaded和运行+RTS -N，它在大约 90 毫秒内运行串行和单块并行版本。具有 10 个块的并行版本运行速度要快得多，大约需要 30 毫秒，而 100 个块的版本则需要 20 毫秒。

import           Criterion.Main
import           Data.List (transpose)
import           Data.List.Split (chunksOf)
import           Control.Parallel.Strategies (parMap, rseq)
import qualified Data.Set as S

cntSeq :: S.Set Int -> [Int] -> Int
cntSeq set xs = sum (map (mmbr set) xs)
  where
    mmbr st x | S.member x st = 1
              | otherwise = 0

cntPar :: S.Set Int -> [[Int]] -> Int
cntPar set = sum . parMap rseq (cntSeq set)

main = do
  let evens = S.fromList [0,2..200000000]
  defaultMain
    [ bench "serial"      $ whnf (cntSeq evens) [0..999999]
    , bench "parallel1"   $ whnf (cntPar evens) [[0..999999]]   -- one chunk
    , bench "parallel10"  $ whnf (cntPar evens) [[i..i+99999] | i <- [0,100000..900000]]  -- 10 chunks
    , bench "parallel100" $ whnf (cntPar evens) [[i..i+9999]  | i <- [0,10000..990000]]   -- 100 chunks
    ]

我机器上的基准输出：

benchmarking serial
time                 90.63 ms   (90.21 ms .. 91.02 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 92.47 ms   (91.81 ms .. 93.48 ms)
std dev              1.372 ms   (807.8 μs .. 2.023 ms)

benchmarking parallel1
time                 91.13 ms   (90.50 ms .. 91.77 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 91.73 ms   (91.38 ms .. 92.26 ms)
std dev              696.0 μs   (427.3 μs .. 905.7 μs)

benchmarking parallel10
time                 31.25 ms   (23.77 ms .. 37.88 ms)
                     0.897 R²   (0.745 R² .. 0.987 R²)
mean                 54.53 ms   (43.81 ms .. 81.93 ms)
std dev              29.69 ms   (18.88 ms .. 40.02 ms)

benchmarking parallel100
time                 19.99 ms   (19.81 ms .. 20.19 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 20.13 ms   (19.99 ms .. 20.62 ms)
std dev              536.7 μs   (111.9 μs .. 1.043 ms)

推荐阅读