Производительность кода, тестируемого в интерактивном приглашении GHCi, может вводить в заблуждение, поэтому при тестировании кода GH C рекомендуется протестировать его в отдельном исполняемом файле, скомпилированном с ghc -O2. Также полезно добавить явные сигнатуры типов и убедиться, что -Wall не сообщает о каких-либо предупреждениях о «дефолтных» типах. В противном случае GH C может выбрать число по умолчанию для чисел c типов, которые вы не намеревались. Наконец, это также хорошая идея использовать библиотеку criterion для бенчмаркинга, так как она хорошо работает для получения надежных и воспроизводимых результатов синхронизации.
Сравнительный анализ ваших двух fib версий таким образом с программой:
import Criterion.Main
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
fib' :: Integer -> Integer -> Integer
fib' 0 a = a
fib' 1 a = 1 + a
fib' n a = fib' (n-1) (fib' (n-2) a)
main :: IO ()
main = defaultMain
[ bench "fib" $ whnf fib 30
, bench "fib'" $ whnf (fib' 30) 0
]
, скомпилированный с GH C 8.6.5 с использованием ghc -O2 -Wall Fib2.hs, я получаю:
$ ./Fib2
benchmarking fib
time 40.22 ms (39.91 ms .. 40.45 ms)
1.000 R² (1.000 R² .. 1.000 R²)
mean 39.91 ms (39.51 ms .. 40.11 ms)
std dev 581.2 μs (319.5 μs .. 906.9 μs)
benchmarking fib'
time 38.88 ms (38.69 ms .. 39.06 ms)
1.000 R² (1.000 R² .. 1.000 R²)
mean 38.57 ms (38.49 ms .. 38.67 ms)
std dev 188.7 μs (139.6 μs .. 268.3 μs)
Разница здесь довольно мала, но может быть последовательно воспроизведена. Версия fib' примерно на 3-5% быстрее, чем версия fib.
На данный момент, возможно, стоит указать, что мои сигнатуры типов использовали Integer. Это также значение по умолчанию, которое GH C выбрал бы без явных сигнатур типов. Замена на Int приводит к значительному повышению производительности:
benchmarking fib
time 4.877 ms (4.850 ms .. 4.908 ms)
0.999 R² (0.999 R² .. 1.000 R²)
mean 4.766 ms (4.730 ms .. 4.808 ms)
std dev 122.2 μs (98.16 μs .. 162.4 μs)
benchmarking fib'
time 3.295 ms (3.260 ms .. 3.332 ms)
0.999 R² (0.998 R² .. 1.000 R²)
mean 3.218 ms (3.202 ms .. 3.240 ms)
std dev 62.51 μs (44.57 μs .. 88.39 μs)
. Поэтому я рекомендую включать явные подписи типов и следить за тем, чтобы не было предупреждений о типах по умолчанию. В противном случае, вы можете потратить много времени в погоне за крошечными улучшениями, когда реальной проблемой является индекс oop, который использует Integer, когда он мог бы использовать Int. В этом примере, конечно, есть еще одна проблема, заключающаяся в том, что алгоритм неверен, поскольку алгоритм имеет квадратичное значение c, и возможна линейная реализация, как и в обычном решении "умный Haskell":
-- fib'' 30 runs about 100 times faster than fib 30
fib'' :: Int -> Int
fib'' n = fibs !! n
where fibs = scanl (+) 0 (1:fibs)
В любом случае, давайте переключимся обратно на fib и fib', используя Integer для остальной части этого ответа ...
Компилятор GH C создает промежуточную форму программы под названием STG (без позвоночника, без метки, G-машина). Это представление самого высокого уровня, которое точно показывает, как программа будет работать на самом деле. Лучшая документация по STG и тому, как она на самом деле переводится в выделение кучи и кадры стека, - это статья Создание быстрого карри: push / enter против eval / apply для языков высшего порядка . При чтении этого документа рисунок 1 является языком STG (хотя синтаксис отличается от того, что GH C создает с -ddump-stg), а первая и третья панели рисунка 2 показывают, как STG оценивается с использованием подхода eval / apply (который соответствует текущему GH C -генерированный код). Есть также более старая статья Реализация ленивых функциональных языков на стандартном оборудовании: G-машина Spineless Tagless G , которая предоставляет намного больше деталей (возможно, слишком много), но немного устарела.
В любом случае, чтобы увидеть разницу между fib и fib', мы можем взглянуть на сгенерированный STG, используя:
ghc -O2 -ddump-stg -dsuppress-all -fforce-recomp Fib2.hs
Взяв вывод STG и существенно очистив его, чтобы он выглядел более похожим на " обычный Haskell ", я получаю следующие определения:
fib = \n -> fib' = \n a ->
case (==) n 0 of case (==) n 0 of
True -> 0 True -> a;
_ -> _ ->
case (==) n 1 of case (==) n 1 of
True -> 1 True -> (+) 1 a; -- (6)
_ -> _ ->
case (-) n 2 of case (-) n 2 of
n_minus_2 -> n_minus_2 ->
case fib n_minus_2 of case fib' n_minus_2 a of
y -> y ->
case (-) n 1 of case (-) n 1 of
n_minus_1 -> n_minus_1 ->
case fib n_minus_1 of fib' n_minus_1 y -- (14)
x -> (+) x y
Здесь анализ строгости уже сделал весь расчет строгим. Здесь нет созданных громов. (В STG только блоки let создают thunks, и в этой STG нет блоков let.) Таким образом, (минимальная) разница в производительности между этими двумя реализациями не имеет ничего общего со строгим и ленивым.
Игнорируя дополнительный аргумент fib', обратите внимание, что эти две реализации по существу структурно идентичны, за исключением операции сложения в строке (6) в fib' и оператора case с операцией сложения в строке ( 14) в fib.
Чтобы понять разницу между этими двумя реализациями, сначала нужно понять, что вызов функции f a b компилируется в псевдокод:
lbl_f: load args a,b
jump to f_entry
Примечание что все вызовы функций, независимо от того, являются ли они хвостовыми вызовами, компилируются в подобные переходы. Когда код в f_entry завершится, он перейдет к любому кадру продолжения на вершине стека, поэтому, если вызывающий объект хочет что-то сделать с результатом вызова функции, он должен сделать sh кадр продолжения до jump.
Например, блок кода:
case f a b of
True -> body1
_ -> body2
хочет что-то сделать с возвращаемым значением f a b, поэтому он компилируется в следующий (неоптимизированный) псевдокод:
push 16-byte case continuation frame <lbl0,copy_of_arg1> onto the stack
lbl_f: -- code block for f a b, as above:
load args a,b
jump to f_entry -- f_entry will jump to lbl0 when done
lbl0: restore copy_of_arg1, pop case continuation frame
if return_value == True jump to lbl2 else lbl1
lbl1: block for body1
lbl2: block for body2
Зная это, разница в строке (6) между двумя реализациями представляет собой псевдокод:
-- True -> 1 -- True -> (+) 1 a
load 1 as return value load args 1,a
jump to next continuation jump to "+"
-- Note: "+" will jump to next contination
, а разница в строке (14) между двумя реализациями:
-- case fib n_minus_1 of ... -- fib' n_minus_1 y
push case continuation <lbl_a> load args n_minus_1,y
load arg n_minus_1 jump to fib'
jump to fib
lbl_a: pop case continuation
load args returned_val,y
jump to "+"
Практически вряд ли есть разница в производительности между ними после их оптимизации. Код сборки, сгенерированный для этих блоков:
-- True -> 1 -- True -> (+) 1 a
movq 16(%rbp),%rsi
movl $lvl_r83q_closure+1,%ebx movl $lvl_r83q_closure+1,%r14d
addq $16,%rbp addq $24,%rbp
jmp *(%rbp) jmp plusInteger_info
-- case fib n_minus_1 of ... -- fib' n_minus_1 y
movq $block_c89A_info,(%rbp) movq 8(%rbp),%rax
movq %rbx,%r14 addq $16,%rbp
jmp fib_info movq %rax,%rsi
movq 8(%rbp),%rsi movq %rbx,%r14
movq %rbx,%r14 // fall through to start of fib'
addq $16,%rbp
jmp plusInteger_info
Разница здесь в нескольких инструкциях. Сохранено еще несколько инструкций, потому что в fib' n_minus_1 y пропущены накладные расходы при проверке размера стека.
В версии, использующей Int, все добавления и сравнения представляют собой отдельные инструкции, а разница между двумя сборками - по моим подсчетам - пять инструкций из примерно 30 инструкций в общей сложности. Из-за жесткого l oop этого достаточно, чтобы учесть разницу в производительности на 33%.
Итак, суть в том, что нет фундаментальной структурной причины, по которой fib' быстрее, чем fib, и небольшое улучшение производительности сводится к микрооптимизации в порядке набора инструкций, которые позволяет хвостовой вызов.
В других ситуациях реорганизация функции для введения хвостового вызова, как это, может или не может улучшить производительность , Эта ситуация, вероятно, была необычной в том смысле, что реорганизация функции имела очень ограниченное влияние на STG, и поэтому улучшение net некоторых инструкций не было подавлено другими факторами.