Что такое оптимизация хвостового вызова?

Оптимизация хвостового вызова - это когда вы можете избежать выделения нового кадра стека для функции, потому что вызывающая функция просто вернет значение, которое она получает от вызываемой функции. Чаще всего используется хвостовая рекурсия, когда рекурсивная функция, написанная для использования преимуществ оптимизации хвостового вызова, может использовать постоянное пространство стека.

Scheme - один из немногих языков программирования, которые гарантируют в спецификации, что любая реализация должна обеспечивать эту оптимизацию, поэтому вот два примера факториальной функции в 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

Как видите, нам нужно отслеживать только один и тот же объем данных для каждого вызова fact-tail, потому что мы просто возвращаем полученное значение прямо наверх. Это означает, что даже если бы я позвонил (факт 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 (оптимизация хвостового вызова) - это процесс, с помощью которого умный компилятор может вызвать функцию и не использовать дополнительное пространство стека. Это происходит только в том случае, если последняя инструкция, выполненная в функции f, является вызовом функции g (примечание: g может быть f). Ключевым моментом здесь является то, что f больше не требует места в стеке - он просто вызывает g, а затем возвращает все, что вернет g. В этом случае оптимизация может быть сделана так, что g просто запускается и возвращает любое значение, которое у него было бы, тому, что вызвало f.

Эта оптимизация может заставить рекурсивные вызовы занимать постоянное пространство стека, а не взрываться.

Пример: эта факториальная функция не оптимизируется по совокупной стоимости владения:

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

Эта функция делает что-то помимо вызова другой функции в своем операторе возврата.

Эта функция ниже может быть оптимизирована по совокупной стоимости владения:

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)

Это потому, что последнее, что нужно сделать в любой из этих функций, - это вызвать другую функцию.

Вероятно, лучшее описание высокого уровня, которое я нашел для хвостовых вызовов, рекурсивных хвостовых вызовов и оптимизации хвостовых вызовов, - это сообщение в блоге

«Какого черта это: хвостовой сигнал "

пользователя Dan Sugalski. Об оптимизации хвостового вызова он пишет:

Рассмотрим на мгновение эту простую функцию:

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 C с анализом дизассемблирования x86

Давайте посмотрим, как GCC может автоматически выполнять оптимизацию хвостовых вызовов за нас, посмотрев на сгенерированную сборку.

Это будет очень конкретным примером того, что было упомянуто в других ответах, таких как https://stackoverflow.com/a/9814654/895245, что оптимизация может преобразовывать рекурсивные вызовы функций в цикл.

Это, в свою очередь, экономит память и повышает производительность, поскольку доступ к памяти часто является главным фактором, замедляющим работу программ в настоящее время.

В качестве входных данных мы передаем 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;
}

GitHub upstream.

Скомпилировать и разобрать:

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

1. Мы должны убедиться, что в самой функции нет операторов goto ... позаботьтесь о том, чтобы вызов функции был последним в вызываемой функции.

2. В крупномасштабных рекурсиях это можно использовать для оптимизации, но в малых масштабах накладные расходы на инструкции по превращению вызова функции в хвостовой вызов уменьшают фактическую цель.

3. 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;
        }
    }
}