haskell - Haskell 中并行计算的性能问题

Question

我正在比较两个运行相同计算的 Haskell 程序的性能。

第一个是顺序的:

main :: IO()
main = putStr $ unlines . map (show . solve) $ [100..107]
  where solve x = pow x (10^7) (982451653)

第二个使用 Control.Parallel.Strategies :

import Control.Parallel.Strategies

main :: IO()
main = putStr $ unlines . parMap rdeepseq (show . solve) $ [100..107]
  where solve x = pow x (10^7) (982451653)

在这两种情况下， pow是 modular exponentiation天真地实现为:

pow :: Int -> Int -> Int -> Int
pow a 0 m = 1
pow a b m = a * (pow a (b-1) m) `mod` m

正如预期的那样，顺序程序使用 100% 的 CPU 在大约 3 秒内运行。

$ stack ghc seq.hs -- -O2
$ \time -f "%e s - %P" ./seq > /dev/null
2.96 s - 100%

当限制为单核时，并行程序也使用 100% CPU 在大约 3 秒内运行。

$ stack ghc par.hs -- -O2 -threaded
$ \time -f "%e s - %P" ./par +RTS -N1 > /dev/null
3.14 s - 99%

但是当我在 4 个内核上运行它时，我没有观察到预期的性能提升:

$ \time -f "%e s - %P" ./par +RTS -N4 > /dev/null
3.31 s - 235%

更令人惊讶的是，顺序程序在多个内核上运行时使用了超过 100% 的 CPU:

$ stack ghc seq.hs -- -O2 -threaded
$ \time -f "%e s - %P" ./seq +RTS -N4 > /dev/null
3.26 s - 232%

如何解释这些结果？

编辑 - 按照@RobertK 和@Yuras 的建议，我替换了 rdeeseq来自 rpar它确实解决了最初的问题。但是，性能仍然远低于我的预期:

$ stack ghc par.hs -- -O2 -threaded
$ \time -f "%e s - %P" ./par +RTS -N1 > /dev/null
3.12 s - 99%
$ \time -f "%e s - %P" ./par +RTS -N4 > /dev/null
1.91 s - 368%

即使 4 个内核的平均运行时间超过 90%，执行时间也几乎不除以 2。

此外，线程示波器图的某些部分看起来非常有序:

Answer 1

首先，rdeepseq好像是 buggy .尝试运行 ./seq +RTS -N4 -s ，您将不会看到产生任何 Spark 。这就是为什么您在 4 个内核上看不到任何加速的原因。使用 rnf x ‘pseq‘ return x反而。

还要注意 +RTS -s 中的 GC 静态输出。实际上GC占用了大部分CPU。与 -N4您有 4 个并行 GC 正在运行，它们需要更多时间。这就是顺序程序在 4 核上占用更多 CPU 的原因。基本上你有 3 个 GC 线程在自旋锁中空闲等待同步。通过在繁忙的循环中吃 CPU 来做任何有用的事情。尝试使用 -qn1 限制并行 GC 线程的数量选项。

关于性能增益。你不应该期望完美的缩放。另外我认为你有 1 个失败的 Spark ——它是并行评估的，但它的结果没有被使用。

补充:与您在评论中链接的 python 实现相比，我看到您在 haskell 中使用了完全不同的算法。或多或少类似的方法是下一个(需要 BangPatterns ):

pow :: Int -> Int -> Int -> Int
pow a b m = go 1 b
  where
  go !r 0 = r
  go r b' = go ((r * a) `mod` m) (pred b')

您的原始算法使用堆栈来构建结果，因此它受 GC 的约束，而不是受实际计算的约束。所以你看不到大的加速。使用新的，我看到了 3 倍的加速(我不得不增加工作量才能看到加速，因为算法变得太慢了)。