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

Question

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

Answer 1

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

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). Это не относится к нерекурсивному факту, и такие большие значения могут вызвать переполнение стека.

Answer 2

Давайте рассмотрим простой пример: функция факториала, реализованная в 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;
}

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

Answer 3

TCO (Tail Call Optimization) - это процесс, с помощью которого умный компилятор может вызывать функцию и не занимать дополнительное пространство в стеке. Единственная ситуация , в которой это происходит, - это когда последняя инструкция, выполняемая в функции f , является вызовом функции g (Примечание: g может быть е ). Ключевым моментом здесь является то, что 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)

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

Answer 4

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

«Что за чертовщина? Хвост»

Дэн Сугальски. При оптимизации хвостового вызова он пишет:

Подумайте на минуту об этой простой функции:

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)

Answer 5

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

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

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

Answer 6

Смотрите здесь:

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

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

Answer 7

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

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

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

   void eternity()
   {
       eternity();
   }
   

Answer 8

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

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

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

Answer 9

Пример минимального запуска 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 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.