¿Qué es la optimización de llamadas de cola?

819

Muy simple, ¿qué es la optimización de llamadas de cola?

Más específicamente, ¿cuáles son algunos pequeños fragmentos de código en los que se podría aplicar y, en caso contrario, con una explicación de por qué?

majelbstoat
fuente
10
TCO convierte una llamada de función en posición de cola en un goto, un salto.
Will Ness
8
Esta pregunta se hizo completamente 8 años antes de esa;)
majelbstoat

Respuestas:

756

La optimización de llamada de cola es donde puede evitar asignar un nuevo marco de pila para una función porque la función de llamada simplemente devolverá el valor que obtiene de la función llamada. El uso más común es la recursividad de cola, donde una función recursiva escrita para aprovechar la optimización de llamada de cola puede usar espacio de pila constante.

Scheme es uno de los pocos lenguajes de programación que garantiza en la especificación que cualquier implementación debe proporcionar esta optimización (JavaScript también lo hace, comenzando con ES6) , así que aquí hay dos ejemplos de la función factorial en 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))

La primera función no es recursiva de cola porque cuando se realiza la llamada recursiva, la función necesita realizar un seguimiento de la multiplicación que necesita hacer con el resultado después de que la llamada regresa. Como tal, la pila tiene el siguiente aspecto:

(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 el contrario, el seguimiento de la pila para el factor recursivo de cola se ve de la siguiente manera:

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

Como puede ver, solo necesitamos hacer un seguimiento de la misma cantidad de datos para cada llamada a la cola de hechos porque simplemente estamos devolviendo el valor que obtenemos a la cima. Esto significa que incluso si tuviera que llamar (hecho 1000000), solo necesito la misma cantidad de espacio que (hecho 3). Este no es el caso con el hecho no recursivo de la cola, y como tales valores grandes pueden causar un desbordamiento de la pila.

Kyle Cronin
fuente
99
Si desea obtener más información al respecto, le sugiero que lea el primer capítulo de Estructura e interpretación de programas de computadora.
Kyle Cronin
3
Gran respuesta, perfectamente explicada.
Jonás
15
Estrictamente hablando, la optimización de llamadas de cola no reemplaza necesariamente el marco de pila de la persona que llama con las llamadas, sino que garantiza que un número ilimitado de llamadas en posición de cola requiere solo una cantidad limitada de espacio. Vea el artículo de Will Clinger " Recurrencia
Jon Harrop
3
¿Es esta solo una forma de escribir funciones recursivas en una forma de espacio constante? ¿Porque no podrías lograr los mismos resultados usando un enfoque iterativo?
dclowd9901
55
@ dclowd9901, TCO le permite preferir un estilo funcional en lugar de un bucle iterativo. Puedes preferir el estilo imperativo. Muchos lenguajes (Java, Python) no proporcionan TCO, entonces debe saber que una llamada funcional cuesta memoria ... y se prefiere el estilo imperativo.
mcoolive
553

Veamos un ejemplo simple: la función factorial implementada en C.

Comenzamos con la definición recursiva obvia

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

Una función termina con una llamada de cola si la última operación antes de que la función regrese es otra llamada de función. Si esta llamada invoca la misma función, es recursiva de cola.

A pesar fac()de que a primera vista parece recursiva, no es que lo que realmente sucede es

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

es decir, la última operación es la multiplicación y no la llamada a la función.

Sin embargo, es posible reescribir fac()para ser recursivo de cola pasando el valor acumulado hacia abajo en la cadena de llamadas como un argumento adicional y pasando solo el resultado final nuevamente como el 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);
}

Ahora, ¿por qué es útil? Como volvemos inmediatamente después de la llamada de cola, podemos descartar el stackframe anterior antes de invocar la función en posición de cola o, en caso de funciones recursivas, reutilizar el stackframe tal cual.

La optimización de llamada de cola transforma nuestro código recursivo en

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

Esto se puede incorporar fac()y llegamos a

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

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

que es equivalente a

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

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

    return acc;
}

Como podemos ver aquí, un optimizador suficientemente avanzado puede reemplazar la recursividad de cola con iteración, lo cual es mucho más eficiente ya que evita la sobrecarga de llamadas de función y solo usa una cantidad constante de espacio de pila.

Christoph
fuente
¿Puedes explicar qué significa un stackframe exactamente? ¿Hay alguna diferencia entre la pila de llamadas y el stackframe?
Shasak
11
@Kasahs: un marco de pila es la parte de la pila de llamadas que 'pertenece' a una función (activa) dada; cf en.wikipedia.org/wiki/Call_stack#Structure
Christoph
1
Acabo de tener una epifanía bastante intensa después de leer esta publicación después de leer 2ality.com/2015/06/tail-call-optimization.html
agm1984
199

TCO (Tail Call Optimization) es el proceso mediante el cual un compilador inteligente puede realizar una llamada a una función y no ocupa espacio adicional en la pila. La única situación en la que esto sucede es si la última instrucción ejecutada en una función f es una llamada a una función g (Nota: g puede ser f ). La clave aquí es que f ya no necesita espacio en la pila: simplemente llama a gy luego devuelve lo que g devolvería. En este caso, se puede hacer la optimización de que g simplemente se ejecuta y devuelve cualquier valor que tenga para lo que se llama f.

Esta optimización puede hacer que las llamadas recursivas tomen un espacio de pila constante, en lugar de explotar.

Ejemplo: esta función factorial no es TCOptimizable:

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

Esta función hace cosas además de llamar a otra función en su declaración de retorno.

La siguiente función es 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)

Esto se debe a que lo último que sucede en cualquiera de estas funciones es llamar a otra función.

Claudiu
fuente
3
Todo el asunto 'función g puede ser f' fue un poco confuso, pero entiendo lo que quieres decir, y los ejemplos realmente aclararon las cosas. ¡Muchas gracias!
majelbstoat
10
Excelente ejemplo que ilustra el concepto. Solo tenga en cuenta que el idioma que elija tiene que implementar la eliminación de la cola o la optimización de la cola. En el ejemplo, escrito en Python, si ingresa un valor de 1000, obtiene un "RuntimeError: profundidad de recursión máxima excedida" porque la implementación predeterminada de Python no admite la eliminación de recursión de cola. Vea una publicación del propio Guido explicando por qué eso es: neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html .
rmcc
"La única situación" es demasiado absoluta; También hay TRMC , al menos en teoría, que optimizaría (cons a (foo b))o (+ c (bar d))en posición de cola de la misma manera.
Will Ness
Me gustó su enfoque f y g mejor que la respuesta aceptada, tal vez porque soy una persona de matemáticas.
Nithin
Creo que te refieres a TCOptimized. Al decir que no es TCOptimizable, se infiere que nunca se puede optimizar (cuando de hecho se puede)
Jacques Mathieu
65

Probablemente la mejor descripción de alto nivel que he encontrado para llamadas de cola, llamadas de cola recursivas y optimización de llamadas de cola es la publicación del blog

"Qué diablos es: una llamada de cola"

por Dan Sugalski. Sobre la optimización de la llamada de cola, escribe:

Considere, por un momento, esta función simple:

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

Entonces, ¿qué puedes hacer tú, o más bien tu compilador de idiomas? Bueno, lo que puede hacer es convertir el código del formulario return somefunc();en la secuencia de bajo nivel pop stack frame; goto somefunc();. En nuestro ejemplo, eso significa que antes de llamar bar, se foolimpia y luego, en lugar de llamar barcomo una subrutina, hacemos una gotooperación de bajo nivel al comienzo de bar. FooYa se ha limpiado de la pila, por lo que cuando barcomienza parece que quien llamó foorealmente ha llamado bar, y cuando bardevuelve su valor, lo devuelve directamente a quien llamó foo, en lugar de devolverlo a fooquien luego lo devolvería a su interlocutor.

Y en la recursividad de la cola:

La recursión de cola ocurre si una función, como su última operación, devuelve el resultado de llamarse a sí misma . La recursión de la cola es más fácil de manejar porque, en lugar de tener que saltar al comienzo de alguna función aleatoria en algún lugar, simplemente debes volver al principio de ti mismo, lo cual es algo muy simple.

Para que esto:

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

se convierte silenciosamente en:

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

Lo que me gusta de esta descripción es lo sucinto y fácil que es comprender a aquellos que provienen de un entorno de lenguaje imperativo (C, C ++, Java)

btiernay
fuente
44
error 404. Sin embargo, todavía está disponible en archive.org: web.archive.org/web/20111030134120/http://www.sidhe.org/~dan/…
Tommy
No lo entendí, ¿la foofunción inicial no está optimizada? Solo está llamando a una función como su último paso, y simplemente está devolviendo ese valor, ¿verdad?
SexyBeast
1
@ TryinHard tal vez no sea lo que tenía en mente, pero lo actualicé para dar una idea de lo que se trata. Lo siento, no voy a repetir todo el artículo!
btiernay
2
Gracias, esto es más simple y más comprensible que el ejemplo de esquema más votado (sin mencionar que Scheme no es un lenguaje común que la mayoría de los desarrolladores entienden)
Sevin7
2
Como alguien que rara vez se sumerge en lenguajes funcionales, es gratificante ver una explicación en "mi dialecto". Hay una tendencia (comprensible) para que los programadores funcionales evangelicen en su idioma de elección, pero viniendo del mundo imperativo me resulta mucho más fácil entender una respuesta como esta.
James Beninger
15

Tenga en cuenta en primer lugar que no todos los idiomas lo admiten.

El TCO se aplica a un caso especial de recursión. Lo esencial es que, si lo último que hace en una función es llamarse a sí mismo (por ejemplo, se llama a sí mismo desde la posición de "cola"), esto puede ser optimizado por el compilador para actuar como iteración en lugar de recursión estándar.

Verá, normalmente durante la recursividad, el tiempo de ejecución necesita realizar un seguimiento de todas las llamadas recursivas, de modo que cuando uno regrese pueda reanudarse en la llamada anterior, y así sucesivamente. (Intente escribir manualmente el resultado de una llamada recursiva para tener una idea visual de cómo funciona). Hacer un seguimiento de todas las llamadas ocupa espacio, lo que se vuelve significativo cuando la función se llama mucho a sí misma. Pero con TCO, solo puede decir "volver al principio, solo que esta vez cambiar los valores de los parámetros a estos nuevos". Puede hacerlo porque nada después de la llamada recursiva se refiere a esos valores.

J Cooper
fuente
3
Las llamadas de cola también pueden aplicarse a funciones no recursivas. Cualquier función cuyo último cálculo antes de regresar es una llamada a otra función puede usar una llamada de cola.
Brian
No necesariamente es cierto idioma por idioma: el compilador de C # de 64 bits puede insertar códigos de cola, mientras que la versión de 32 bits no lo hará; y F # versión build lo hará, pero F # debug no lo hará por defecto.
Steve Gilham el
3
"TCO se aplica a un caso especial de recursión". Me temo que eso está completamente mal. Las llamadas de cola se aplican a cualquier llamada en posición de cola. Comúnmente discutido en el contexto de la recursión, pero en realidad no tiene nada que ver específicamente con la recursividad.
Jon Harrop
@Brian, mira el enlace @btiernay provisto arriba. ¿El foométodo inicial no está optimizado?
SexyBeast
13

Ejemplo de ejecución mínima de GCC con análisis de desmontaje x86

Veamos cómo GCC puede hacer automáticamente las optimizaciones de llamadas de cola mirando el ensamblaje generado.

Esto servirá como un ejemplo extremadamente concreto de lo que se mencionó en otras respuestas como https://stackoverflow.com/a/9814654/895245 de que la optimización puede convertir las llamadas de funciones recursivas en un bucle.

Esto a su vez ahorra memoria y mejora el rendimiento, ya que los accesos a la memoria son a menudo lo principal que hace que los programas sean lentos hoy en día .

Como entrada, le damos a GCC un factorial basado en una pila ingenua no optimizada:

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 aguas arriba .

Compilar y desmontar:

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

donde -foptimize-sibling-callses el nombre de generalización de las llamadas de cola de acuerdo con man gcc:

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

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

como se menciona en: ¿Cómo verifico si gcc está realizando la optimización de recursión de cola?

Elijo -O1porque:

  • la optimización no se realiza con -O0. Sospecho que esto se debe a que faltan las transformaciones intermedias requeridas.
  • -O3 produce un código impío y eficiente que no sería muy educativo, aunque también está optimizado.

Desmontaje con -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

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

La diferencia clave entre los dos es que:

  • los -fno-optimize-sibling-callsusos callq, que es la llamada de función típica no optimizada.

    Esta instrucción empuja la dirección de retorno a la pila, por lo tanto, la aumenta.

    Además, esta versión también lo hace push %rbx, lo que empuja %rbxa la pila .

    GCC hace esto porque almacena edi, que es el primer argumento de función ( n) ebx, luego llama factorial.

    GCC necesita hacer esto porque se está preparando para otra llamada a factorial, que utilizará la nueva edi == n-1.

    Elige ebxporque este registro está guardado por la persona que llama: los registros se conservan a través de una llamada a la función linux x86-64 para que la llamada secundaria a factorialno lo cambie y pierda n.

  • el -foptimize-sibling-callsno utiliza ningún instrucciones que empujan a la pila: sólo lo hace gotosalta dentro factorialde las instrucciones jey jne.

    Por lo tanto, esta versión es equivalente a un ciclo while, sin ninguna llamada a la función. El uso de la pila es constante.

Probado en Ubuntu 18.10, GCC 8.2.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
fuente
7

Mira aquí:

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

Como probablemente sepa, las llamadas a funciones recursivas pueden causar estragos en una pila; Es fácil quedarse rápidamente sin espacio de pila. La optimización de llamadas de cola es la forma en que puede crear un algoritmo de estilo recursivo que utiliza espacio de pila constante, por lo tanto, no crece y crece y obtiene errores de pila.

BobbyShaftoe
fuente
3
  1. Deberíamos asegurarnos de que no haya declaraciones de goto en la función en sí misma. Cuidamos que la llamada a la función sea lo último en la función de llamada.

  2. Las recursiones a gran escala pueden usar esto para optimizaciones, pero en pequeña escala, la sobrecarga de instrucciones para hacer que la función llame una llamada de cola reduce el propósito real.

  3. El TCO puede causar una función que se ejecuta para siempre:

    void eternity()
    {
        eternity();
    }
    
sándwich
fuente
3 aún no se ha optimizado. Esa es la representación no optimizada que el compilador transforma en código iterativo que utiliza espacio de pila constante en lugar de código recursivo. El TCO no es la causa del uso del esquema de recursión incorrecto para una estructura de datos.
nomen
"El costo total de propiedad no es la causa del uso del esquema de recursión incorrecto para una estructura de datos". Explique cómo esto es relevante para el caso dado. El ejemplo anterior solo señala un ejemplo de los marcos asignados en la pila de llamadas con y sin TCO.
grillSandwich
Decidió utilizar la recursión infundada para atravesar (). Eso no tuvo nada que ver con el TCO. La eternidad pasa a ser la posición de cola, pero la posición de cola no es necesaria: anular eternity () {eternity (); salida(); }
nomen
Mientras estamos en eso, ¿qué es una "recursión a gran escala"? ¿Por qué debemos evitar los goto's en la función? Esto no es necesario ni suficiente para permitir el TCO. ¿Y qué instrucciones sobrecarga? El objetivo de TCO es que el compilador reemplaza la llamada de función en posición de cola por un goto.
nomen
TCO se trata de optimizar el espacio utilizado en la pila de llamadas. Por recursión a gran escala, me refiero al tamaño del marco. Cada vez que ocurre una recursión, si necesito asignar un marco enorme en la pila de llamadas por encima de la función de llamada, el TCO sería más útil y me permitiría más niveles de recursión. Pero en caso de que mi tamaño de cuadro sea menor, puedo prescindir del TCO y seguir ejecutando bien mi programa (no estoy hablando de recursión infinita aquí). Si queda con goto en la función, la llamada "tail" no es realmente una llamada tail y el TCO no es aplicable.
grillSandwich
3

El enfoque de la función recursiva tiene un problema. Construye una pila de llamadas de tamaño O (n), lo que hace que nuestra memoria total cueste O (n). Esto lo hace vulnerable a un error de desbordamiento de pila, donde la pila de llamadas se vuelve demasiado grande y se queda sin espacio.

Esquema de optimización de llamada de cola (TCO). Donde puede optimizar las funciones recursivas para evitar la acumulación de una gran pila de llamadas y, por lo tanto, ahorra el costo de la memoria.

Hay muchos lenguajes que están haciendo TCO como (JavaScript, Ruby y algunos C) mientras que Python y Java no hacen TCO.

El lenguaje JavaScript ha confirmado usando :) http://2ality.com/2015/06/tail-call-optimization.html

Rupesh Kumar Tiwari
fuente
0

En un lenguaje funcional, la optimización de la llamada de cola es como si una llamada de función pudiera devolver una expresión parcialmente evaluada como resultado, que luego sería evaluada por la persona que llama.

f x = g x

f 6 se reduce a g 6. Entonces, si la implementación pudiera devolver g 6 como resultado, y luego llamar a esa expresión, guardaría un marco de pila.

también

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

Reduce a f 6 a g 6 o h 6. Entonces, si la implementación evalúa c 6 y encuentra que es cierto, entonces puede reducir,

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

f x ---> h x

Un simple intérprete de optimización de llamada no final podría verse así,

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

Un intérprete de optimización de llamada de cola podría verse así,

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
fuente