multithreading - Haskell 并行列表计算性能

Question

我正在使用并行的 Haskell 函数 par和 pseq我发现了一些有趣的东西。

我的示例基于 Real World Haskell 中的示例的书(Parallel programming in Haskell):

通用代码:

import Control.Parallel (par, pseq)

-- <<sorting code goes here>>

force :: [a] -> ()
force xs = go xs `pseq` ()
    where go (_:xs) = go xs
          go [] = 1

main = do
    print $ take 10 $ parSort [0..1000000]

排序代码1(取自书中):

parSort :: (Ord a) => [a] -> [a]
parSort (x:xs)    = force greater `par` (force lesser `pseq`
                                         (lesser ++ x:greater))
    where lesser  = parSort [y | y <- xs, y <  x]
          greater = parSort [y | y <- xs, y >= x]
parSort _         = []

排序代码 2(我的自定义变体):

parSort :: (Ord a) => [a] -> [a]
parSort (x:xs)    = force greater `par` (lesser ++ x:greater)
    where lesser  = parSort [y | y <- xs, y <  x]
          greater = parSort [y | y <- xs, y >= x]
parSort _         = []

编译并运行: ghc -O2 -threaded --make Main.hs && time ./Main +RTS -N8
有趣的是，我的变体比书籍快一点:

sorting code 1 - avg. 16 seconds
sorting code 2 - avg. 14 seconds

我想问你为什么我们可以观察到这样的行为，以及这本书的解决方案是否比我的更有好处。我很想深入了解为什么这个解决方案可以表现得更好。

Answer 1

我会说这是因为您的自定义变体不会强制列表的第一部分。让我们看看顶层发生了什么:你强制列表的右半部分，而不是左部分。并且当您打印前 10 个元素时，您只会懒惰地评估左侧部分的前 10 个元素，其余部分不予评估。

另一方面，书中的解决方案强制这两个部分，因此在打印前 10 个元素之前，您需要评估左侧和右侧部分。

尝试打印最后一个，而不是打印前 10 个元素，例如

print $ last $ parSort data

那么算法的两个变体都必须评估整个列表。或者在排序之后和打印之前强制整个列表。

备注 那个排序 [0..100000]使用此算法将非常低​​效，因为您总是选择最差的枢轴，因此需要 O(n^2) 时间。测量根本不会给出有意义的结果。如果您想在 O(n log n) 时间内获得好的结果，请为算法提供类似随机的数据。您可以找到一个简单的方法来创建随机排列 here .

注:而不是使用 time我建议你使用 criterion测量你的代码。然后，您可以仅测量代码的相关部分，不包括初始化等，并强制输入和输出数据，以便精确测量您感兴趣的部分。