Extend call stack to disk in C ++?

Question

When it comes to mass recursive method calls, the size of the call stack should be expanded by changing the appropriate compiler options to avoid.

Let's consider writing a portable application, the layout of which is simple enough so that its users have the minimum technical knowledge, so the guide to setting up virtual memory is out of the question.

Running massive recursive methods (obviously behind the scenes) can lead to exceeding the call stack limit, especially if the machine on which the application is running is limited in size.

Enough chit-chat: In C ++, can I manually expand the call stack to disk if the memory is (almost) full?

Answer 1

It can be hardly possible.

Use the coroutine library. In doing so, you allocate your own stack from the heap. Rebuild your code to keep track of how deep it is in its stack, and when it gets dangerously deep, create a new cothread and switch to it. When you run out of heap memory, freeze old cothreads and free their memory. Of course, you should definitely unfreeze them at the same address - so I suggest you lay out your stacks from your own arena so that you can control. It may actually be easier to just reuse the same piece of memory for the cothread stack and swap them every time.

Of course, you can rewrite your algorithm as non-recursive.

This can be an example of his work, or he can simply print the correct answer in case of an accident:

#include <stdio.h> #include "libco.h" //byuu libco has been modified to use a provided stack; it 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 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)); } 

Now you just need to determine how much memory is in the system, how much of it is available, how big the column is, and when the callstack is exhausted, so you know when to deploy an infinite stack. This is not an easy task for one system, not to mention its portability. Perhaps it would be better to learn how to actually use the stack, rather than fight it.

Answer 2

It is doable. You need a little assembly to manipulate the stack pointer, since there is no standardized way to access it directly from C ++ (as far as I know). Once you are there, you can point to your memory page and take care of the memory exchange. There are already libraries that do this for you.

On the other hand, if the system provider believes that the paging memory or other virtual memory methods will not work / stand on the platform, they probably had a very good reason (most likely, it would be incredibly slow). Try to make your decision work without recursion, or modify it to make recursion suitable for what is available. Even less efficient implementations will end faster than disk recursion.