Stack e heap
Stack e heap
Cosa succede in memoria quando si chiama una funzione. Va oltre quello che serve per gli esercizi.
Due funzioni quasi uguali:
function preparaContatore(): number {
let conteggio: number = 0;
conteggio++;
return conteggio;
}
function preparaLista(): string[] {
const lista: string[] = ["latte"];
lista.push("pane");
return lista;
}
const n: number = preparaContatore();
const spesa: string[] = preparaLista();
console.log(n); // 1
console.log(spesa); // [ 'latte', 'pane' ]
// console.log(conteggio); errore: Cannot find name 'conteggio'.
// console.log(lista); errore: Cannot find name 'lista'.
Dopo le chiamate, le variabili conteggio e lista non esistono più: sono locali, e alla fine della funzione spariscono. L'array però è arrivato intatto in spesa, con dentro quello che la funzione ci aveva messo. Se la variabile è sparita, dove è rimasto l'array per tutto quel tempo?
La risposta sta nel fatto che il programma usa due zone di memoria diverse, con regole diverse: lo stack e lo heap.
Il modello, allargato
Nel corso disegniamo la memoria come una tabella di celle con un indirizzo (vedi La memoria - celle e indirizzi). Finora avevamo due zone:
- le celle delle variabili, dagli indirizzi 100 in su;
- la zona "altrove" per array, oggetti e istanze, dal 500 in su.
Queste due zone hanno un nome. La prima è lo stack, la seconda è lo heap. Le funzioni sono il momento in cui la differenza conta.
| Zona | Cosa ci sta | Quando nasce un dato | Quando sparisce |
|---|---|---|---|
| Stack | Parametri e variabili locali di ogni chiamata, e le variabili del programma principale | Quando la funzione viene chiamata | Al return della funzione |
| Heap | Array, oggetti, istanze di classi | Quando scrivete [...], {...} o new |
Quando nessuna freccia lo raggiunge più |
Lo stack: una pila di fogli
"Stack" in inglese vuol dire pila. Nel modello è una pila di fogli:
- Quando il programma parte, c'è un foglio solo, quello del programma principale, con le sue variabili.
- Ogni chiamata di funzione mette un foglio nuovo in cima alla pila. Sul foglio il programma scrive i parametri (con i valori degli argomenti), le variabili locali man mano che vengono dichiarate, e il punto del codice a cui tornare.
- Si lavora sempre e solo sul foglio in cima.
- Al
return, il valore restituito viene consegnato al foglio sotto, e il foglio in cima si butta, con tutto quello che c'era sopra.
Il foglio di una chiamata si chiama, nei testi tecnici, frame (o record di attivazione). Qui lo chiamiamo foglio.
La regola "si toglie sempre quello in cima" funziona perché le chiamate si chiudono in ordine inverso a come si sono aperte: se a chiama b e b chiama c, finisce prima c, poi b, poi a. L'ultima chiamata aperta è sempre la prima a chiudersi.
Una chiamata, passo passo
function bmi(pesoKg: number, altezzaM: number): number {
const risultato: number = pesoKg / (altezzaM * altezzaM);
return Math.round(risultato * 10) / 10;
}
const peso: number = 70;
const valore: number = bmi(peso, 1.75);
console.log(valore); // 22.9
Prima della chiamata c'è solo il foglio del programma:
| Foglio | Indirizzo | Nome | Contenuto |
|---|---|---|---|
| programma | 100 | peso |
70 |
| programma | 101 | valore |
(in attesa) |
Il programma arriva a bmi(peso, 1.75). Mette in cima un foglio per bmi, crea le celle dei parametri e ci copia gli argomenti. pesoKg riceve una copia del contenuto della cella 100:
| Foglio | Indirizzo | Nome | Contenuto |
|---|---|---|---|
bmi (in cima) |
111 | altezzaM |
1.75 |
bmi (in cima) |
110 | pesoKg |
70 |
| programma | 101 | valore |
(in attesa) |
| programma | 100 | peso |
70 |
Disegniamo la pila con la cima in alto, come una pila vera. La funzione esegue la prima riga e aggiunge la sua variabile locale:
| Foglio | Indirizzo | Nome | Contenuto |
|---|---|---|---|
bmi (in cima) |
112 | risultato |
22.857142857142858 |
bmi (in cima) |
111 | altezzaM |
1.75 |
bmi (in cima) |
110 | pesoKg |
70 |
| programma | 101 | valore |
(in attesa) |
| programma | 100 | peso |
70 |
Al return la funzione calcola 22.9 e lo consegna. Il foglio di bmi si butta, e il valore va nella cella di valore:
| Foglio | Indirizzo | Nome | Contenuto |
|---|---|---|---|
| programma | 101 | valore |
22.9 |
| programma | 100 | peso |
70 |
Le celle 110, 111 e 112 non ci sono più. Per questo, dopo la chiamata, scrivere risultato o pesoKg dà Cannot find name. La prossima funzione che verrà chiamata riuserà quelle celle per il suo foglio.
Chiamate annidate
Quando una funzione ne chiama un'altra, i fogli si impilano:
function quadrato(x: number): number {
return x * x;
}
function distanza(dx: number, dy: number): number {
const somma: number = quadrato(dx) + quadrato(dy);
return Math.sqrt(somma);
}
const metri: number = distanza(3, 4);
console.log(metri); // 5
Durante la prima chiamata a quadrato, quella con dx:
| Foglio | Indirizzo | Nome | Contenuto |
|---|---|---|---|
quadrato (in cima) |
120 | x |
3 |
distanza |
111 | dy |
4 |
distanza |
110 | dx |
3 |
| programma | 100 | metri |
(in attesa) |
distanza è ferma a metà della riga, in attesa di sapere quanto vale quadrato(dx). quadrato restituisce 9, il suo foglio si butta, e distanza riprende da dove era rimasta. Subito dopo chiama di nuovo quadrato, con dy: un foglio nuovo, che finisce negli stessi indirizzi di prima (120), con x che questa volta vale 4. Le due chiamate a quadrato non condividono niente. Ognuna ha il suo x.
Solo dopo la seconda chiamata distanza può calcolare somma, che vale 25, e aggiungere la cella al suo foglio.
Se in un programma qualcosa va storto, l'errore di solito riporta l'elenco dei fogli aperti in quel momento: si chiama stack trace. Si legge dall'alto, dalla funzione in cui l'errore è successo, fino al programma principale.
Lo heap: dove vivono array e oggetti
"Heap" vuol dire mucchio. A differenza della pila, non c'è un ordine: il programma mette un array o un oggetto dove trova posto, e si segna l'indirizzo.
Lo heap non è legato alle chiamate. Un array creato dentro una funzione resta nello heap anche quando il foglio di quella funzione si butta. Questo risolve il problema iniziale:
function preparaLista(): string[] {
const lista: string[] = ["latte"];
lista.push("pane");
return lista;
}
const spesa: string[] = preparaLista();
Dentro preparaLista, prima del return:
| Zona | Foglio | Indirizzo | Nome | Contenuto |
|---|---|---|---|---|
| stack | preparaLista (in cima) |
110 | lista |
→ 500 |
| stack | programma | 100 | spesa |
(in attesa) |
| heap | 500 | ["latte", "pane"] |
return lista restituisce il contenuto della cella 110, cioè la freccia → 500. Il foglio si butta e la freccia viene scritta in spesa:
| Zona | Foglio | Indirizzo | Nome | Contenuto |
|---|---|---|---|---|
| stack | programma | 100 | spesa |
→ 500 |
| heap | 500 | ["latte", "pane"] |
È morta la variabile lista, cioè la cella con la freccia. L'array non è mai stato sullo stack, quindi non è stato buttato con il foglio. Con preparaContatore invece il numero stava dentro la cella conteggio, sullo stack: si salva perché return ne consegna una copia prima che il foglio si butti.
Lo stesso vale per gli oggetti e per le istanze create con new:
type Evento = {
titolo: string;
giorno: string;
ora: number;
};
function nuovoEvento(titolo: string, giorno: string, ora: number): Evento {
const evento: Evento = { titolo, giorno, ora };
return evento;
}
const dentista: Evento = nuovoEvento("Dentista", "giovedì", 15);
console.log(dentista.titolo); // Dentista
L'oggetto nasce nello heap quando il programma valuta { titolo, giorno, ora }, e sopravvive al return perché dentista riceve la sua freccia.
Chi pulisce lo heap
Lo stack si pulisce da solo: ogni return butta un foglio. Lo heap invece si riempie a ogni array, oggetto o new. Prima o poi qualcuno deve liberarlo.
In JavaScript lo fa un componente che si chiama garbage collector ("raccoglitore di spazzatura"). Ogni tanto parte, segue tutte le frecce che partono dallo stack, e segna tutto quello che riesce a raggiungere. Quello che non è raggiungibile da nessuna freccia non può più essere usato dal programma, quindi è spazzatura, e il suo spazio torna libero.
let classifica: number[] = [92, 88, 75];
classifica = [95, 92, 88];
| Zona | Indirizzo | Nome | Contenuto |
|---|---|---|---|
| stack | 100 | classifica |
→ 600 |
| heap | 500 | [92, 88, 75], nessuna freccia: spazzatura |
|
| heap | 600 | [95, 92, 88] |
Dopo la seconda riga nessuno raggiunge più l'array alla cella 500. Il garbage collector prima o poi lo libera, in un momento che il programma non controlla: in JavaScript la memoria non si libera mai a mano. In linguaggi come il C invece lo fa il programmatore, e dimenticarsene è una fonte classica di errori.
La ricorsione e lo stack overflow
Una funzione può chiamare sé stessa. Si chiama ricorsione. Ogni chiamata, anche alla stessa funzione, ha il suo foglio:
function contoAllaRovescia(n: number): void {
if (n === 0) {
console.log("Via!");
return;
}
console.log(n);
contoAllaRovescia(n - 1);
}
contoAllaRovescia(3);
// 3
// 2
// 1
// Via!
Nel momento in cui stampa "Via!", la pila è così:
| Foglio | Nome | Contenuto |
|---|---|---|
contoAllaRovescia (in cima) |
n |
0 |
contoAllaRovescia |
n |
1 |
contoAllaRovescia |
n |
2 |
contoAllaRovescia |
n |
3 |
| programma |
Quattro fogli della stessa funzione, ciascuno con il suo n. Poi il foglio con n uguale a 0 fa return, e i fogli si buttano uno alla volta, dall'alto.
La riga if (n === 0) si chiama caso base: è il punto in cui la funzione smette di chiamarsi. Senza caso base i fogli si accumulano senza fine:
function contoAllaRovescia(n: number): void {
console.log(n);
contoAllaRovescia(n - 1);
}
Il compilatore non segnala niente: per lui è codice valido. Quando lo eseguite, stampa numeri sempre più negativi e dopo qualche migliaio di chiamate si ferma:
RangeError: Maximum call stack size exceeded
Lo stack ha un'altezza massima, decisa da chi esegue il programma (Node.js, il browser). Quando i fogli la superano, il programma si ferma. L'errore si chiama stack overflow, "traboccamento della pila".
Si arriva allo stesso errore con due funzioni che si chiamano a vicenda senza fermarsi mai. Quando lo vedete, cercate una ricorsione senza caso base, o con un caso base che non viene mai raggiunto (per esempio n === 0 con un n che parte da 2.5 e scende di 1 a ogni chiamata).
Perché due zone
Una zona sola non basterebbe, perché stack e heap rispondono a due esigenze diverse.
Lo stack è velocissimo e ordinato. Aggiungere e togliere un foglio costa pochissimo, perché si lavora sempre in cima, e la memoria si libera da sola al return. In cambio, ogni foglio ha una dimensione decisa quando la funzione parte, e i dati muoiono con la chiamata.
Lo heap è flessibile. Un array può crescere con push, un oggetto può essere passato da una funzione all'altra e restare in vita quanto serve. In cambio, cercare spazio e ripulire costa di più.
Da qui la divisione del lavoro: i valori piccoli e di dimensione fissa (numeri, boolean, le frecce) stanno nelle celle sullo stack; quello che può crescere o deve sopravvivere alla chiamata sta nello heap, e sullo stack ne resta solo l'indirizzo.
Cosa semplifica il modello
Come per il resto del corso, il modello con i fogli è più semplice della macchina vera:
- un foglio vero contiene anche altre informazioni (l'indirizzo dell'istruzione a cui tornare, alcuni valori del processore);
- i motori JavaScript moderni, come V8 dentro Node.js e Chrome, a volte spostano dati da una zona all'altra per andare più veloci, quando sono sicuri che il risultato non cambia;
- le stringhe lunghe stanno di solito nello heap anche se nel modello le mettiamo dentro la cella. Siccome non si possono modificare, il comportamento è lo stesso di un valore copiato.
Nessuna di queste differenze cambia cosa stampa il vostro codice. Il modello risponde sempre giusto a tre domande: questa variabile esiste ancora? Questo array è ancora raggiungibile? Se modifico questo, chi vede la modifica? Per l'ultima domanda c'è anche Copiare un valore, copiare un riferimento.