Вы не говорите, из какого кода был сгенерирован этот пример, или на каком компиляторе, но он должен быть очень грубым, может быть, даже каким-то игрушечным компилятором из класса компиляторов старшекурсников. Вы правы, что это крайне неоптимально. Даже самая старая версия gcc, которую я тестировал со всеми отключенными оптимизациями, не дает такого плохого кода. Давайте посмотрим на то, что мы получаем, когда собираем несколько разных компиляторов. Хороший способ сравнить - на Годболт .
Я проверял следующий код:
unsigned long long factorial(const unsigned long long n)
{
return (n <= 1) ? 1
: n*(factorial(n-1));
}
Функция factorial() - это простая однострочная рекурсивная реализация, которую вы описываете. Я также написал factorial_tail(), хвостовую рекурсивную версию с аккумулятором, чтобы некоторым компиляторам было легче заметить, что функция является хвостовой рекурсивной по модулю ассоциативной операцией и поэтому может автоматически преобразовываться в тугая петля.
Современные компиляторы, тем не менее, обычно довольно умны в этом вопросе.
Без каких-либо оптимизаций, кроме -fomit-frame-pointer (для подавления сохранения и восстановления кадров стека), это то, что делает gcc 8.2:
factorial:
sub rsp, 24
mov QWORD PTR [rsp+8], rdi
cmp QWORD PTR [rsp+8], 1
jbe .L2
mov rax, QWORD PTR [rsp+8]
sub rax, 1
mov rdi, rax
call factorial
imul rax, QWORD PTR [rsp+8]
jmp .L4
.L2:
mov eax, 1
.L4:
add rsp, 24
ret
Вы по-прежнему можете видеть, как функция сохраняет промежуточный результат в стеке, непосредственно над 8-байтовым адресом возврата, и выполняет некоторое ненужное копирование в и из стека. Цель этого состоит в том, чтобы при отладке временное значение существовало в отдельном месте памяти и могло просматриваться, проверяться и изменяться.
Вы спрашиваете: «Разве эти вычисления не будут намного быстрее, если использовать какой-либо из нетронутых регистров общего назначения и опускать эти локальные стеки [...]?» Хорошо подумать! Это действительно так! Вы не можете просто сохранить каждый фактор факториала в другом регистре, потому что могут быть миллиарды и миллиарды. Но вы можете автоматически реорганизовать код до тех пор, пока вам не понадобится только постоянное пустое место.
В рабочем коде вы бы включили оптимизацию. В целях обучения код, оптимизированный для пространства, легче понять, чем код, полностью оптимизированный для скорости, который часто намного длиннее и сложнее. С gcc -std=c11 -g -Os -mavx мы получаем это вместо:
factorial:
mov eax, 1
.L3:
cmp rdi, 1
jbe .L1
imul rax, rdi
dec rdi
jmp .L3
.L1:
ret
GCC достаточно умен, чтобы понять, что , потому что умножение ассоциативно и имеет тождество , (4 × (3 × (2 × 1))) = 1 × 4 × 3 × 2 × 1 Следовательно, он может хранить промежуточный итог продукта слева направо (4, затем 12, затем 24) и полностью исключить call. Этот код является просто узким циклом, почти идентичным тому, что вы получили бы, если бы написали цикл for на языке высокого уровня.
Если вы оптимизировали время вместо пробела с помощью -O3, GCC попытается векторизовать цикл в зависимости от того, присвоили ли вы ему флаг, такой как -mavx. Другие компиляторы при максимальной оптимизации развертывают цикл, но не используют векторные инструкции.
Clang 7.0.0 генерирует немного более быстрый код на одну инструкцию длиннее с теми же флагами, поскольку он знает достаточно, чтобы проверить, завершить ли цикл в конце, не вернуться назад и затем проверить в начале. Я бы предпочел этот код немного GCC.
factorial: # @factorial
mov eax, 1
cmp rdi, 2
jb .LBB0_2
.LBB0_1: # =>This Inner Loop Header: Depth=1
imul rax, rdi
dec rdi
cmp rdi, 1
ja .LBB0_1
.LBB0_2:
ret
MSVC 19.0 не может понять, применить ли это преобразование к этому коду, и все еще генерирует рекурсивный код с call, но мы можем дать ему подсказку путем рефакторинга и добавления явного параметра аккумулятора:
unsigned long long factorial_tail(const unsigned long long n,
const unsigned long long p)
/* The n parameter is the current value counted down, and the p parameter
* is the accumulating product. Call this function with an initial value
* of p = 1.
*/
{
return (n <= 1) ? p
: factorial_tail( n-1, n*p );
}
Эта версия явно хвостовая рекурсивная, и каждый современный компилятор знает об устранении хвостовых вызовов. Это компилируется с /Ox /arch:avx до:
factorial_tail PROC
mov rax, rdx
cmp rcx, 1
jbe SHORT $LN4@factorial_
mov rdx, rcx
imul rdx, rax
dec rcx
jmp factorial_tail
$LN4@factorial_:
ret 0
Вы наблюдаете в другом листинге кода: «то, что кажется избыточной операцией, когда результат умножения перемещается в локальную переменную из rax, а затем обратно в rax, прежде чем функция возвращается». Действительно, это происходит в каждом итерация цикла. Он не понимает, что, поставив уже запущенный продукт на rax, он может и должен просто оставить его там.
Компилятор Intel 19.0.1 aПоэтому я не могу сказать, что он может преобразовать factorial() в цикл, но он может сделать с factorial_tail().С -std=c11 -g -avT -Os это создает код лучше, чем MSVC и очень похож на clang:
factorial_tail:
cmp rdi, 1 #14.16
jbe ..B2.5 # Prob 12% #14.16
..B2.3: # Preds ..B2.1 ..B2.3
imul rsi, rdi #15.44
dec rdi #15.39
cmp rdi, 1 #14.16
ja ..B2.3 # Prob 88% #14.16
..B2.5: # Preds ..B2.3 ..B2.1
mov rax, rsi #14.16
ret
Он понимает, что следует избегать копирования значений из одного регистра в другой и обратно между итерациями цикла.Вместо этого он выбирает сохранить его в своем первоначальном расположении rsi (второй параметр функции) и перемещает возвращаемое значение в rax только один раз в конце.