Haskell: последовательный Fibonacci быстрее, чем параллельный

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 секунд.

Теперь, если я меняю свой метод Фибо к

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

Compiling и работает, как описано выше, 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:

Кроме того, это хорошая идея, чтобы убедиться, что не является тривиальным вычисление, в противном случае стоимость нереста его параллельно затмевает выгоды, получаемые запустив его параллельно.

Добавление и несколько вычитаний - это тривиальное вычисление. Если вы только запустить несколько уровней глубины параллельно, вы увидите преимущества:

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)