Haskell并行列表计算性能

Question

我是用平行的Haskell函数普兰par和pseq我已经发现了一些有趣的事情.

我的例子基于Real World Haskell的书(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)时间内获得良好的结果,请使用类似随机数据的算法.你可以找到一个简单的方法,如何创建一个随机排列在这里.

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