Вопрос:

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

algorithm recursion language-agnostic tail-recursion tail-call-optimization

134857 просмотра

9 ответа

4652 Репутация автора

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

Автор: majelbstoat Источник Размещён: 22.11.2008 06:56

Ответы (9)


6 плюса

24022 Репутация автора

Смотри сюда:

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

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

Автор: BobbyShaftoe Размещён: 22.11.2008 07:05

655 плюса

60559 Репутация автора

Решение

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

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

Автор: Kyle Cronin Размещён: 22.11.2008 07:07

13 плюса

10021 Репутация автора

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

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

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

Автор: J Cooper Размещён: 22.11.2008 07:09

176 плюса

130633 Репутация автора

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

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

Автор: Claudiu Размещён: 22.11.2008 07:12

499 плюса

132612 Репутация автора

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

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

Автор: Christoph Размещён: 22.03.2012 12:04

4 плюса

79 Репутация автора

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

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

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

    void eternity()
    {
        eternity();
    }
    
Автор: grillSandwich Размещён: 20.08.2012 10:12

56 плюса

6455 Репутация автора

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

«Что, черт возьми, это: зов хвоста»

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

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

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)

Автор: btiernay Размещён: 26.08.2012 01:27

3 плюса

561 Репутация автора

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

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

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

Автор: Rupesh Kumar Tiwari Размещён: 30.07.2018 01:34

3 плюса

156721 Репутация автора

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

Автор: Ciro Santilli 新疆改造中心996ICU六四事件 Размещён: 18.03.2019 09:39
Вопросы из категории :
32x32