Erlang: stackoverflow con funzione ricorsiva non ottimizzata per la coda?

Question

E 'possibile ottenere uno stackoverflow con una funzione che non è ottimizzata per la coda in Erlang? Ad esempio, supponiamo di avere una funzione come questa

sum_list([],Acc) -> 
    Acc; 
sum_list([Head|Tail],Acc) -> 
    Head + sum_list(Tail, Acc). 

Sembrerebbe come se un elenco di grandi dimensioni abbastanza è stata approvata in esso sarebbe poi esaurito lo spazio di stack e crash. Ho provato a provare questo in questo modo:

> L = lists:seq(1, 10000000). 
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22, 23,24,25,26,27,28,29|...] 
> sum_test:sum_list(L, 0). 
50000005000000 

Ma non si arresta mai! L'ho provato con un elenco di 100.000.000 di interi e ci è voluto un po 'di tempo per finire, ma non si è mai fermato! Domande:

1. Sto verificando questo correttamente?
2. In tal caso, perché non riesco a generare uno stackoverflow?
3. Erlang sta facendo qualcosa che impedisce il verificarsi di flussi di stackover?

Answer 1

Si sta verificando correttamente: la propria funzione non è effettivamente ricorsiva in coda. Per scoprirlo, è possibile compilare il codice utilizzando erlc -S <erlang source file>.

{function, sum_list, 2, 2}. 
    {label,1}. 
    {func_info,{atom,so},{atom,sum_list},2}. 
    {label,2}. 
    {test,is_nonempty_list,{f,3},[{x,0}]}. 
    {allocate,1,2}. 
    {get_list,{x,0},{y,0},{x,0}}. 
    {call,2,{f,2}}. 
    {gc_bif,'+',{f,0},1,[{y,0},{x,0}],{x,0}}. 
    {deallocate,1}. 
    return. 
    {label,3}. 
    {test,is_nil,{f,1},[{x,0}]}. 
    {move,{x,1},{x,0}}. 
    return. 

Come confronto la seguente versione tail-ricorsiva della funzione:

tail_sum_list([],Acc) -> 
    Acc; 
tail_sum_list([Head|Tail],Acc) -> 
    tail_sum_list(Tail, Head + Acc). 

compila come:

{function, tail_sum_list, 2, 5}. 
    {label,4}. 
    {func_info,{atom,so},{atom,tail_sum_list},2}. 
    {label,5}. 
    {test,is_nonempty_list,{f,6},[{x,0}]}. 
    {get_list,{x,0},{x,2},{x,3}}. 
    {gc_bif,'+',{f,0},4,[{x,2},{x,1}],{x,1}}. 
    {move,{x,3},{x,0}}. 
    {call_only,2,{f,5}}. 
    {label,6}. 
    {test,is_nil,{f,4},[{x,0}]}. 
    {move,{x,1},{x,0}}. 
    return. 

Avviso mancanza di allocate e call_only opcode nella di coda versione ricorsiva, in contrasto con lo allocate/call/deallocate/return sequenza nella funzione non ricorsiva.

Non si ottiene un overflow dello stack perché lo "stack" Erlang è molto grande. Infatti, l'overflow dello stack di solito significa che lo stack del processore è in overflow, poiché il puntatore dello stack del processore si è allontanato troppo. I processi hanno tradizionalmente una dimensione dello stack limitata che può essere ottimizzata interagendo con il sistema operativo. Vedi ad esempio POSIX setrlimit.

Tuttavia, lo stack di esecuzione di Erlang è non lo stack del processore, poiché il codice è interpretato. Ogni processo ha il proprio stack che può crescere secondo le necessità richiamando le funzioni di allocazione della memoria del sistema operativo (in genere malloc su Unix).

Come risultato, la funzione non si arresta finché le chiamate malloc hanno esito positivo.

Per la registrazione, l'elenco effettivo L utilizza la stessa quantità di memoria dello stack per elaborarlo. Infatti, ogni elemento della lista prende due parole (il valore intero stesso, che è racchiuso in una parola così come sono piccole) e il puntatore all'elemento successivo alla lista. Al contrario, lo stack viene generato da due parole a ogni iterazione tramite allocate opcode: una parola per CP che viene salvata dallo stesso allocate e una parola come richiesto (il primo parametro di allocate) per il valore corrente.

Per 100.000.000 di parole su una macchina virtuale a 64 bit, l'elenco richiede un minimo di 1,5 GB (più di quanto lo stack effettivo non cresca ogni due parole, per fortuna). Monitorare e garbaging è difficile nella shell, dal momento che molti valori rimangono attivi. Se si depongono le uova una funzione, è possibile visualizzare l'utilizzo della memoria:

spawn(fun() -> 
    io:format("~p\n", [erlang:memory()]), 
    L = lists:seq(1, 100000000), 
    io:format("~p\n", [erlang:memory()]), 
    sum_test:sum_list(L, 0), 
    io:format("~p\n", [erlang:memory()]) 
end). 

Come si può vedere, la memoria per la chiamata ricorsiva non viene rilasciato immediatamente.