Estendi lo stack di chiamate su disco in C++?

Question

Quando si tratta di chiamate di metodo ricorsive in modo massivo, è necessario estendere le dimensioni dello stack di chiamata modificando i parametri del compilatore appropriati per evitare il sovraccarico dello stack.

Consideriamo di scrivere un'applicazione portatile il cui layout è abbastanza semplice da consentire agli utenti di avere solo una conoscenza tecnica minima, quindi la configurazione manuale della memoria virtuale è fuori questione.

L'esecuzione di metodi ricorsivi in ​​modo massivo (ovviamente dietro le quinte) può comportare il superamento del limite di stack delle chiamate, soprattutto se la macchina su cui è in esecuzione l'applicazione ha una memoria limitata.

Basta chiacchiere: In C++ è possibile estendere manualmente lo stack di chiamata sul disco nel caso in cui la memoria sia (quasi) piena?

Answer 1

Potrebbe essere appena possibile.

Utilizzare una libreria di coroutine. Con ciò, si alloca il proprio stack dall'heap. Ristruttura il tuo codice per tenere traccia di quanto è profondo nel suo callstack, e quando diventa pericolosamente profondo, crea un nuovo cothread e passa a quello. Quando esaurisci la memoria heap, congela vecchi cothread e libera la loro memoria. Ovviamente, è meglio che li sblocchi allo stesso indirizzo - quindi ti suggerisco di allocare i loro stack stessi dalla tua arena che puoi controllare. In effetti, potrebbe essere più semplice riutilizzare lo stesso pezzo di memoria per la pila di filtri e scambiarli uno alla volta.

È sicuramente più semplice riscrivere l'algoritmo in modo che non sia ricorsivo.

Questo può essere un esempio di farlo funzionare, o può semplicemente stampare la risposta giusta sull'incidente:

#include <stdio.h> 
#include "libco.h" 

//byuu's libco has been modified to use a provided stack; it's a simple mod, but needs to be done per platform 
//x86.c: 
////if(handle = (cothread_t)malloc(size)) { 
//handle = (cothread_t)stack; 

//here we're going to have a stack on disk and have one recursion's stack in RAM at a time 
//I think it may be impossible to do this without a main thread controlling the coroutines, but I'm not sure. 

#define STACKSIZE (32*1024) 
char stack[STACKSIZE]; 

FILE* fpInfiniteStack; 
cothread_t co_mothership; 

#define RECURSING 0 
#define EXITING 1 
int disposition; 

volatile int recurse_level; 

int call_in_cothread(int (*entrypoint)(int), int arg); 

int fibo_b(int n); 
int fibo(int n) 
{ 
    if(n==0) 
     return 0; 
    else if(n==1) 
     return 1; 
    else { 
     int a = call_in_cothread(fibo,n-1); 
     int b = call_in_cothread(fibo_b,n-2); 
     return a+b; 
    } 
} 
int fibo_b(int n) { printf("fibo_b\n"); return fibo(n); } //just to make sure we can call more than one function 

long filesize; 
void freeze() 
{ 
    fwrite(stack,1,STACKSIZE,fpInfiniteStack); 
    fflush(fpInfiniteStack); 
    filesize += STACKSIZE; 
} 
void unfreeze() 
{ 
    fseek(fpInfiniteStack,filesize-STACKSIZE,SEEK_SET); 
    int read = fread(stack,1,STACKSIZE,fpInfiniteStack); 
    filesize -= STACKSIZE; 
    fseek(fpInfiniteStack,filesize,SEEK_SET); 
} 

struct 
{ 
    int (*proc)(int); 
    int arg; 
} thunk, todo; 

void cothunk() 
{ 
    thunk.arg = thunk.proc(thunk.arg); 
    disposition = EXITING; 
    co_switch(co_mothership); 
} 

int call_in_cothread(int (*proc)(int), int arg) 
{ 
    if(co_active() != co_mothership) 
    { 
     todo.proc = proc; 
     todo.arg = arg; 

     disposition = RECURSING; 
     co_switch(co_mothership); 
     //we land here after unfreezing. the work we wanted to do has already been done. 
     return thunk.arg; 
    } 

NEXT_RECURSE: 
    thunk.proc = proc; 
    thunk.arg = arg; 
    cothread_t co = co_create(stack,STACKSIZE,cothunk); 
    recurse_level++; 
NEXT_EXIT: 
    co_switch(co); 

    if(disposition == RECURSING) 
    { 
     freeze(); 
     proc = todo.proc; 
     arg = todo.arg; 
     goto NEXT_RECURSE; 
    } 
    else 
    { 
     recurse_level--; 
     unfreeze(); 
     if(recurse_level==0) 
      return thunk.arg; //return from initial level of recurstion 
     goto NEXT_EXIT; 
    } 

    return -666; //this should not be possible 
} 

int main(int argc, char**argv) 
{ 
    fpInfiniteStack = fopen("infinite.stack","w+b"); 
    co_mothership = co_active(); 
    printf("result: %d\n",call_in_cothread(fibo,10)); 
} 

Ora non vi resta per rilevare la quantità di memoria di nel sistema, quanto di esso è disponibile , quanto è grande il callstack e quando il callstack è esaurito, quindi sai quando distribuire lo stack infinito. Non è roba facile per un sistema, per non parlare di renderlo portabile. Potrebbe essere meglio imparare come lo stack è effettivamente destinato ad essere usato, invece di combatterlo.

Answer 2

È fattibile. È necessario un po 'di assembly per manipolare il puntatore dello stack in quanto non esiste un modo standardizzato di accedervi dal C++ direttamente (per quanto ne so). Una volta che sei lì puoi puntare alla tua pagina di memoria e occuparti di scambiare la memoria dentro e fuori. Ci sono già delle librerie là fuori che lo fanno per te.

D'altro canto se il fornitore del sistema riteneva che la memoria di paging o le altre tecniche di memoria virtuale non funzionassero/valessero sulla piattaforma, probabilmente avevano una buona ragione (molto probabilmente sarebbe incredibilmente lento). Cerca di far funzionare la soluzione senza ricorrere alla ricorsione o modificarla per rendere la ricorsione adatta a ciò che è disponibile. Anche un'implementazione meno efficiente finirebbe più velocemente della ricorsione su disco.