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

Очень просто, что такое оптимизация хвостового вызова?

В частности, что это за небольшие фрагменты кода, где их можно применить, а где нет, с объяснением почему?

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

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 является вызовом функции г (Примечание: г может быть е ). Ключевым моментом здесь является то, что для 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)

Прежде всего, обратите внимание, что не все языки поддерживают это.

TCO применяется к особому случаю рекурсии. Суть этого в том, что если последнее, что вы делаете в функции, это сам вызов (например, он вызывает себя из позиции «хвоста»), то компилятор может оптимизировать его так, чтобы он действовал как итерация, а не как стандартная рекурсия.

Вы видите, что обычно во время рекурсии среда выполнения должна отслеживать все рекурсивные вызовы, чтобы при возврате он мог возобновиться при предыдущем вызове и так далее. (Попробуйте вручную выписать результат рекурсивного вызова, чтобы получить наглядное представление о том, как это работает.) Отслеживание всех вызовов занимает место, которое становится значительным, когда функция сама вызывает много. Но с TCO можно просто сказать: «вернитесь к началу, только на этот раз измените значения параметров на эти новые». Это может быть сделано, потому что ничто после рекурсивного вызова не ссылается на эти значения.

Пример минимального запуска GCC с анализом разборки 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 вверх по течению .

Скомпилируйте и разберите:

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.

Смотри сюда:

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

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

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

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

3. TCO может вызывать постоянно работающую функцию:

   void eternity()
   {
       eternity();
   }
   

У подхода с рекурсивной функцией есть проблема. Он создает стек вызовов размером O (n), что делает нашу общую стоимость памяти O (n). Это делает его уязвимым для ошибки переполнения стека, когда стек вызовов становится слишком большим и не хватает места.

Схема оптимизации Tail Call (TCO). Где он может оптимизировать рекурсивные функции, чтобы избежать создания большого стека вызовов и, следовательно, экономит стоимость памяти.

Есть много языков, которые делают TCO как (JavaScript, Ruby и немного C), тогда как Python и Java не делают TCO.

Язык JavaScript подтвержден с использованием :) http://2ality.com/2015/06/tail-call-optimization.html

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

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