Ricorsione con allocazione di memoria

Question

Stavo guardando un video su CUDA e l'algoritmo Barnes-Hut in cui è stato affermato che è necessario posizionare un limite di profondità sull'albero per la GPU, e quindi l'idea mi è venuta in mente probabilmente facendo ricorsione nell'heap.

Fondamentalmente, mi stavo chiedendo proprio questo: è possibile allocare memoria dall'heap e usarla come "stack" temporaneo in cui posizionare le chiamate di funzione per la funzione ricorsiva in questione per ritardare un overflow dello stack?

Se sì, come potrebbe essere implementato, dovremmo allocare lo spazio per un puntatore alla funzione? Presumo che implicherebbe l'archiviazione dell'indirizzo di funzione nell'heap, ma non ne sono troppo sicuro.

[modifica] Volevo solo aggiungere che questa è una domanda puramente teorica, e immagino che facendo ciò si rallenterebbe il programma una volta che si utilizza l'heap.

[modifica] Secondo la richiesta, il compilatore che sto usando è 4.8.4 GCC su Ubuntu 14.04 (64-bit)

Answer 1

Certo. Questo è chiamato stile di passaggio continuo. La libreria standard lo supporta con setjmp() e longjmp() e memorizza le informazioni necessarie per ripristinare il controllo in un punto precedente in una struttura denominata jmp_buf. (Esistono diverse restrizioni su dove è possibile eseguire il ripristino.) Le memorizzeresti in una pila, che è solo una coda LIFO.

Un approccio più generale è eseguire il programma come macchina di stato e memorizzare le informazioni necessarie per tornare indietro allo stato del programma, chiamato continuazione, in una struttura dati chiamata trampolino. Un motivo comune per volerlo fare è ottenere l'equivalente della ricorsione in coda in un'implementazione che non lo ottimizzi e potrebbe rompere un sacco di spazio nello stack. Un'applicazione del mondo reale in cui qualcuno che conosco sta attualmente scrivendo un trampolino è un parser GLL in cui la grammatica è rappresentata come un grafico diretto, il risultato del parse è una foresta di analisi condivisa e il parser ha spesso bisogno di tornare indietro per provare un Regola diversa

continuazione-passing e tappeti elastici sembrano essere considerato come lo stile di fantasia perché provengono dal mondo della programmazione funzionale, mentre longjmp() è considerato come un brutto hack di basso livello e anche la pagina man di Linux dice di non usarlo.

Answer 2

È possibile simulare ciò implementando il proprio stack basato su heap come una matrice di strutture, con ogni struttura che rappresenta uno stack frame che contiene l'equivalente di parametri e variabili locali. Invece di una funzione che si chiama in modo ricorsivo, la funzione si ripete e ogni "chiamata" spinge esplicitamente un nuovo frame nello stack.

Ho fatto esattamente questo anni fa mentre tentavo di risolvere un semplice gioco da tavolo. Il programma era originariamente ricorsivo, e ci volle un'eternità per correre. L'ho modificato nella struttura di cui sopra, e questo ha reso semplice rendere l'app interrompibile/riavviabile. Una volta interrotta, l'app ha scaricato il suo "stack" in un file di stato. Al riavvio, l'app ha caricato il file di stato e ha continuato da dove era stato interrotto.

Ciò richiede un po 'di attenzione se la struttura del frame dello stack contiene dei puntatori integrati, ma non è insormontabile.