haskell 中的“pars”没有加速

Question

我正在尝试学习 Haskellpars和parseqHaskell。我做了以下事情：

import Control.Parallel
import System.Random

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x : xs) = losort ++ x : hisort
  where
    losort = quicksort [y | y <- xs, y < x]
    hisort = quicksort [y | y <- xs, y >= x]

parallelQuicksort :: Ord a => [a] -> [a]
parallelQuicksort [] = []
parallelQuicksort (x : xs) =
  losort `par` (hisort `pseq` (losort ++ (x : hisort)))
  where
    losort = forceList' $ quicksort [y | y <- xs, y < x]
    hisort = forceList' $ quicksort [y | y <- xs, y >= x]

forceList' :: [a] -> [a]
forceList' xs = foldr pseq [] xs `pseq` xs

main :: IO ()
main = do
  let input = take 3000000 (randomRs (0, 10000) (mkStdGen 42)) :: [Int]
  print $ last $ parallelQuicksort input

然而，运行cabal run haskell-notes-exe -- +RTS -N1 -s并cabal run haskell-notes-exe -- +RTS -N2 -s给出大约相同的性能（事实上该-N1版本更快一点）。为什么？我怎样才能解决这个问题？我本来希望该-N2版本的速度大约是原来的两倍。（我知道有更好的排序方法，我只是想了解这一点）。

Answer 1

确保使用该-threaded选项进行构建。

executable haskell-notes-exe
  ghc-options: -threaded

这样我就看到了-N1take 11 和-N2take 10 ，因此有明显的加速，但它们仍然足够接近，以至于在嘈杂的机器上很难区分。

head input = 8752注意范围 中第一个主元 的值(0,10000)。因此，一个线程仅对列表的 12% 进行排序，而另一个线程则对列表的 88% 进行排序。

如果我们将列表大致分成两半，则parallelQuicksort (5000 : input)、-N1需要 9 秒，并且-N2需要 6.5 秒。好一点，虽然不是 2 倍加速。这个答案的其余部分解释了为什么会这样。

使用 RTS 选项-s打印一些运行时统计信息。重点关注列出时间的表格：

$ ... +RTS -N1 -s

  INIT    time    0.001s  (  0.001s elapsed)
  MUT     time    5.727s  (  5.785s elapsed)
  GC      time    3.273s  (  3.311s elapsed)
  EXIT    time    0.002s  (  0.004s elapsed)
  Total   time    9.003s  (  9.101s elapsed)


$ ... +RTS -N2 -s

  INIT    time    0.001s  (  0.000s elapsed)
  MUT     time    6.412s  (  3.350s elapsed)
  GC      time    4.229s  (  3.240s elapsed)
  EXIT    time    0.012s  (  0.010s elapsed)
  Total   time   10.654s  (  6.601s elapsed)

有两个时间列。第一个是CPU时间，每个线程所花费的时间总和；第二个是“经过”的时间，即你必须等待的时间。

每次运行中的两条重要行是MUT和GC。GC是在垃圾收集器中花费的时间。MUT是“mutator”的缩写，您可以推断出这是进行实际工作的时间。

大约一半的时间花在 GC 上。你的程序会产生很多垃圾。几乎所有作为递归调用的输入和输出的中间列表都quicksort被丢弃，对实际的最终列表没有贡献。您可以通过使用差异列表来避免分配无用的中间输出列表，但每次递归调用时的输入列表实际上是无法避免的（这就是为什么有些人认为真正的快速排序是一种就地算法；Haskell 列表只是错误的数据结构为了那个原因）。

另请注意，使用-N2, in 时MUT，所用时间约为 CPU 时间的一半，这证实了两个线程正在共享工作。两个线程的工作可能仍然不均匀：我们将第一个枢轴放在中间，但后续枢轴可能会偏离中心。

相反，GC 时间在线程之间并不是均匀共享的。垃圾收集器只是部分并行的。另一个需要了解的重要一点是，它是一个停止世界的垃圾收集器：所有线程都必须停止才能让 GC 运行。这就解释了为什么CPU 时间-N2明显高于：有很多垃圾，所以 GC 经常运行，每次都会中断线程，导致大量同步开销。MUT-N1

总而言之，两个线程确实将“实际工作”一分为二，但是 GC 添加了不可并行的额外工作，并且需要同步，这进一步减慢了“实际工作”的速度。