Об улучшении производительности Haskell по сравнению с C в микро-эталоне Фибоначчи

Question

Я сталкивался с этим вопросом , который сравнивал производительность различных компиляторов при вычислении чисел Фибоначчи наивным способом.

Я попытался сделать это с Haskell, чтобы увидеть, как он сравнивается с C.

Код C:

#include <stdio.h>
#include <stdlib.h>

int fib (int n) {
  if (n < 2) return 1;
  return fib (n-1) + fib (n-2);
}

int main (int argc, char* argv[]) {
  printf ("%i\n", fib (atoi(argv[1])));
  return 0;
}

Результат:

> gcc -O3 main.c -o fib
> time ./fib 40
165580141
real    0m0.421s
user    0m0.420s
sys 0m0.000s

Haskell:

module Main where
import System.Environment (getArgs)

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

main = getArgs >>= print . fib . read . head

Результат:

> ghc -O3 -fllvm -optlo-O3 Main.hs -o fib
> time ./fib 40
165580141
real    0m1.476s
user    0m1.476s
sys 0m0.000s

Профилирование с

> ghc -O3 -fllvm -optlo-O3 -prof -auto-all -caf-all -rtsopts Main.hs -fforce-recomp -o fib
> ./fib 40 +RTS -prof

показывает, что fib занимает 100% времени и выделяется, что неудивительно.Я взял некоторый профиль кучи, но не знаю, что они подразумевают:

> ./fib 40 +RTS -hc

> ./fib 40 +RTS -hd

Так что мой вопрос: Могу ли я что-то сделать со своей стороны, чтобы приблизить производительность этой программы на Haskell к C, или именно так GHC делает то, что происходит, чтобы замедлить ее в этом микро-бенчмарке?(Я не прошу асимптотически более быстрый алгоритм для вычисления выдумок.)

Большое спасибо.

[EDIT]

Оказалось, что ghc -O3 былобыстрее, чем ghc -O3 -fllvm -optlo-O3 в этом случае.Но optlo-block-placement сделал заметное отличие для бэкэнда LLVM:

> ghc -O3 Main.hs -o fib -fforce-recomp
> time ./fib 40
165580141
real    0m1.283s
user    0m1.284s
sys 0m0.000s

> ghc -O3 -fllvm -optlo-O3 -o fib -fforce-recomp
> time ./fib 40
165580141
real    0m1.449s
user    0m1.448s
sys 0m0.000s

> ghc -O3 -fllvm -optlo-O3 -optlo-block-placement -o fib -fforce-recomp
> time ./fib 40
165580141
real    0m1.112s
user    0m1.096s
sys 0m0.016s

Причина, по которой я хотел исследовать это, заключалась в том, что и C, и OCaml были значительно быстрее, чем Haskell для этой программы.Я вроде не мог принять это и хотел узнать больше, чтобы убедиться, что я уже сделал все, что мог: D

> ocamlopt main.ml -o fib
> time ./fib 40
165580141
real    0m0.668s
user    0m0.660s
sys 0m0.008s

Answer 1

Профиль кучи здесь не очень интересен, поскольку GHC компилирует fib в функцию, которая работает исключительно в стеке. Просто посмотрите на профиль ... Когда-либо выделяется только 800 байтов, это небольшие накладные расходы вашей main реализации.

Что касается уровня ядра GHC, то он фактически оптимизируется настолько, насколько это возможно. Генерация кода низкого уровня - другое дело. Давайте быстро погрузимся в код, который генерирует GHC:

_Main_zdwfib_info:
.Lc1RK:
    leal -8(%ebp),%eax
    cmpl 84(%ebx),%eax
    jb .Lc1RM

Это проверка стека. Вероятно, что-то C не нужно, поскольку это может позволить операционной системе обрабатывать выделение стекового пространства. На Haskell есть потоки уровня пользователя, поэтому управление пространством стека осуществляется вручную.

    cmpl $2,0(%ebp)
    jl .Lc1RO

Сравнение с 2 из вашего кода.

    movl 0(%ebp),%eax
    decl %eax

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

    movl %eax,-8(%ebp)
    movl $_s1Qp_info,-4(%ebp)
    addl $-8,%ebp
    jmp _Main_zdwfib_info

Параметр и адрес возврата помещаются в верхнюю часть стека, и мы переходим непосредственно к метке для рекурсии.

.Lc1RO:
    movl $1,%esi
    addl $4,%ebp
    jmp *0(%ebp)

Код для случая, когда параметр меньше 2. Возвращаемое значение передается в регистр.

Итог: кажется, все работает так, как должно, вряд ли вы сможете выжать из этого гораздо больше, изменив программу. Пользовательская проверка стека является очевидным источником замедлений, хотя и не уверен, что его можно обвинить в полной разнице во времени.

Answer 2

Это похоже на очень слабый «эталон», как говорит barsoap.Предположим, я сравнил следующие почти одинаково наивные программы:

module Main where
import System.Environment (getArgs)

fib ::  Int ->  Int
fib 0 = 1
fib 1 = 1
fib 2 = 2 
fib n = (\x y -> x + y + y )  (fib (n-3))  (fib (n-2) )

main = getArgs >>= print . fib . read . head  

... и в другом углу ...

#include <stdio.h>
#include <stdlib.h>

int fib (int n) {
  if (n < 2) return 1;
  if (n < 3) return n;
  return (fib (n-3) + fib (n-2)) + fib (n-2);
}

int main (int argc, char* argv[]) {
  printf ("%i\n", fib (atoi(argv[1])));
  return 0;
}

Затем Славные ghc сокрушает gcc, что не удивительно, действительно:

$ ghc --make -fforce-recomp fib.hs -o fibh
[1 of 1] Compiling Main             ( fib.hs, fib.o )
Linking fibh ...
$ time ./fibh 40
165580141

real    0m0.013s
user    0m0.007s
sys 0m0.003s

$ gcc fib.c -o fibc
$ time ./fibc 40
165580141

real    0m1.495s
user    0m1.483s
sys 0m0.003s

, теперь включающий оптимизацию, ghc набирает немного большую скорость:

$ ghc --make -fforce-recomp fib.hs -O3 -o fibhO
$ time ./fibhO 40
165580141

real    0m0.007s
user    0m0.002s
sys 0m0.004s

но gcc наконецПолучите подсказку.

$ gcc fib.c -O3 -o fibcO
$ time ./fibcO 40
165580141

real    0m0.007s
user    0m0.004s
sys 0m0.002s

Я думаю, что объяснение заключается в осторожности ghc общего исключения подвыражения: опасно, когда «(почти) все является выражением», и это полагает, что программист знаеткак использовать лямбду.

Answer 3

GHC компилирует этот штраф. Следующим шагом является микрооптимизация выходных данных из бэкэнда GHC. Игра с различными флагами LLVM может помочь здесь.

Чтобы сделать это, используйте ghc-core для проверки сборки и попробуйте другие флаги для LLVM, чтобы увидеть, что вы получите.

Другой подход заключается в добавлении небольшого количества параллелизма.

Answer 4

Попробуйте это:

fibs :: [Integer]
fibs = 0:1:zipWith (+) fibs (tail fibs)

fib n = fibs !! n

$ time ./fib 10000
  33644[...]6875
  ./fib 10000  0.03s user 0.01s system 89% cpu 0.039 total

(Это на хорошем оле Athlon64 3200 +)

Версия, которую вы используете, для каждого n, вычисляет fib (n-1) и fib (n-2), то есть имеет сложность примерно треугольной природы.Версия выше является линейной: каждый фиб вычисляется только один раз.Несмотря на то, что думает сторонник программирования, не относящийся к Haskell, Haskell не автоматически запоминает (что в целом будет медленнее, чем хорошее оле-динамическое программирование).

Там даже быстрее(используя математические приемы) версия fibonnaci на на Haskell Wiki .

Измените версию C на нерекурсивную, и я уверен, что вы увидите, что и Haskell, и C имеют оченьаналогичная производительность.Плотные петли просто легче оптимизировать.