Наивный Фибоначчи в Си против Хаскелла
Пожалуйста, как сделать оценку g (выдумка) совершенно строго? (Я знаю, что это экспоненциальное решение не является оптимальным. Я хотел бы знать, как сделать эту рекурсию полностью строгой / если возможно /)
Haskell
g :: Int -> Int
g 0 = 0
g 1 = 1
g x = g(x-1) + g(x-2)
main = print $ g 42
Так что он работает примерно так же быстро, как и простое решение C:
С
#include <stdio.h>
long f(int x)
{
if (x == 0) return 0;
if (x == 1) return 1;
return f(x-1) + f(x-2);
}
int main(void)
{
printf("%ld\n", f(42));
return 0;
}
Примечание: эта FIBS-рекурсия используется только в качестве простого примера. Я полностью знаю, что существуют десятки лучших алгоритмов. Но, безусловно, существуют рекурсивные алгоритмы, которые не имеют столь простых и более эффективных альтернатив.
4 ответа
Ответ в том, что GHC делает оценку полностью строгой сама по себе (когда вы даете ей возможность компилировать с оптимизацией). Исходный код производит ядро
Rec {
Main.$wg [Occ=LoopBreaker] :: GHC.Prim.Int# -> GHC.Prim.Int#
[GblId, Arity=1, Caf=NoCafRefs, Str=DmdType L]
Main.$wg =
\ (ww_s1JE :: GHC.Prim.Int#) ->
case ww_s1JE of ds_XsI {
__DEFAULT ->
case Main.$wg (GHC.Prim.-# ds_XsI 1) of ww1_s1JI { __DEFAULT ->
case Main.$wg (GHC.Prim.-# ds_XsI 2) of ww2_X1K4 { __DEFAULT ->
GHC.Prim.+# ww1_s1JI ww2_X1K4
}
};
0 -> 0;
1 -> 1
}
end Rec }
который, как вы можете видеть, если вы знаете ядро GHC, является абсолютно строгим и использует неупакованные целые числа необработанных машин.
(К сожалению, машинный код, создаваемый gcc из исходного кода C, просто быстрее.)
Анализатор строгости GHC довольно хорош, и в таких простых случаях, как здесь, где нет вовлеченного полиморфизма и функция не слишком сложна, вы можете рассчитывать на то, что она может распаковать все значения, чтобы создать работника с использованием unboxed Int#s.
Однако в подобных случаях быстрое создание кода - это больше, чем просто работа на типах компьютеров. Сборка, созданная генератором собственного кода, а также бэкэндом LLVM, по сути является прямой трансляцией кода в сборку, проверяет, является ли аргумент 0 или 1, и если нет, дважды вызывает функцию и добавляет результаты. Оба производят некоторый код входа и выхода, который я не понимаю, и на моем устройстве генератор родного кода производит более быстрый код.
Для кода C clang -O3 производит простую сборку с меньшими затратами и использованием большего количества регистров,
.Ltmp8:
.cfi_offset %r14, -24
movl %edi, %ebx
xorl %eax, %eax
testl %ebx, %ebx
je .LBB0_4
# BB#1:
cmpl $1, %ebx
jne .LBB0_3
# BB#2:
movl $1, %eax
jmp .LBB0_4
.LBB0_3:
leal -1(%rbx), %edi
callq recfib
movq %rax, %r14
addl $-2, %ebx
movl %ebx, %edi
callq recfib
addq %r14, %rax
.LBB0_4:
popq %rbx
popq %r14
popq %rbp
ret
(который по какой-то причине сегодня работает намного лучше в моей системе, чем вчера). Большая разница в производительности между кодом, созданным из исходного кода на Haskell, и C связана с использованием регистров в последнем случае, когда в первом используется косвенная адресация, ядро алгоритма одинаково для обоих.
gcc, без каких-либо оптимизаций, производит, по сути, то же самое, используя некоторую косвенную адресацию, но меньше, чем то, что GHC производил с помощью NCG или LLVM. С -O1То же самое, но с еще меньшей косвенной адресацией. С -O2вы получаете преобразование, так что сборка не может быть легко сопоставлена с источником, и с -O3GCC производит довольно удивительно
.LFB0:
.cfi_startproc
pushq %r15
.cfi_def_cfa_offset 16
.cfi_offset 15, -16
pushq %r14
.cfi_def_cfa_offset 24
.cfi_offset 14, -24
pushq %r13
.cfi_def_cfa_offset 32
.cfi_offset 13, -32
pushq %r12
.cfi_def_cfa_offset 40
.cfi_offset 12, -40
pushq %rbp
.cfi_def_cfa_offset 48
.cfi_offset 6, -48
pushq %rbx
.cfi_def_cfa_offset 56
.cfi_offset 3, -56
subq $120, %rsp
.cfi_def_cfa_offset 176
testl %edi, %edi
movl %edi, 64(%rsp)
movq $0, 16(%rsp)
je .L2
cmpl $1, %edi
movq $1, 16(%rsp)
je .L2
movl %edi, %eax
movq $0, 16(%rsp)
subl $1, %eax
movl %eax, 108(%rsp)
.L3:
movl 108(%rsp), %eax
movq $0, 32(%rsp)
testl %eax, %eax
movl %eax, 72(%rsp)
je .L4
cmpl $1, %eax
movq $1, 32(%rsp)
je .L4
movl 64(%rsp), %eax
movq $0, 32(%rsp)
subl $2, %eax
movl %eax, 104(%rsp)
.L5:
movl 104(%rsp), %eax
movq $0, 24(%rsp)
testl %eax, %eax
movl %eax, 76(%rsp)
je .L6
cmpl $1, %eax
movq $1, 24(%rsp)
je .L6
movl 72(%rsp), %eax
movq $0, 24(%rsp)
subl $2, %eax
movl %eax, 92(%rsp)
.L7:
movl 92(%rsp), %eax
movq $0, 40(%rsp)
testl %eax, %eax
movl %eax, 84(%rsp)
je .L8
cmpl $1, %eax
movq $1, 40(%rsp)
je .L8
movl 76(%rsp), %eax
movq $0, 40(%rsp)
subl $2, %eax
movl %eax, 68(%rsp)
.L9:
movl 68(%rsp), %eax
movq $0, 48(%rsp)
testl %eax, %eax
movl %eax, 88(%rsp)
je .L10
cmpl $1, %eax
movq $1, 48(%rsp)
je .L10
movl 84(%rsp), %eax
movq $0, 48(%rsp)
subl $2, %eax
movl %eax, 100(%rsp)
.L11:
movl 100(%rsp), %eax
movq $0, 56(%rsp)
testl %eax, %eax
movl %eax, 96(%rsp)
je .L12
cmpl $1, %eax
movq $1, 56(%rsp)
je .L12
movl 88(%rsp), %eax
movq $0, 56(%rsp)
subl $2, %eax
movl %eax, 80(%rsp)
.L13:
movl 80(%rsp), %eax
movq $0, 8(%rsp)
testl %eax, %eax
movl %eax, 4(%rsp)
je .L14
cmpl $1, %eax
movq $1, 8(%rsp)
je .L14
movl 96(%rsp), %r15d
movq $0, 8(%rsp)
subl $2, %r15d
.L15:
xorl %r14d, %r14d
testl %r15d, %r15d
movl %r15d, %r13d
je .L16
cmpl $1, %r15d
movb $1, %r14b
je .L16
movl 4(%rsp), %r12d
xorb %r14b, %r14b
subl $2, %r12d
.p2align 4,,10
.p2align 3
.L17:
xorl %ebp, %ebp
testl %r12d, %r12d
movl %r12d, %ebx
je .L18
cmpl $1, %r12d
movb $1, %bpl
je .L18
xorb %bpl, %bpl
jmp .L20
.p2align 4,,10
.p2align 3
.L21:
cmpl $1, %ebx
je .L58
.L20:
leal -1(%rbx), %edi
call recfib
addq %rax, %rbp
subl $2, %ebx
jne .L21
.L18:
addq %rbp, %r14
subl $2, %r13d
je .L16
subl $2, %r12d
cmpl $1, %r13d
jne .L17
addq $1, %r14
.L16:
addq %r14, 8(%rsp)
subl $2, 4(%rsp)
je .L14
subl $2, %r15d
cmpl $1, 4(%rsp)
jne .L15
addq $1, 8(%rsp)
.L14:
movq 8(%rsp), %rax
addq %rax, 56(%rsp)
subl $2, 96(%rsp)
je .L12
subl $2, 80(%rsp)
cmpl $1, 96(%rsp)
jne .L13
addq $1, 56(%rsp)
.L12:
movq 56(%rsp), %rax
addq %rax, 48(%rsp)
subl $2, 88(%rsp)
je .L10
subl $2, 100(%rsp)
cmpl $1, 88(%rsp)
jne .L11
addq $1, 48(%rsp)
.L10:
movq 48(%rsp), %rax
addq %rax, 40(%rsp)
subl $2, 84(%rsp)
je .L8
subl $2, 68(%rsp)
cmpl $1, 84(%rsp)
jne .L9
addq $1, 40(%rsp)
.L8:
movq 40(%rsp), %rax
addq %rax, 24(%rsp)
subl $2, 76(%rsp)
je .L6
subl $2, 92(%rsp)
cmpl $1, 76(%rsp)
jne .L7
addq $1, 24(%rsp)
.L6:
movq 24(%rsp), %rax
addq %rax, 32(%rsp)
subl $2, 72(%rsp)
je .L4
subl $2, 104(%rsp)
cmpl $1, 72(%rsp)
jne .L5
addq $1, 32(%rsp)
.L4:
movq 32(%rsp), %rax
addq %rax, 16(%rsp)
subl $2, 64(%rsp)
je .L2
subl $2, 108(%rsp)
cmpl $1, 64(%rsp)
jne .L3
addq $1, 16(%rsp)
.L2:
movq 16(%rsp), %rax
addq $120, %rsp
.cfi_remember_state
.cfi_def_cfa_offset 56
popq %rbx
.cfi_def_cfa_offset 48
popq %rbp
.cfi_def_cfa_offset 40
popq %r12
.cfi_def_cfa_offset 32
popq %r13
.cfi_def_cfa_offset 24
popq %r14
.cfi_def_cfa_offset 16
popq %r15
.cfi_def_cfa_offset 8
ret
.p2align 4,,10
.p2align 3
.L58:
.cfi_restore_state
addq $1, %rbp
jmp .L18
.cfi_endproc
что намного быстрее чем что-либо еще проверенное. gcc развернул алгоритм на удивительную глубину, чего не сделали ни GHC, ни LLVM, и здесь это имеет огромное значение.
Начните с использования лучшего алгоритма!
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fib n = fibs !! n-1
fib 42 даст вам ответ гораздо быстрее.
Гораздо важнее использовать лучший алгоритм, чем незначительные изменения скорости.
Вы можете счастливо и быстро рассчитать fib 123456 в ghci (то есть интерпретируется, даже не компилируется) с этим определением (его длина 25801 цифр). Вы могли бы заставить свой C-код вычислять это быстрее, но вам потребуется немало времени, чтобы написать его. Это заняло у меня совсем немного времени. Я потратил гораздо больше времени на написание этого поста!
Мораль:
- Используйте правильный алгоритм!
- Haskell позволяет писать чистые версии кода, просто запоминать ответы.
- Иногда легче определить бесконечный список ответов и получить тот, который вы хотите, чем написать какую-то зацикленную версию, которая обновляет значения.
- Хаскель - это круто.
Это абсолютно строго.
g :: Int -> Int
g 0 = 0
g 1 = 1
g x = a `seq` b `seq` a + b where
a = g $! x-1
b = g $! x-2
main = print $! g 42
$! такой же как $ (приложение с низким приоритетом), за исключением того, что оно строгое в аргументе функции.
Вы хотите скомпилировать с -O2 также, хотя мне любопытно, почему вы не хотите использовать лучший алгоритм.
Функция уже полностью строгая.
Обычное определение строгой функции состоит в том, что если вы дадите ей неопределенный ввод, она сама будет неопределенной. Из контекста я предполагаю, что вы думаете о другом понятии строгости, а именно, функция является строгой, если она оценивает свои аргументы до получения результата. Но обычно единственный способ проверить, является ли значение неопределенным, состоит в том, чтобы оценить его, поэтому эти два значения часто эквивалентны.
Согласно первому определению, g безусловно, строгий, поскольку он должен проверить, равен ли аргумент нулю, прежде чем узнавать, какую ветвь определения использовать, поэтому, если аргумент не определен, g сам захлебнется, когда попытается это прочитать.
Согласно более неформальному определению, что может g делать неправильно? Первые два предложения явно хороши и означают, что к тому времени, как мы дойдем до третьего предложения, мы уже должны были оценить n, Теперь в третьем предложении мы добавили два вызова функций. Точнее, перед нами стоят следующие задачи:
- вычесть 1 из
n - вычесть 2 из
n - вызов
gс результатом 1. - вызов
gс результатом 2. - сложите результаты 3. и 4. вместе.
Лень может немного испортить порядок этих операций, но так как + а также g нужны значения их аргументов, прежде чем они смогут запустить свой код, на самом деле ничто не может быть отложено на сколько-нибудь значительную сумму, и, конечно, компилятор может выполнять эти операции в строгом порядке, если он может только показать, что + строгий (встроенный, так что не должен быть слишком сложным) и g строгий (но это, очевидно, так). Таким образом, любой разумный оптимизирующий компилятор не будет иметь особых проблем с этим, и, кроме того, любой неоптимизирующий компилятор не будет подвергаться значительным накладным расходам (это, конечно, не похоже на ситуацию с foldl (+) 0 [1 .. 1000000]) делая абсолютно наивную вещь.
Урок состоит в том, что когда функция немедленно сравнивает свой аргумент с чем-то, эта функция уже строгая, и любой достойный компилятор сможет использовать этот факт для устранения обычных накладных расходов на лень. Это не означает, что он сможет устранить другие накладные расходы, такие как время, затрачиваемое на запуск системы времени выполнения, что, как правило, делает программы на Haskell немного медленнее, чем программы на Си. Если вы просто смотрите на показатели производительности, там происходит гораздо больше, чем ваша программа строгая или ленивая.