Wie kann ich den Stapelrahmen einer tief rekursiven Funktion in C reduzieren?

Question

Angenommen ich eine rekursive Funktion haben, die eine Graphenstruktur manipuliert:

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

Aufgrund der lokalen Variablen I in der Schleife zu verwenden, erzeugt der Compiler (gcc) einen über-I-wäre-like Stapelrahmen für diese Funktion (eine gute Anzahl von pushq und popq Anweisungen sogar mit -O3), was ein Problem ist, da es tief rekursiv ist. Da es egal ist, in welcher Reihenfolge ich die Knoten besuche, könnte ich diesen Code umgestalten, um einen Stapel von Node Zeigern zu verwenden, wodurch der Aufwand auf einen Zeiger pro Iteration reduziert wird.

1. Gibt es irgendwelche Hinweise, die ich dem Compiler geben kann (gcc), um dieses Problem zu beheben?
2. Wenn nicht, ist es möglich, den Aufrufstapel selbst für meinen Stapel von Zeigern zu verwenden, ohne auf die Assembly zuzugreifen?

Answer 1

Können Sie die Berechnungen in ihre eigene, nicht-rekursive Funktion einfügen? Auf diese Weise wird der Stapel für alle temporären Variablen nicht vorhanden sein, wenn Sie den rekursiven Aufruf ausführen.

Update: sieht aus wie mindestens einige Daten in den lokalen Variablen ist für die Rekursion notwendig. Sie können alloca verwenden, um Speicher auf dem Stapel explizit zuzuweisen.

Answer 2

Was würden Sie vom Compiler erwarten, um das Problem zu lösen?

Sie können natürlich Ihren Code durchlaufen und die Anzahl der lokalen Variablen minimieren, versuchen Sie es so klar wie möglich zu machen, dass sie (z. B.) nur einmal zugewiesen werden, indem Sie const verwenden, wenn möglich. Dieser könnte machen den Compiler den Raum, wenn möglich, wiederverwenden.

Andernfalls können Sie wahrscheinlich etwas Speicher sparen, indem Sie stattdessen iterativ gehen, da dies die Notwendigkeit für die Rücksendeadresse ausschließt.

Answer 3

Sie können malloc und realloc verwenden, um einen dynamisch wachsenden Knotenstapel zu verwalten. Hier ist eine „Klasse“ für die Verwaltung des Stapels:

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 4

Sie könnten einen Vektor oder eine Liste (oder eine Warteschlange, oder vielleicht einen Stapel oder sogar eine beliebige ungeordnete Menge) halten von Knoten besucht werden (und Sie wahrscheinlich eine Set- oder Hash-Tabelle von bereits besuchten Knoten pflegen wollen).

Dann werden Sie eine Schleife haben, die den Knoten vor dem Zu-besuchten Behälter nimmt, und möglicherweise einige unvisited Knoten in der Rückseite des Containers hinzufügen ....

die WikiPages Lesen Sie mehr über continuation passing style und tail calls über

Google auch für Deutsch Schorr Waite Algorithmus, es könnte Ihnen ein paar Ideen.

Answer 5

Wenn Sie eine größere Anzahl von lokalen Variablen und Arrays haben, können Sie versuchen, Speicher unter Verwendung von malloc zuzuordnen, indem Sie ihn mit einem einzigen Zeiger und festen Offsets manipulieren. free der Speicher beim Verlassen der Funktion.

Auf diese Weise speichern Sie den Stapel und verwenden denselben Heap-Abschnitt (vielleicht) für alle Iterationen.

Answer 6

"Es ist tief rekursiv" ist ein Hinweis, dass die tiefsten Rekursionen in Pfaden auftreten, die nicht mehr als 1 nicht besuchte neighbor haben.

Lassen Sie Code nur recurse, wenn es mehr als 1 interessante Nachbar gibt, sonst nur Schleife.

Dies reduziert nicht den Stapelrahmen, aber Rekursion, wenn es nur 1-lagig ist. IOWs: wenn Rekursion nicht benötigt wird.

Die Rekursionstiefe sollte nun nicht mehr überschreiten O (log 2 (n)) anstelle des ursprünglichen ungünstigsten Fall O (n)

Answer 7

Ich finde viele, wenn die anderen Antworten nicht elegant und erfordert viel Aufwand. Wahrscheinlich gibt es keinen guten Weg und jeder hängt von der Art der Rekursion ab.

In Ihrem Fall ist die Rekursion am Ende und nur die Variable i wird noch benötigt. Um den Stack-Frame zu reduzieren, können Sie für andere Variablen den globalen Space verwenden.

Wenn Sie noch mehr zu reduzieren und zu entfernen, i, können Sie node-> visisted als Gegen:

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

alle lokalen Variablen Setzen Sie die für Rekursion nicht wesentlich sind in struct locals und greifen Sie mit plocals-> . Der Vorteil gegenüber den Berechnungen in ihre eigene, nicht-rekursive Funktion (Arkadiy's Antwort) ist, falls nötig, dass die Variablen gültig sind und ihre Werte über die Rekursionen behalten.

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

Wenn die Variablen immer noch zu groß sind, um sie auf dem Stapel zu verteilen, können sie auf dem Heap zugewiesen werden, wie Vagish vorgeschlagen:

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