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

Ответ 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. Возвращаемое значение передается в регистре.

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

Ответ 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 настороженность устранения общего подвыражения: это опасно, где "(почти) все является выражением", и это указывает, что программист знает, как использовать лямбда.

Ответ 3

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

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

Другим подходом было бы добавить небольшое количество parallelism.

Ответ 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 программирование hivemind, Haskell не делает автоматически memoise (что в любом случае будет медленнее, чем хорошее динамическое программирование ole).

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

Измените версию C на нерекурсивную, и моя ставка заключается в том, что вы увидите, что Haskell и C имеют очень схожую производительность. Трудные циклы проще оптимизировать.