Haskell：顺序斐波那契比并行更快

Question

因此，我正在Haskell中尝试并行处理。我举了一个经典的示例，该示例以顺序和并行方式实现斐波那契数列方法。这是我的Main.hs文件：

module Main where
import Control.Parallel
main = print (fib 47)
fib :: Int -> Int
fib n
| n <=1 = n
| otherwise = fib (n-1) + fib (n-2)

我编译ghc -O2 --make Main.hs -threaded -rtsopts 并执行，time ./Main +RTS -N4这给了我：

2971215073
63.23user 13.03system 0:20.30elapsed 375%CPU (0avgtext+0avgdata 3824maxresident)k
0inputs+0outputs (0major+276minor)pagefaults 0swaps

因此，使用正常的斐波那契大约需要20秒。

现在，如果我将fib方法更改为

pfib :: Int -> Int
pfib n
    | n <= 1 = n
    | otherwise = n1 `par` (n2 `par` n1 + n2)
        where
            n1 = pfib (n - 1)
            n2 = pfib (n - 2)

如上编译和运行，time需要花费更长的时间并完成输出：

2971215073
179.50user 9.04system 0:53.08elapsed 355%CPU (0avgtext+0avgdata 6980maxresident)k
0inputs+0outputs (0major+1066minor)pagefaults 0swaps

进一步修改我的pfib以pseq代替第二个par，可以time得到：

2971215073
113.34user 3.42system 0:30.91elapsed 377%CPU (0avgtext+0avgdata 7312maxresident)k
0inputs+0outputs (0major+1119minor)pagefaults 0swaps

我的代码有问题吗？为什么我在各种实现之间会有不合逻辑的时间差异？

Answer 1

从文档中par：

另外，确保a不是一个微不足道的计算也是一个好主意，否则，并行生成它的成本将使并行运行所获得的收益蒙上阴影。

加法和减法是微不足道的计算。如果仅并行运行几个深度级别，您将看到好处：

module Main where
import Control.Parallel

main = print (pfib 16 47)

fib :: Int -> Int
fib n
    | n <= 1 = n
    | otherwise = fib (n-1) + fib (n-2)

pfib :: Int -> Int -> Int
pfib 1 n = fib n
pfib p n
    | n <= 1 = n
    | otherwise = n1 `par` (n2 `par` n1 + n2)
        where
            n1 = pfib (p - 1) (n - 1)
            n2 = pfib (p - 1) (n - 2)