Расширить стек вызовов на диск в C++?

Question

Когда дело доходит до массово-рекурсивных вызовов методов, размер стека вызовов должен быть расширен путем изменения соответствующих параметров компилятора, чтобы избежать переполнения стека.

Давайте рассмотрим возможность написания переносного приложения, макет которого достаточно прост, чтобы его пользователи обладали минимальными техническими знаниями, поэтому настройка виртуальной памяти вручную не может быть и речи.

Выполнение массово-рекурсивных методов (очевидно, за кулисами) может привести к превышению предела стека вызовов, особенно если машина, на которой работает приложение, ограничена по размеру.

Достаточно chit-chat: В C++ можно ли вручную расширить стек вызовов на диск в случае, если память (почти) заполнена?

Answer 1

Это может быть едва ли возможно.

Используйте библиотеку сопрограмм. При этом вы выделяете свой собственный стек из кучи. Перестройте свой код, чтобы отслеживать, насколько он глубоко в своем стеке, и когда он становится опасно глубоким, создайте новый cothread и переключитесь на него. Когда вы исчерпаете память кучи, заморозите старые cothreads и освободите их память. Разумеется, вы должны обязательно разморозить их по одному и тому же адресу - поэтому я предлагаю вам выложить свои стеки из своей собственной арены, чтобы вы могли контролировать. На самом деле может быть проще просто повторно использовать один и тот же кусок памяти для стека cothread и поменять их каждый раз.

Это, безусловно, проще переписать алгоритм так, чтобы он не был рекурсивным.

Это может быть примером его работы, или он может просто напечатать правильный ответ на аварии:

#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)); 
} 

Теперь вам просто нужно определить, сколько памяти в системе, сколько это доступно , насколько большой столбец, и когда израсходованный стоп-код исчерпан, поэтому вы знаете, когда нужно развернуть бесконечный стек. Это непростая задача для одной системы, не говоря уже о ее переносимости. Возможно, было бы лучше узнать, как фактически использовать стек, а не бороться с ним.

Answer 2

Это осуществимо. Вам нужна небольшая сборка для управления указателем стека, поскольку нет стандартизованного способа доступа к нему с C++ напрямую (насколько я знаю). Как только вы там, вы можете указать на свою страницу памяти и позаботиться об обмене памяти. Там уже есть библиотеки, которые делают это за вас.

С другой стороны, если системный провайдер считает, что пейджинговая память или другие методы виртуальной памяти не будут работать/стоят на платформе, у них, вероятно, была очень веская причина (скорее всего, это было бы невероятно медленно). Попытайтесь заставить свое решение работать без рекурсии или изменить его, чтобы рекурсия соответствовала тому, что доступно. Даже менее эффективная реализация закончится быстрее, чем рекурсия на диске.