如何在Haskell中使用并行策略

Question

我有一个frequencyBy我想并行化的功能.以下是一个简单的测试用例:

import Control.Parallel.Strategies
import Control.DeepSeq
import System.Environment

frequencyBy :: (a -> b -> Bool) -> [a] -> [b] -> [(a,Int)]
frequencyBy f as bs = map 
    (\a ->(a, foldr (\b -> if f a b then (+) 1 else id) 0 bs)) as

main :: IO ()
main = do
  x:xs <- getArgs
  let result = frequencyBy (==) [1::Int .. 10000] [1 .. (read x)] `using` 
                 parList rdeepseq
  print $ product $ map snd $ result

我想运行map在frequencyBy平行.我正在尝试使用parList rdeepseq(所有其他的东西main只是为了确保不是所有的东西都被优化了).但是,这不起作用,两个线程的工作量是同一个线程同时执行的两倍.我不明白我在这里做错了什么.

Answer 1

可能是开销减慢了速度,取决于x的大小; 如果你在每个火花中所做的工作与产生每个火花所需的时间相当(当然还有调度开销等),那么你会遇到问题.

你可以尝试parListChunk,例如parListChunk 64 rdeepseq; 你必须尝试找出要使用的块大小.虽然您当前的策略是为列表的每个元素parListChunk创建一个spark,但是为列表中的每个特定大小的块创建一个spark,并使用您在该块的每个元素上按顺序指定的策略.

顺便说一句,由于过多的thunk创建,foldrin frequencyBy可能会减慢速度; 就像是

frequencyBy :: (a -> b -> Bool) -> [a] -> [b] -> [(a,Int)]
frequencyBy f as bs = map (\a -> (a, sum . map (const 1) . filter (f a) $ bs)) as

应该解决这个问题

当然,一如既往,确保您正在编译-O2和运行+RTS -N.

Answer 2

我认为你的并行性太精细了. parList尝试并行评估每个元素,并且对于任何一个元素来说确实没有那么多工作.

当我从改变parList到parListChunk 500执行时间增加了近50%; 因为我在双核机器上,它的功能和它一样好.

作为参考,我正在测试x=20000.