How can I reduce the stack frame using a deeply recursive function in C?

Question

Suppose I have some recursive function that manipulates the structure of a graph:

typedef struct Node { Data data; size_t visited; size_t num_neighbors; struct Node *neighbors[]; } Node; void doSomethingWithNode(Node *node) { if ((!node) || node->visited) return; node->visited = 1; /* Do something with node->data */ size_t /* some local variables */; size_t i; for (i = 0; i < node->num_neighbors; i++) { /* Do some calculations with the local variables */ if (/* something */) doSomethingWithNode(node->neighbors[i]); } } 

Due to the local variables that I use in the loop, the compiler ( gcc ) creates a larger stack frame for this function than I-will (a good number of pushq and popq even with -O3 ), which is a problem because it is deep recursive. Since it doesn't matter in which order I visit the nodes, I could reorganize this code using the Node pointer stack, thereby reducing the overhead to a single iteration pointer.

• Are there any tips I can give the compiler ( gcc ) to fix this problem?
• If not, is it possible to use the call stack itself for my pointer stack without resorting to assembly?

Answer 1

You can save a vector or list (or some queue, or maybe a stack or even an arbitrary unordered set) of nodes to visit (and you probably want to maintain a set or hash table of already visited nodes).

Then you will have a loop that selects node in front of the container to visit, and can add some invisible nodes to the back of this container ....

Read the wikipages on the sequel style and tail calls.

Google is also for the Deutsch Schorr Waite algorithm, it can give you some ideas.

Answer 2

Can you put calculations in your non-recursive function? Thus, the stack for all temporary variables will not be present when making a recursive call.

Update: it looks like at least some data in local variables is needed for recursion. You can use alloca to explicitly allocate memory on the stack.

Answer 3

What do you expect from the compiler to solve the problem?

You can, of course, go through your code and minimize the number of local variables, try to make it as clear as possible that they (for example) are assigned only once, using const whenever possible, and so on. This can cause the compiler to reuse space , if possible.

Otherwise, you can probably save some memory by going iteratively, as this eliminates the need for a return address.

Answer 4

You can use malloc and realloc to manage a dynamically growing set of nodes. Here is the "class" for managing the stack:

 typedef struct Stack { void **pointers; size_t count; size_t alloc; } Stack; void Stack_new(Stack *stack) { stack->alloc = 10; stack->count = 0; stack->pointers = malloc(stack->alloc * sizeof(void*)); } void Stack_free(Stack *stack) { free(stack->pointers); stack->pointers = null; } void Stack_push(Stack *stack, void *value) { if (stack->alloc < stack->count + 1) { stack->alloc *= 2; stack->pointers = realloc(stack->pointers, stack->alloc * sizeof(void*)); } stack->pointers[stack->count++] = value; } void *Stack_pop(Stack *stack) { if (stack->count > 0) return stack->pointers[--stack->count]; return NULL; } 

Answer 5

"it is very recursive" is a hint that the deepest recursions occur in paths that do not have more than 1 neighbor not visited.

Let the code only recurs when there is more than one interesting neighbor, otherwise just a loop.

 void doSomethingWithNode(Node *node) { while (node) { if (node->visited) return; node->visited = 1; /* Do something with node->data */ size_t /* some local variables */; size_t i; Node *first = NULL; for (i = 0; i < node->num_neighbors; i++) { /* Do some calculations with the local variables */ if (/* something */) { // Save the first interesting node->neighbors[i] for later if (first == NULL && node->neighbors[i] != NULL && node->neighbors[i]->visited == 0) { first = node->neighbors[i]; } else { doSomethingWithNode(node->neighbors[i]); } } } node = first; } } 

This does not reduce the stack frame, but excludes recursion when there is only 1 layer. IOW: when recursion is not needed.

The recursion depth should now not exceed O (log2 (n)) instead of the original worst case O (n)

Answer 6

If you have more local variables and arrays, you can try to allocate memory with malloc , manipulate it with a single pointer and fixed offsets. free memory when exiting a function.

This way you save the stack and reuse the same heap (possibly) section for all iterations.

Answer 7

I find a lot if the other answers are not elegant and require a lot of overhead. There is probably no good way, and any way depends on the type of recursion.

In your case, the recursion completes, and only the variable i is still needed. To reduce the stack frame, you can use global space for other global variables.

If you want to reduce even more and delete i, you can use node → as a counter:

 static struct VARS { int iSomething; Data *dataptr; double avg; } gVars; void doSomethingWithNode(Node *node) { if ((!node) || node->visited) return; /* Do something with node->data */ /* some local variables in global space */; gVars.iSomething= 1; for (; node->visited < node->num_neighbors; node->visited++) { /* Do some calculations with the local variables */ if (/* something */) doSomethingWithNode(node->neighbors[node->visited]); } } 

Answer 8

Put all local variables that are not essential for recursion in struct locals and access them using plocals-> . An advantage over calculating into your own, non-recursive function (Arkady's answer), if it is necessary that the variables are valid and retain their values ​​by recursion.

 #include <stddef.h> struct Data { char data[1]; }; typedef struct Node { struct Data data; size_t visited; size_t num_neighbors; struct Node *neighbors; } Node; struct Locals { /* local variables not essential for recursion */; }; static void doSomethingWithNodeRecurse(Node *node, struct Locals *plocals) { if ((!node) || node->visited) return; node->visited = 1; /* Do something with node->data */ /* local variables essential for recursion */ size_t i; for (i = 0; i < node->num_neighbors; i++) { /* Do some calculations with the local variables */ if (1/* something */) doSomethingWithNodeRecurse(&node->neighbors[i], plocals); /* Do some calculations with the local variables */ } } void doSomethingWithNode(Node *node) { struct Locals locals; doSomethingWithNodeRecurse(node, &locals); } 

If the variables are still too large to allocate them on the stack, they can be allocated on the heap, as Vagish suggested:

 #include <stddef.h> #include <stdlib.h> struct Data { char data[1]; }; typedef struct Node { struct Data data; size_t visited; size_t num_neighbors; struct Node *neighbors; } Node; struct Locals { /* local variables too big for allocation on stack */; }; void doSomethingWithNode(Node *node) { struct Locals *plocals; if ((!node) || node->visited) return; /* ---> allocate the variables on the heap <--- */ if ((plocals = malloc(sizeof *plocals)) == NULL) abort(); node->visited = 1; /* Do something with node->data */ size_t i; for (i = 0; i < node->num_neighbors; i++) { /* Do some calculations with the local variables */ if (1/* something */) doSomethingWithNode(&node->neighbors[i]); /* Do some calculations with the local variables */ } /* ---> free the variables <--- */ free(plocals); }