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 的文档：

Also it is a good idea to ensure that a is not a trivial computation, otherwise the cost of spawning it in parallel overshadows the benefits obtained by running it in parallel.

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

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)

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

Haskell: sequential Fibonacci faster than parallel

parallel-processing

haskell

fibonacci