Что такое оптимизация вызовов?
Очень просто, что такое оптимизация хвостового вызова? В частности, может ли кто-нибудь показать небольшие фрагменты кода, где его можно применить, а где нет, с объяснением почему?
8 ответов
При оптимизации хвостового вызова вы можете избежать выделения нового стекового фрейма для функции, потому что вызывающая функция просто возвратит значение, которое она получает из вызываемой функции. Самым распространенным применением является хвостовая рекурсия, где рекурсивная функция, написанная для использования преимуществ оптимизации хвостового вызова, может использовать пространство постоянного стека.
Scheme является одним из немногих языков программирования, которые в спецификации гарантируют, что любая реализация должна обеспечивать эту оптимизацию (JavaScript также делает, начиная с ES6), поэтому вот два примера факториальной функции в Scheme:
(define (fact x)
(if (= x 0) 1
(* x (fact (- x 1)))))
(define (fact x)
(define (fact-tail x accum)
(if (= x 0) accum
(fact-tail (- x 1) (* x accum))))
(fact-tail x 1))
Первая функция не является хвостовой рекурсивной, потому что, когда выполняется рекурсивный вызов, функция должна отслеживать умножение, которое необходимо выполнить с результатом после возврата вызова. Таким образом, стек выглядит следующим образом:
(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6
Напротив, трассировка стека для хвостового рекурсивного факториала выглядит следующим образом:
(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6
Как видите, нам нужно отслеживать только один и тот же объем данных для каждого вызова факт-хвоста, потому что мы просто возвращаем значение, которое мы получаем, вплоть до вершины. Это означает, что даже если бы мне пришлось звонить (факт 1000000), мне нужно только столько же места, сколько (факт 3). Это не относится к нерекурсивному факту, и такие большие значения могут вызвать переполнение стека.
Давайте рассмотрим простой пример: функция факториала, реализованная в C.
Начнем с очевидного рекурсивного определения
unsigned fac(unsigned n)
{
if (n < 2) return 1;
return n * fac(n - 1);
}
Функция заканчивается хвостовым вызовом, если последняя операция перед возвратом функции - это другой вызов функции. Если этот вызов вызывает ту же функцию, она является хвостовой рекурсивной.
Даже если fac() на первый взгляд выглядит хвостово-рекурсивным
unsigned fac(unsigned n)
{
if (n < 2) return 1;
unsigned acc = fac(n - 1);
return n * acc;
}
т.е. последняя операция - это умножение, а не вызов функции.
Тем не менее, можно переписать fac() быть рекурсивным, передавая накопленное значение по цепочке вызовов в качестве дополнительного аргумента и передавая только конечный результат снова в качестве возвращаемого значения:
unsigned fac(unsigned n)
{
return fac_tailrec(1, n);
}
unsigned fac_tailrec(unsigned acc, unsigned n)
{
if (n < 2) return acc;
return fac_tailrec(n * acc, n - 1);
}
Теперь, почему это полезно? Поскольку мы немедленно возвращаемся после хвостового вызова, мы можем отказаться от предыдущего стекового фрейма перед вызовом функции в хвостовой позиции или, в случае рекурсивных функций, повторно использовать стековый фрейм как есть.
Оптимизация хвостового вызова превращает наш рекурсивный код в
unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
if (n < 2) return acc;
acc = n * acc;
n = n - 1;
goto TOP;
}
Это может быть встроено в fac() и мы приходим к
unsigned fac(unsigned n)
{
unsigned acc = 1;
TOP:
if (n < 2) return acc;
acc = n * acc;
n = n - 1;
goto TOP;
}
что эквивалентно
unsigned fac(unsigned n)
{
unsigned acc = 1;
for (; n > 1; --n)
acc *= n;
return acc;
}
Как мы видим здесь, достаточно продвинутый оптимизатор может заменить хвостовую рекурсию итерацией, что гораздо более эффективно, поскольку вы избегаете накладных расходов на вызов функции и используете только постоянный объем стекового пространства.
TCO (Tail Call Optimization) - это процесс, с помощью которого умный компилятор может выполнять вызов функции и не занимать дополнительное пространство в стеке. Единственная ситуация, в которой это происходит, - это когда последняя инструкция, выполняемая в функции f, является вызовом функции g (Примечание: g может быть f). Ключевым моментом здесь является то, что для f больше не требуется место в стеке - он просто вызывает g и затем возвращает то, что вернул бы g. В этом случае можно сделать оптимизацию, так как g просто запускается и возвращает любое значение, которое оно будет иметь, для вещи, которая называется f.
Эта оптимизация может заставить рекурсивные вызовы занимать постоянное место в стеке, а не взрываться.
Пример: эта факториальная функция не TCOptimizable:
def fact(n):
if n == 0:
return 1
return n * fact(n-1)
Эта функция делает что-то кроме вызова другой функции в своем операторе возврата.
Эта функция ниже TCOptimizable:
def fact_h(n, acc):
if n == 0:
return acc
return fact_h(n-1, acc*n)
def fact(n):
return fact_h(n, 1)
Это потому, что последнее, что должно произойти в любой из этих функций, - это вызвать другую функцию.
Вероятно, лучшее описание высокого уровня, которое я нашел для оконечных вызовов, рекурсивных оконечных вызовов и оптимизации оконечных вызовов, - это сообщение в блоге.
Дэн Сугальски. При оптимизации хвостового вызова он пишет:
Рассмотрим на мгновение эту простую функцию:
sub foo (int a) { a += 15; return bar(a); }Итак, что вы можете сделать, или, скорее, ваш языковой компилятор? Ну, что он может сделать, это код поворота формы
return somefunc();в последовательность низкого уровняpop stack frame; goto somefunc();, В нашем примере это означает, что прежде чем мы позвонимbar,fooубирается и потом, а не звонитbarв качестве подпрограммы, мы делаем низкий уровеньgotoоперация к началуbar,Fooуже вычистил себя из стека, поэтому, когдаbarначинается это выглядит как кто-то звонилfooдействительно звонилbar, и когдаbarвозвращает его значение, оно возвращает его непосредственно тому, кто вызвалfooвместо того, чтобы вернуть егоfooкоторый затем вернул бы его вызывающему.
И на хвостовой рекурсии:
Хвостовая рекурсия происходит, если функция, как ее последняя операция, возвращает результат вызова самой себя. С рекурсией хвоста легче иметь дело, потому что вместо того, чтобы переходить к началу какой-то случайной функции где-то, вы просто возвращаетесь к началу себя, что чертовски просто сделать.
Так что это:
sub foo (int a, int b) { if (b == 1) { return a; } else { return foo(a*a + a, b - 1); }
тихо превращается в:
sub foo (int a, int b) { label: if (b == 1) { return a; } else { a = a*a + a; b = b - 1; goto label; }
Что мне нравится в этом описании, так это то, насколько лаконичным и легким он может быть для тех, кто пришел из императивного языка (C, C++, Java)
Пример минимального запуска GCC с анализом разборки x86
Давайте посмотрим, как GCC может автоматически выполнять оптимизацию хвостовых вызовов для нас, посмотрев на сгенерированную сборку.
Это послужит чрезвычайно конкретным примером того, что было упомянуто в других ответах, таких как /questions/32095727/chto-takoe-optimizatsiya-vyizovov/32095749#32095749 что оптимизация может преобразовывать рекурсивные вызовы функций в цикл.
Это, в свою очередь, экономит память и повышает производительность, поскольку доступ к памяти часто является основным фактором, замедляющим работу программ в наше время.
В качестве входных данных мы даем GCC неоптимизированный факториал на основе наивного стека:
tail_call.c
#include <stdio.h>
#include <stdlib.h>
unsigned factorial(unsigned n) {
if (n == 1) {
return 1;
}
return n * factorial(n - 1);
}
int main(int argc, char **argv) {
int input;
if (argc > 1) {
input = strtoul(argv[1], NULL, 0);
} else {
input = 5;
}
printf("%u\n", factorial(input));
return EXIT_SUCCESS;
}
Скомпилируйте и разберите:
gcc -O1 -foptimize-sibling-calls -ggdb3 -std=c99 -Wall -Wextra -Wpedantic \
-o tail_call.out tail_call.c
objdump -d tail_call.out
где -foptimize-sibling-calls имя обобщения хвостовых вызовов в соответствии с man gcc:
-foptimize-sibling-calls
Optimize sibling and tail recursive calls.
Enabled at levels -O2, -O3, -Os.
как упомянуто в: Как я проверяю, выполняет ли gcc оптимизацию хвостовой рекурсии?
я выбираю -O1 так как:
- оптимизация не выполняется с
-O0, Я подозреваю, что это потому, что отсутствуют необходимые промежуточные преобразования. -O3создает нечестиво эффективный код, который не будет очень познавательным, хотя он также оптимизирован с помощью хвостового вызова.
Разборка с -fno-optimize-sibling-calls:
0000000000001145 <factorial>:
1145: 89 f8 mov %edi,%eax
1147: 83 ff 01 cmp $0x1,%edi
114a: 74 10 je 115c <factorial+0x17>
114c: 53 push %rbx
114d: 89 fb mov %edi,%ebx
114f: 8d 7f ff lea -0x1(%rdi),%edi
1152: e8 ee ff ff ff callq 1145 <factorial>
1157: 0f af c3 imul %ebx,%eax
115a: 5b pop %rbx
115b: c3 retq
115c: c3 retq
С -foptimize-sibling-calls:
0000000000001145 <factorial>:
1145: b8 01 00 00 00 mov $0x1,%eax
114a: 83 ff 01 cmp $0x1,%edi
114d: 74 0e je 115d <factorial+0x18>
114f: 8d 57 ff lea -0x1(%rdi),%edx
1152: 0f af c7 imul %edi,%eax
1155: 89 d7 mov %edx,%edi
1157: 83 fa 01 cmp $0x1,%edx
115a: 75 f3 jne 114f <factorial+0xa>
115c: c3 retq
115d: 89 f8 mov %edi,%eax
115f: c3 retq
Основное различие между ними заключается в том, что:
-fno-optimize-sibling-callsиспользованияcallq, который является типичным неоптимизированным вызовом функции.Эта инструкция помещает адрес возврата в стек, увеличивая его.
Кроме того, эта версия также делает
push %rbx, который толкает%rbxв стек.GCC делает это, потому что хранит
edi, который является первым аргументом функции (n) вebxзатем звонитfactorial,GCC должен сделать это, потому что он готовится к другому вызову
factorial, который будет использовать новыйedi == n-1,Выбирает
ebxпотому что этот регистр сохранен вызываемым пользователем: какие регистры сохраняются с помощью вызова функции linux x86-64, поэтомуfactorialне изменится и не потеряетn,-foptimize-sibling-callsне использует какие-либо инструкции, которые толкают в стек: он только делаетgotoпрыгает вfactorialс инструкциямиjeа такжеjne,Следовательно, эта версия эквивалентна циклу while без каких-либо вызовов функций. Использование стека постоянно.
Протестировано в Ubuntu 18.10, GCC 8.2.
Прежде всего обратите внимание, что не все языки поддерживают это.
TCO применяется к особому случаю рекурсии. Суть этого в том, что если последнее, что вы делаете в функции, это сам вызов (например, он вызывает себя из позиции "хвоста"), то компилятор может оптимизировать его так, чтобы он действовал как итерация, а не как стандартная рекурсия.
Вы видите, что обычно во время рекурсии среда выполнения должна отслеживать все рекурсивные вызовы, чтобы при возврате он мог возобновить работу при предыдущем вызове и так далее. (Попробуйте вручную выписать результат рекурсивного вызова, чтобы получить наглядное представление о том, как это работает.) Отслеживание всех вызовов занимает место, которое становится значительным, когда функция сама вызывает много. Но с TCO можно просто сказать: "вернитесь к началу, только на этот раз измените значения параметров на эти новые". Это может быть сделано, потому что ничто после рекурсивного вызова не ссылается на эти значения.
Смотри сюда:
http://tratt.net/laurie/tech_articles/articles/tail_call_optimization
Как вы, вероятно, знаете, рекурсивные вызовы функций могут нанести ущерб стеку; легко быстро исчерпать пространство стека. Оптимизация вызова хвоста - это способ, с помощью которого вы можете создать алгоритм рекурсивного стиля, который использует постоянное пространство стека, поэтому он не растет и не растет, и вы получаете ошибки стека.
У рекурсивного функционального подхода есть проблема. Он создает стек вызовов размером O(n), что делает нашу общую стоимость памяти O(n). Это делает его уязвимым для ошибки переполнения стека, когда стек вызовов становится слишком большим и не хватает места. Схема оптимизации стоимости хвоста (TCO). Где он может оптимизировать рекурсивные функции, чтобы избежать создания большого стека вызовов и, следовательно, экономит стоимость памяти.
Есть много языков, которые делают TCO, как (Javascript, Ruby и несколько C), где Python и Java не делают TCO.
Язык JavaScript подтвержден с использованием:) http://2ality.com/2015/06/tail-call-optimization.html
Мы должны убедиться, что в самой функции нет операторов goto... позаботились о том, чтобы вызов функции был последним в функции вызываемого.
Крупномасштабные рекурсии могут использовать это для оптимизации, но в небольшом масштабе накладные расходы на инструкции для вызова функции хвостовым вызовом уменьшают фактическую цель.
TCO может вызвать вечно работающую функцию:
void eternity() { eternity(); }
На функциональном языке оптимизация хвостового вызова выглядит так, как если бы вызов функции мог вернуть частично оцененное выражение в качестве результата, которое затем будет оценено вызывающим.
f x = g x
f 6 сокращается до g 6. Итак, если реализация могла бы вернуть g 6 в качестве результата, а затем вызвать это выражение, она сохранит кадр стека.
Также
f x = if c x then g x else h x.
Уменьшается до f 6 либо до g 6, либо до h 6. Таким образом, если реализация оценивает c 6 и находит, что это правда, то она может уменьшить,
if true then g x else h x ---> g x
f x ---> h x
Простой интерпретатор оптимизации без хвостового вызова может выглядеть так:
class simple_expresion
{
...
public:
virtual ximple_value *DoEvaluate() const = 0;
};
class simple_value
{
...
};
class simple_function : public simple_expresion
{
...
private:
simple_expresion *m_Function;
simple_expresion *m_Parameter;
public:
virtual simple_value *DoEvaluate() const
{
vector<simple_expresion *> parameterList;
parameterList->push_back(m_Parameter);
return m_Function->Call(parameterList);
}
};
class simple_if : public simple_function
{
private:
simple_expresion *m_Condition;
simple_expresion *m_Positive;
simple_expresion *m_Negative;
public:
simple_value *DoEvaluate() const
{
if (m_Condition.DoEvaluate()->IsTrue())
{
return m_Positive.DoEvaluate();
}
else
{
return m_Negative.DoEvaluate();
}
}
}
Интерпретатор оптимизации хвостового вызова может выглядеть так:
class tco_expresion
{
...
public:
virtual tco_expresion *DoEvaluate() const = 0;
virtual bool IsValue()
{
return false;
}
};
class tco_value
{
...
public:
virtual bool IsValue()
{
return true;
}
};
class tco_function : public tco_expresion
{
...
private:
tco_expresion *m_Function;
tco_expresion *m_Parameter;
public:
virtual tco_expression *DoEvaluate() const
{
vector< tco_expression *> parameterList;
tco_expression *function = const_cast<SNI_Function *>(this);
while (!function->IsValue())
{
function = function->DoCall(parameterList);
}
return function;
}
tco_expresion *DoCall(vector<tco_expresion *> &p_ParameterList)
{
p_ParameterList.push_back(m_Parameter);
return m_Function;
}
};
class tco_if : public tco_function
{
private:
tco_expresion *m_Condition;
tco_expresion *m_Positive;
tco_expresion *m_Negative;
tco_expresion *DoEvaluate() const
{
if (m_Condition.DoEvaluate()->IsTrue())
{
return m_Positive;
}
else
{
return m_Negative;
}
}
}