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

Question

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

Answer 1

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

Схема является один из немногих языков программирования, которые гарантируют в спецификации, что любая реализация должна обеспечить такую ​​оптимизацию (JavaScript будет также после того, как ES6 финализации), поэтому здесь два примера функции факториала на схеме:

(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

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

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

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

Answer 3

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

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

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

Answer 4

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

Пройдет через простой пример: факторная функция реализованы в С.

Начнут с очевидным рекурсивным определением

unsigned fac(unsigned n) 
{ 
    if (n < 2) return 1; 
    return n * fac(n - 1); 
} 

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

Даже если 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; 
} 

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

Answer 6

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

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

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

   void eternity() 
   { 
       eternity(); 
   } 
   

Answer 7

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

"What the heck is: A tail call"

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

Consider, for a moment, this simple function:

sub foo (int a) { 
    a += 15; 
    return bar(a); 
} 

So, what can you, or rather your language compiler, do? Well, what it can do is turn code of the form return somefunc(); into the low-level sequence pop stack frame; goto somefunc(); . In our example, that means before we call bar , foo cleans itself up and then, rather than calling bar as a subroutine, we do a low-level goto operation to the start of bar . Foo 's already cleaned itself out of the stack, so when bar starts it looks like whoever called foo has really called bar , and when bar returns its value, it returns it directly to whoever called foo , rather than returning it to foo which would then return it to its caller.

А на хвосте рекурсии:

Tail recursion happens if a function, as its last operation, returns the result of calling itself. Tail recursion is easier to deal with because rather than having to jump to the beginning of some random function somewhere, you just do a goto back to the beginning of yourself, which is a darned simple thing to do.

таким образом, что это:

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)