コールスタックをC++でディスクに拡張しますか？

Question

大量再帰メソッド呼び出しでは、スタックオーバーフローを避けるために、適切なコンパイラパラメータを変更することによってコールスタックサイズを拡張する必要があります。

ユーザーが最小限の技術知識しか必要としないように、レイアウトが単純なポータブルアプリケーションを作成することを考えてみましょう。マニュアル仮想メモリの設定は問題になりません。

（特に舞台裏で）大量の再帰的メソッドを実行すると、特にアプリケーションが実行されているマシンのメモリが制限されている場合は、コールスタックの制限を超える可能性があります。

十分なchit-chat： C++では、メモリが（ほぼ）完全な場合に手動でコールスタックをディスクに拡張できますか？

Answer 1

これはほんのわずかかもしれません。

コルーチンライブラリを使用します。これで、自分のスタックをヒープから割り当てます。呼び出しスタック内の深さを追跡するためにコードを再構築し、危険なほど深くなったら新しいCothreadを作成し、その代わりにそのコードに切り替えます。ヒープメモリが足りなくなると、古いコードをフリーズしてメモリを解放します。もちろん、あなたは同じアドレスにそれらを解凍することをお勧めします - あなたが制御することができるあなた自身の競技場の自分自身のスタックを割り当てることをお勧めします。実際には、Cothreadスタックのために同じメモリを再利用し、一度に1つずつメモリを交換する方が簡単かもしれません。

アルゴリズムを再帰的でないものに書き換えることは間違いありません。

これは働いて、それの一例であってもよいし、それだけで事故に正しい答えを印刷することがあります。

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

は今、あなたは、単に利用可能ですどのくらいの、どのくらいのメモリのシステムで検出する必要がありますコールスタックの大きさ、およびコールスタックが使い尽くされたときに、無限スタックをいつ展開するかを知ることができます。 1つのシステムには簡単なものではありません。スタックが実際にどのように戦う代わりに使用されるのかを知る方が良いでしょう。

Answer 2

可能です。 C++から（私が知る限り）直接アクセスするための標準化された方法はないので、スタックポインタを操作するには少しのアセンブリが必要です。一度そこにいれば、あなたのメモリページを指し、メモリを入れ替えたりすることができます。既にあなたのためにそれを行っているライブラリがあります。

一方、システムプロバイダがページングメモリやその他の仮想メモリ技術がプラットフォーム上で動作しない/価値がないと考えた場合、おそらく非常に良い理由があったでしょう（おそらく非常に遅いでしょう）。あなたの解が再帰なしで動くようにするか、または再帰が利用可能なものに収まるように変更してください。効率の低い実装であっても、ディスクページの再帰よりも速く終了します。