Che cos'è l'ottimizzazione delle chiamate di coda?
https://stackoverflow.com/questions/310974
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
In parole semplici, cos'è l'ottimizzazione delle chiamate in coda? Più specificamente, qualcuno può mostrare alcuni piccoli frammenti di codice dove potrebbe essere applicato e dove no, con una spiegazione del perché?
Soluzione
L'ottimizzazione delle chiamate di coda è dove è possibile evitare di allocare un nuovo frame di stack per una funzione perché la funzione chiamante restituirà semplicemente il valore che ottiene dalla funzione chiamata. L'uso più comune è la ricorsione della coda, in cui una funzione ricorsiva scritta per sfruttare l'ottimizzazione della coda può utilizzare uno spazio di stack costante.
Lo schema è uno dei pochi linguaggi di programmazione che garantisce nelle specifiche che qualsiasi implementazione deve fornire questa ottimizzazione (anche JavaScript, a partire da ES6) , quindi ecco due esempi della funzione fattoriale in schema:
(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 prima funzione non è ricorsiva di coda perché quando viene effettuata la chiamata ricorsiva, la funzione deve tenere traccia della moltiplicazione che deve fare con il risultato dopo il ritorno della chiamata. Come tale, lo stack ha il seguente aspetto:
(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6
Al contrario, la traccia dello stack per il fattoriale ricorsivo della coda appare come segue:
(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6
Come puoi vedere, dobbiamo solo tenere traccia della stessa quantità di dati per ogni chiamata alla coda dei fatti perché stiamo semplicemente restituendo il valore che otteniamo fino in cima. Ciò significa che anche se dovessi chiamare (fatto 1000000), avrei bisogno solo della stessa quantità di spazio (fatto 3). Questo non è il caso del fatto non ricorsivo della coda e poiché valori così grandi possono causare un overflow dello stack.
Altri suggerimenti
Vediamo un semplice esempio: la funzione fattoriale implementata in C.
Iniziamo con l'ovvia definizione ricorsiva
unsigned fac(unsigned n)
{
if (n < 2) return 1;
return n * fac(n - 1);
}
Una funzione termina con una chiamata di coda se l'ultima operazione prima che la funzione ritorni è un'altra chiamata di funzione. Se questa chiamata richiama la stessa funzione, è ricorsiva alla coda.
Anche se fac () sembra ricorsivo alla coda a prima vista, non è come ciò che realmente accade è
unsigned fac(unsigned n)
{
if (n < 2) return 1;
unsigned acc = fac(n - 1);
return n * acc;
}
ovvero l'ultima operazione è la moltiplicazione e non la chiamata di funzione.
Tuttavia, è possibile riscrivere fac () in modo ricorsivo della coda passando il valore accumulato nella catena di chiamate come argomento aggiuntivo e passando di nuovo solo il risultato finale come valore di ritorno:
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);
}
Ora, perché è utile? Poiché torniamo immediatamente dopo la chiamata di coda, possiamo scartare lo stackframe precedente prima di richiamare la funzione in posizione di coda o, in caso di funzioni ricorsive, riutilizzare lo stackframe così com'è.
L'ottimizzazione del tail-call trasforma il nostro codice ricorsivo in
unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
if (n < 2) return acc;
acc = n * acc;
n = n - 1;
goto TOP;
}
Questo può essere inserito in fac () e arriviamo a
unsigned fac(unsigned n)
{
unsigned acc = 1;
TOP:
if (n < 2) return acc;
acc = n * acc;
n = n - 1;
goto TOP;
}
che equivale a
unsigned fac(unsigned n)
{
unsigned acc = 1;
for (; n > 1; --n)
acc *= n;
return acc;
}
Come possiamo vedere qui, un ottimizzatore sufficientemente avanzato può sostituire la ricorsione della coda con l'iterazione, che è molto più efficiente poiché si evita l'overhead della chiamata di funzione e si utilizza solo una quantità costante di spazio dello stack.
TCO (Tail Call Optimization) è il processo mediante il quale un compilatore intelligente può effettuare una chiamata a una funzione e non occupare spazio aggiuntivo nello stack. L'unica situazione in cui ciò accade è se l'ultima istruzione eseguita in una funzione f è una chiamata a una funzione g (Nota: g può essere f ). La chiave qui è che f non ha più bisogno di spazio per lo stack: chiama semplicemente g e quindi restituisce qualunque cosa g restituisca. In questo caso è possibile eseguire l'ottimizzazione che g viene eseguito e restituisce qualsiasi valore che avrebbe alla cosa che ha chiamato f.
Questa ottimizzazione può far sì che le chiamate ricorsive occupino spazio nello stack costante, anziché esplodere.
Esempio: questa funzione fattoriale non è TCOptimizable:
def fact(n):
if n == 0:
return 1
return n * fact(n-1)
Questa funzione fa cose oltre a chiamare un'altra funzione nella sua dichiarazione di ritorno.
Questa funzione di seguito è 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)
Questo perché l'ultima cosa che accade in una di queste funzioni è chiamare un'altra funzione.
Probabilmente la migliore descrizione di alto livello che ho trovato per le chiamate di coda, le chiamate di coda ricorsive e l'ottimizzazione delle chiamate di coda è il post sul blog
" ; Che diamine è: un richiamo alla coda "
di Dan Sugalski. Sull'ottimizzazione delle chiamate di coda scrive:
Considera, per un momento, questa semplice funzione:
sub foo (int a) { a += 15; return bar(a); }Quindi, cosa puoi fare, o meglio, il tuo compilatore di lingue? Bene, ciò che può fare è trasformare il codice nella forma
return somefunc ();nella sequenza di basso livellopop stack frame; vai a somefunc ();. Nel nostro esempio, ciò significa che prima di chiamarebar,foosi pulisce e quindi, anziché chiamarebarcome subroutine, facciamo un operazionegotodi basso livello all'inizio dellabarra.Foosi è già ripulito dallo stack, quindi quando si avviabarsembra che chiunque abbia chiamatofooabbia davvero chiamatobare quandobarrestituisce il suo valore, lo restituisce direttamente a chiunque abbia chiamatofoo, anziché restituirlo afooche quindi restituirlo al suo chiamante.
E sulla ricorsione della coda:
La ricorsione della coda si verifica se una funzione, come ultima operazione, ritorna il risultato della chiamata stessa . La ricorsione della coda è più facile da gestire perché piuttosto che dover saltare all'inizio di alcuni casuali funzione da qualche parte, basta tornare indietro all'inizio te stesso, che è una cosa dannatamente semplice da fare.
In modo che questo:
sub foo (int a, int b) { if (b == 1) { return a; } else { return foo(a*a + a, b - 1); }
viene tranquillamente trasformato in:
sub foo (int a, int b) { label: if (b == 1) { return a; } else { a = a*a + a; b = b - 1; goto label; }
Quello che mi piace di questa descrizione è quanto sia facile e conciso capire chi proviene da un background linguistico imperativo (C, C ++, Java)
Nota innanzitutto che non tutte le lingue lo supportano.
Il TCO si applica a un caso speciale di ricorsione. In sostanza, se l'ultima cosa che fai in una funzione è chiamare se stessa (ad esempio, si sta chiamando dalla posizione "coda"), questo può essere ottimizzato dal compilatore per agire come iterazione invece che ricorsione standard.
Vedi, normalmente durante la ricorsione, il runtime deve tenere traccia di tutte le chiamate ricorsive, in modo che quando si ritorna può riprendere alla chiamata precedente e così via. (Prova a scrivere manualmente il risultato di una chiamata ricorsiva per avere un'idea visiva di come funziona.) Tenere traccia di tutte le chiamate occupa spazio, il che diventa significativo quando la funzione si chiama molto. Ma con TCO, può solo dire "tornare all'inizio, solo che questa volta cambia i valori dei parametri con questi nuovi." Può farlo perché nulla dopo la chiamata ricorsiva fa riferimento a tali valori.
Esempio eseguibile minimo GCC con analisi di disassemblaggio x86
Vediamo come GCC può eseguire automaticamente le ottimizzazioni delle chiamate di coda per noi osservando l'assembly generato.
Questo servirà da esempio estremamente concreto di ciò che è stato menzionato in altre risposte come https://stackoverflow.com/a/ 9814654/895245 che l'ottimizzazione può convertire le chiamate di funzioni ricorsive in un ciclo.
Questo a sua volta consente di risparmiare memoria e migliorare le prestazioni, poiché gli accessi alla memoria sono spesso la cosa principale che oggi rallenta i programmi .
Come input, diamo a GCC un fattoriale basato su stack ingenuo non ottimizzato:
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;
}
Compila e disassembla:
gcc -O1 -foptimize-sibling-calls -ggdb3 -std=c99 -Wall -Wextra -Wpedantic \
-o tail_call.out tail_call.c
objdump -d tail_call.out
dove -foptimize-sibling-Calls è il nome della generalizzazione delle chiamate di coda secondo man gcc :
-foptimize-sibling-calls
Optimize sibling and tail recursive calls.
Enabled at levels -O2, -O3, -Os.
come menzionato in: Come posso verificare se gcc sta eseguendo l'ottimizzazione della ricorsione della coda?
Scelgo -O1 perché:
- l'ottimizzazione non viene eseguita con
-O0. Sospetto che ciò sia dovuto alla mancanza di trasformazioni intermedie richieste. -
-O3produce un codice ungodly efficiente che non sarebbe molto istruttivo, sebbene sia anche ottimizzato per le chiamate di coda.
Disassemblaggio con -fno-optim-sibling-Calls :
0000000000001145 <factorial>:
1145: 89 f8 mov %edi,%eax
1147: 83 ff 01 cmp 0000000000001145 <factorial>:
1145: b8 01 00 00 00 mov <*>x1,%eax
114a: 83 ff 01 cmp <*>x1,%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 <*>x1,%edx
115a: 75 f3 jne 114f <factorial+0xa>
115c: c3 retq
115d: 89 f8 mov %edi,%eax
115f: c3 retq
x1,%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 :
La differenza chiave tra i due è che:
-
il
-fno-optim-sibling-Callsutilizzacallq, che è la tipica chiamata di funzione non ottimizzata.Questa istruzione spinge l'indirizzo di ritorno nello stack, aumentandolo quindi.
Inoltre, questa versione fa anche
push% rbx, che spinge% rbxnello stack .GCC lo fa perché memorizza
edi, che è il primo argomento della funzione (n) inebx, quindi chiamafattoriale.GCC deve farlo perché si sta preparando per un'altra chiamata a
factorial, che utilizzerà il nuovoedi == n-1.Sceglie
ebxperché questo registro è salvato dalla chiamata: Quali registri vengono conservati tramite una chiamata di funzione x86-64 di Linux in modo che la chiamata secondaria afattorialenon la cambi e perdan. -
il
-foptimize-sibling-Callsnon usa alcuna istruzione che va nello stack: fa sologotosalta all'interno difattoriale con le istruzionijeejne.Pertanto, questa versione equivale a un ciclo while, senza alcuna chiamata di funzione. L'uso dello stack è costante.
Testato in Ubuntu 18.10, GCC 8.2.
Guarda qui:
http://tratt.net/laurie/tech_articles/articles/tail_call_optimization
Come probabilmente saprai, le chiamate di funzione ricorsive possono causare il caos in una pila; è facile esaurire rapidamente lo spazio dello stack. L'ottimizzazione delle chiamate di coda è il modo in cui è possibile creare un algoritmo di stile ricorsivo che utilizza uno spazio di stack costante, quindi non cresce e cresce e si ottengono errori di stack.
-
Dovremmo assicurarci che non ci siano dichiarazioni goto nella funzione stessa. La cura della chiamata funzione è l'ultima cosa nella funzione chiamata.
-
Le ricorsioni su larga scala possono utilizzarlo per le ottimizzazioni, ma su piccola scala, il sovraccarico di istruzioni per rendere la chiamata di funzione una chiamata di coda riduce lo scopo reale.
-
TCO potrebbe causare una funzione in esecuzione per sempre:
void eternity() { eternity(); }
L'approccio alla funzione ricorsiva ha un problema. Costruisce uno stack di chiamate di dimensioni O (n), il che rende la nostra memoria totale costata O (n). Ciò lo rende vulnerabile a un errore di overflow dello stack, in cui lo stack di chiamate diventa troppo grande e si esaurisce lo spazio. Schema di ottimizzazione dei costi di coda (TCO). Dove può ottimizzare le funzioni ricorsive per evitare di accumulare uno stack di chiamate elevato e quindi risparmiare il costo della memoria.
Ci sono molte lingue che fanno TCO come (Javascript, Ruby e poche C) dove Python e Java non fanno TCO.
Il linguaggio JavaScript ha confermato utilizzando :) http://2ality.com/ 2015/06 / tail-call-optimization.html
