时间戳

首页 > 解决方案 > Haskell 中并行计算的性能问题

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

问题描述

我正在比较运行相同计算的两个 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模幂运算是否天真地实现为：

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 所建议的，我替换了rdeeseqby 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。

此外，threadscope 图的某些部分看起来非常连续： 在此处输入图像描述

标签： haskellparallel-processing

解决方案

首先，rdeepseq似乎是越野车。尝试运行./seq +RTS -N4 -s，您将不会看到任何火花。这就是为什么您在 4 核上看不到任何加速的原因。改为使用rnf x ‘pseq‘ return x。

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

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

补充：与您在评论中链接的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 倍的加速（我不得不增加工作量才能看到加速，因为算法变得太慢了）。

推荐阅读