O que é otimização de chamada de cauda?

818

Muito simplesmente, o que é otimização de chamada de cauda?

Mais especificamente, quais são alguns pequenos trechos de código onde eles podem ser aplicados e onde não, com uma explicação do porquê?

majelbstoat
fonte
10
O TCO transforma uma chamada de função na posição de cauda em um goto, um salto.
Will Ness
8
Esta pergunta foi feita completamente 8 anos antes da pergunta;) #
majelbstoat

Respostas:

755

A otimização de chamada de cauda é onde você pode evitar a alocação de um novo quadro de pilha para uma função porque a função de chamada retornará simplesmente o valor que obtém da função chamada. O uso mais comum é a recursão de cauda, ​​onde uma função recursiva escrita para aproveitar a otimização de chamada de cauda pode usar espaço de pilha constante.

O Scheme é uma das poucas linguagens de programação que garantem na especificação que qualquer implementação deve fornecer essa otimização (o JavaScript também inicia no ES6) ; portanto, aqui estão dois exemplos da função fatorial no 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))

A primeira função não é recursiva de cauda porque, quando a chamada recursiva é feita, a função precisa acompanhar a multiplicação que precisa fazer com o resultado após o retorno da chamada. Como tal, a pilha tem a seguinte aparência:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

Por outro lado, o rastreamento da pilha para o fatorial recursivo da cauda é o seguinte:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

Como você pode ver, só precisamos acompanhar a mesma quantidade de dados para cada chamada à realidade, porque estamos simplesmente retornando o valor que atingimos até o topo. Isso significa que, mesmo que eu chame (fato 1000000), preciso apenas da mesma quantidade de espaço que (fato 3). Esse não é o caso do fato não recursivo de cauda e, como tais, valores grandes podem causar um estouro de pilha.

Kyle Cronin
fonte
99
Se você quiser aprender mais sobre isso, sugiro a leitura do primeiro capítulo da Estrutura e Interpretação de Programas de Computador.
Kyle Cronin
3
Ótima resposta, perfeitamente explicada.
Jonah
15
Estritamente falando, a otimização da chamada de cauda não substitui necessariamente o quadro da pilha do chamador pelas chamadas, mas garante que um número ilimitado de chamadas na posição de cauda exija apenas uma quantidade limitada de espaço. Veja o artigo de Will Clinger "Recursão adequada da cauda e eficiência de espaço": cesura17.net/~will/Professional/Research/Papers/tail.pdf
Jon Harrop
3
Essa é apenas uma maneira de escrever funções recursivas em um espaço constante? Porque você não conseguiu os mesmos resultados usando uma abordagem iterativa?
precisa saber é o seguinte
5
@ dclowd9901, o TCO permite que você prefira um estilo funcional em vez de um loop iterativo. Você pode preferir um estilo imperativo. Muitas linguagens (Java, Python) não fornecem TCO, então você precisa saber que uma chamada funcional custa memória ... e o estilo imperativo é o preferido.
Mvcive #
553

Vamos seguir um exemplo simples: a função fatorial implementada em C.

Começamos com a definição recursiva óbvia

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

Uma função termina com uma chamada final se a última operação antes do retorno da função for outra chamada de função. Se essa chamada chamar a mesma função, será recursiva da cauda.

Embora fac()pareça recursivo à primeira vista, não é como o que realmente acontece é

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

ou seja, a última operação é a multiplicação e não a chamada de função.

No entanto, é possível reescrever fac()para ser recursivo passando o valor acumulado na cadeia de chamadas como um argumento adicional e passando apenas o resultado final novamente como o valor de retorno:

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

Agora, por que isso é útil? Como retornamos imediatamente após a chamada final, podemos descartar o stackframe anterior antes de chamar a função na posição final ou, no caso de funções recursivas, reutilizar o stackframe como está.

A otimização de chamada de cauda transforma nosso código recursivo em

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

Isso pode ser incorporado fac()e chegamos a

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

que é equivalente a

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

Como podemos ver aqui, um otimizador suficientemente avançado pode substituir a recursão da cauda pela iteração, o que é muito mais eficiente, pois você evita a sobrecarga da chamada de função e usa apenas uma quantidade constante de espaço na pilha.

Christoph
fonte
você pode explicar o que significa um stackframe exatamente? Existe uma diferença entre a pilha de chamadas e o stackframe?
Shasak
10
@ Kasahs: um quadro de pilha é a parte da pilha de chamadas que 'pertence' a uma determinada função (ativa); cf en.wikipedia.org/wiki/Call_stack#Structure
Christoph
1
Eu só tinha epifania bastante intensa depois de ler este post depois de ler 2ality.com/2015/06/tail-call-optimization.html
agm1984
198

TCO (Otimização de chamada de cauda) é o processo pelo qual um compilador inteligente pode fazer uma chamada para uma função e não ocupa espaço adicional na pilha. A única situação em que isso ocorre é se a última instrução executada em uma função f for uma chamada para uma função g (Nota: g pode ser f ). A chave aqui é que f não precisa mais de espaço na pilha - simplesmente chama g e depois retorna o que g retornaria. Nesse caso, pode-se fazer a otimização de que g simplesmente roda e retorna qualquer valor que ele teria para a coisa chamada f.

Essa otimização pode fazer com que chamadas recursivas ocupem espaço constante na pilha, em vez de explodir.

Exemplo: esta função fatorial não é TCOptimizable:

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

Essa função faz outras coisas além de chamar outra função em sua declaração de retorno.

Esta função abaixo é 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)

Isso ocorre porque a última coisa que acontece em qualquer uma dessas funções é chamar outra função.

Claudiu
fonte
3
A coisa toda 'function g can be f' foi um pouco confusa, mas entendi o que você quer dizer e os exemplos realmente esclareceram as coisas. Muito obrigado!
Majelbstoat
10
Excelente exemplo que ilustra o conceito. Basta levar em consideração que o idioma escolhido deve implementar a eliminação da chamada final ou a otimização da chamada final. No exemplo, escrito em Python, se você digitar um valor de 1000, obtém um "RuntimeError: profundidade máxima de recursão excedida" porque a implementação padrão do Python não suporta a eliminação da recursão de cauda. Veja uma postagem do próprio Guido explicando por que isso é: neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html .
Rmcc #
"A única situação" é um pouco absoluta demais; há também TRMC , pelo menos em teoria, que otimizaria (cons a (foo b))ou (+ c (bar d))na posição da cauda da mesma maneira.
Will Ness
Eu gostei da sua abordagem eg melhor que a resposta aceita, talvez porque eu sou uma pessoa de matemática.
Nithin 5/10
Eu acho que você quer dizer TCOptimized. Dizendo que é infere não TCOptimizable que nunca pode ser otimizado (quando na verdade pode)
Jacques Mathieu
65

Provavelmente, a melhor descrição de alto nível que encontrei para chamadas de cauda, ​​chamadas de cauda recursivas e otimização de chamada de cauda é a postagem do blog

"O que diabos é: Uma chamada de cauda"

de Dan Sugalski. Na otimização de chamada de cauda, ​​ele escreve:

Considere, por um momento, esta função simples:

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

Então, o que você pode fazer, ou melhor, o seu compilador de idiomas? Bem, o que ele pode fazer é transformar o código do formulário return somefunc();na sequência de baixo nível pop stack frame; goto somefunc();. Em nosso exemplo, isso significa que, antes de chamarmos bar, se foolimpa e, em vez de chamar barcomo sub-rotina, fazemos uma gotooperação de baixo nível no início bar. Foojá se limpou da pilha, então, quando barinicia, parece com quem chamou foorealmente ligou bare quandobar retorna seu valor, ele o retorna diretamente para quem chamou foo, em vez de retornar para o fooque o retornaria ao chamador.

E na recursão da cauda:

A recursão da cauda ocorre se uma função, como sua última operação, retornar o resultado da chamada em si . A recursão da cauda é mais fácil de lidar, porque, em vez de ter que pular para o início de alguma função aleatória em algum lugar, basta voltar ao início de si mesmo, o que é uma coisa muito simples de se fazer.

Para que isso:

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }

é silenciosamente transformado em:

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }

O que eu gosto nessa descrição é o quão fácil e sucinto é entender para aqueles que têm um histórico imperativo de linguagem (C, C ++, Java)

btiernay
fonte
4
Erro 404. No entanto, ele ainda está disponível no archive.org: web.archive.org/web/20111030134120/http://www.sidhe.org/~dan/…
Tommy
Eu não entendi, a foochamada inicial da função não está otimizada? Ele está apenas chamando uma função como seu último passo, e está simplesmente retornando esse valor, certo?
Sexy Beast
1
@TryinHard talvez não seja o que você tinha em mente, mas eu o atualizei para dar uma ideia do que se trata. Desculpe, não vou repetir o artigo inteiro!
btiernay 10/09/2015
2
Obrigado, isso é mais simples e mais compreensível do que o mais up-votado exemplo esquema (para não mencionar, Scheme não é uma linguagem comum que a maioria dos desenvolvedores entender)
Sevin7
2
Como alguém que raramente mergulha em linguagens funcionais, é gratificante ver uma explicação em "meu dialeto". Há uma tendência (compreensível) para os programadores funcionais evangelizarem em seu idioma de escolha, mas, vindo do mundo imperativo, acho muito mais fácil entender uma resposta como essa.
James Beninger
15

Observe primeiro que nem todos os idiomas o suportam.

O TCO aplica-se a um caso especial de recursão. A essência disso é que, se a última coisa que você faz em uma função é chamada de si mesma (por exemplo, está se chamando da posição "tail"), isso pode ser otimizado pelo compilador para agir como iteração em vez de recursão padrão.

Você vê, normalmente durante a recursão, o tempo de execução precisa acompanhar todas as chamadas recursivas, para que, quando a pessoa retorne, possa retomar a chamada anterior e assim por diante. (Tente escrever manualmente o resultado de uma chamada recursiva para ter uma idéia visual de como isso funciona.) Manter o controle de todas as chamadas ocupa espaço, o que é significativo quando a função se chama muito. Mas com o TCO, ele pode apenas dizer "volte ao início, só que desta vez altere os valores dos parâmetros para esses novos". Isso é possível porque nada após a chamada recursiva se refere a esses valores.

J Cooper
fonte
3
As chamadas de cauda também podem ser aplicadas a funções não recursivas. Qualquer função cujo último cálculo antes de retornar seja uma chamada para outra função pode usar uma chamada final.
Brian
Não necessariamente verdadeiro, idioma por idioma - o compilador C # de 64 bits pode inserir opcodes finais, enquanto a versão de 32 bits não; e a versão do F # será compilada, mas a depuração do F # não será por padrão.
9139 Steve Gilham
3
"O TCO se aplica a um caso especial de recursão". Receio que isso esteja completamente errado. As chamadas de cauda se aplicam a qualquer chamada na posição de cauda. Geralmente discutido no contexto da recursão, mas na verdade nada especificamente relacionado à recursão.
Jon Harrop
@ Brian, veja o link @btiernay fornecido acima. A foochamada inicial do método não é otimizada?
Sexy Beast
13

Exemplo executável mínimo do GCC com análise de desmontagem x86

Vamos ver como o GCC pode fazer automaticamente otimizações de chamada de cauda para nós, observando o assembly gerado.

Isso servirá como um exemplo extremamente concreto do que foi mencionado em outras respostas, como https://stackoverflow.com/a/9814654/895245 que a otimização pode converter chamadas de função recursivas em um loop.

Por sua vez, economiza memória e melhora o desempenho, pois os acessos à memória costumam ser a principal coisa que torna os programas lentos atualmente. .

Como entrada, fornecemos ao GCC um fatorial não otimizado baseado em pilha:

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 .

Compilar e desmontar:

gcc -O1 -foptimize-sibling-calls -ggdb3 -std=c99 -Wall -Wextra -Wpedantic \
  -o tail_call.out tail_call.c
objdump -d tail_call.out

Onde -foptimize-sibling-callsé o nome da generalização de chamadas de cauda de acordo com man gcc:

   -foptimize-sibling-calls
       Optimize sibling and tail recursive calls.

       Enabled at levels -O2, -O3, -Os.

como mencionado em: Como verifico se o gcc está executando a otimização da recursão de cauda?

Eu escolho -O1porque:

  • a otimização não é feita com -O0 . Eu suspeito que isso ocorre porque faltam transformações intermediárias necessárias.
  • -O3 produz um código incrivelmente eficiente que não seria muito educativo, embora também seja otimizado.

Desmontagem com -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

Com -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

A principal diferença entre os dois é que:

  • os -fno-optimize-sibling-callsusos callq, que é a chamada de função não otimizada típica.

    Esta instrução envia o endereço de retorno para a pilha, aumentando-o.

    Além disso, esta versão também faz push %rbx, que empurra %rbxpara a pilha .

    O GCC faz isso porque armazena o ediqual é o primeiro argumento da função ( n) ebxe depois chama factorial.

    O GCC precisa fazer isso porque está se preparando para outra chamada para factorial, que usará o novo edi == n-1.

    Ele escolhe ebxporque este registro é salvo por chamada: O que os registros são preservados por meio de uma chamada de função x86-64 do linux, para que a sub- chamadafactorial não o altere e perca n.

  • o -foptimize-sibling-callsnão usa nenhuma instrução que empurre para a pilha: apenas gotosalta dentro factorialcom as instruções jee jne.

    Portanto, esta versão é equivalente a um loop while, sem nenhuma chamada de função. O uso da pilha é constante.

Testado no Ubuntu 18.10, GCC 8.2.

Ciro Santilli adicionou uma nova foto
fonte
6

Olhe aqui:

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

Como você provavelmente sabe, chamadas de função recursivas podem causar estragos em uma pilha; é fácil ficar rapidamente sem espaço na pilha. A otimização de chamada de cauda é a maneira pela qual você pode criar um algoritmo de estilo recursivo que utiliza espaço constante da pilha; portanto, ele não cresce e cresce e você recebe erros de pilha.

BobbyShaftoe
fonte
3
  1. Devemos garantir que não haja instruções goto na própria função. O cuidado pela chamada da função é a última coisa na função callee.

  2. Recursões em larga escala podem usar isso para otimizações, mas em pequena escala, a sobrecarga de instruções para fazer a chamada de função ser uma chamada final reduz o objetivo real.

  3. O TCO pode causar uma função de execução permanente:

    void eternity()
    {
        eternity();
    }
    
grillSandwich
fonte
3 ainda não foi otimizado. Essa é a representação não otimizada que o compilador transforma em código iterativo que usa espaço de pilha constante em vez de código recursivo. O TCO não é a causa do uso do esquema de recursão errado para uma estrutura de dados.
22/03/13
"O TCO não é a causa do uso do esquema de recursão errado para uma estrutura de dados". Por favor, elabore como isso é relevante para o caso em questão. O exemplo acima apenas indica que um exemplo dos quadros é alocado na pilha de chamadas com e sem TCO.
grillSandwich
Você optou por usar a recursão infundada para atravessar (). Isso não tinha nada a ver com o TCO. a eternidade é uma posição de chamada de cauda, ​​mas a posição de chamada de cauda não é necessária: anular a eternidade () {eternidade (); Saída(); }
nomen 24/03
Enquanto estamos nisso, o que é uma "recursão em larga escala"? Por que devemos evitar o goto na função? Isso não é necessário nem suficiente para permitir o TCO. E que instrução aérea? O ponto principal do TCO é que o compilador substitui a chamada de função na posição final por um goto.
nomen
O custo total de propriedade é otimizar o espaço usado na pilha de chamadas. Por recursão em larga escala, estou me referindo ao tamanho do quadro. Sempre que ocorre uma recursão, se eu precisar colocar um enorme quadro na pilha de chamadas acima da função de chamada, o TCO será mais útil e me permitirá mais níveis de recursão. Mas, se o tamanho do meu quadro for menor, eu posso ficar sem o TCO e ainda assim executar meu programa (não estou falando de recursão infinita aqui). Se você for deixado com saltar na função, a chamada "final" não é realmente chamada final e o TCO não é aplicável.
grillSandwich
3

A abordagem da função recursiva tem um problema. Ele cria uma pilha de chamadas do tamanho O (n), que faz com que nossa memória total custe O (n). Isso o torna vulnerável a um erro de estouro de pilha, em que a pilha de chamadas fica muito grande e fica sem espaço.

Esquema de otimização de chamada de cauda (TCO). Onde ele pode otimizar funções recursivas para evitar a criação de uma pilha alta de chamadas e, portanto, economiza o custo da memória.

Existem muitas linguagens que fazem TCO como (JavaScript, Ruby e poucos C), enquanto Python e Java não fazem TCO.

A linguagem JavaScript foi confirmada usando :) http://2ality.com/2015/06/tail-call-optimization.html

Rupesh Kumar Tiwari
fonte
0

Em uma linguagem funcional, a otimização da chamada de cauda é como se uma chamada de função pudesse retornar uma expressão parcialmente avaliada como resultado, que seria avaliada pelo chamador.

f x = g x

f 6 reduz para g 6. Portanto, se a implementação puder retornar g 6 como resultado e, em seguida, chamar essa expressão, ela salvará um quadro de pilha.

Além disso

f x = if c x then g x else h x.

Reduz para f 6 para g 6 ou h 6. Portanto, se a implementação avalia c 6 e descobre que é verdade, pode reduzir,

if true then g x else h x ---> g x

f x ---> h x

Um simples intérprete de otimização de chamada sem cauda pode se parecer com isso,

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

Um intérprete de otimização de chamada de cauda pode se parecer com isso,

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;
        }
    }
}
Peter Driscoll
fonte