C/C++ maximale Stapelgröße des Programms

Ich möchte DFS auf einem 100 x 100-Array ausführen. (Angenommen, Elemente eines Arrays stellen Diagrammknoten dar.) Unter der Annahme des schlimmsten Falls kann die Tiefe rekursiver Funktionsaufrufe bis zu 10000 betragen, wobei jeder Aufruf bis zu sagen wir 20 Bytes benötigt. Ist es also machbar, besteht die Möglichkeit eines Stapelüberlaufs?

Was ist die maximale Stapelgröße in C/C++?

Bitte gcc für beide angeben
1) cygwin unter Windows
2) Unix

Was sind die allgemeinen Grenzen?

In Visual Studio beträgt die Standardstapelgröße meiner Meinung nach 1 MB. Bei einer Rekursionstiefe von 10.000 kann jeder Stapelrahmen höchstens ~ 100 Bytes umfassen, was für einen DFS-Algorithmus ausreichen sollte.

Bei den meisten Compilern, einschließlich Visual Studio, können Sie die Stapelgröße angeben. Bei einigen (allen?) Linux-Varianten ist die Stapelgröße nicht Teil der ausführbaren Datei, sondern eine Umgebungsvariable im Betriebssystem. Sie können dann die Stapelgröße mit überprüfen ulimit -s und setzen Sie ihn beispielsweise mit auf einen neuen Wert ulimit -s 16384.

Hier ist ein Verknüpfung mit Standardstapelgrößen für gcc.

DFS ohne Rekursion:

std::stack<Node> dfs;
dfs.push(start);
do {
    Node top = dfs.top();
    if (top is what we are looking for) {
       break;
    }
    dfs.pop();
    for (outgoing nodes from top) {
        dfs.push(outgoing node);
    }
} while (!dfs.empty())

Stacks für Threads sind oft kleiner. Sie können die Standardeinstellung zum Zeitpunkt der Verknüpfung oder auch zur Laufzeit ändern. Als Referenz sind einige Standardwerte:

• glibc i386, x86_64: 7,4 MB
• Tru64 5.1: 5,2MB
• Cygwin: 1,8 MB
• Solaris 7..10: 1MB
• MacOS X 10.5: 460 KB
• AIX5: 98 KB
• OpenBSD 4.0: 64 KB
• HP-UX 11: 16 KB

Plattformabhängig, Toolchain-abhängig, ulimit-abhängig, Parameter-abhängig…. Es ist überhaupt nicht spezifiziert, und es gibt viele statische und dynamische Eigenschaften, die es beeinflussen können.

Ja, es besteht die Möglichkeit eines Stapelüberlaufs. Der C- und der C++-Standard schreiben keine Dinge wie die Stapeltiefe vor, diese sind im Allgemeinen ein Umweltproblem.

Mit den meisten anständigen Entwicklungsumgebungen und/oder Betriebssystemen können Sie die Stapelgröße eines Prozesses anpassen, entweder zur Link- oder Ladezeit.

Für eine gezieltere Unterstützung sollten Sie angeben, welches Betriebssystem und welche Entwicklungsumgebung Sie verwenden.

Beispielsweise ist unter Ubuntu Karmic Koala die Standardeinstellung für gcc 2 MB reserviert und 4 KB festgeschrieben, aber dies kann geändert werden, wenn Sie das Programm verknüpfen. Verwenden Sie die --stack Option von ld das zu tun.

Mir ist gerade bei der Arbeit der Stack ausgegangen, es war eine Datenbank und es lief einige Threads, im Grunde hatte der vorherige Entwickler ein großes Array auf den Stack geworfen, und der Stack war sowieso niedrig. Die Software wurde mit Microsoft Visual Studio 2015 kompiliert.

Obwohl dem Thread der Stack ausgegangen war, schlug er stillschweigend fehl und fuhr fort, er lief nur über, wenn es darum ging, auf den Inhalt der Daten auf dem Stack zuzugreifen.

Der beste Rat, den ich geben kann, ist, Arrays nicht auf dem Stapel zu deklarieren – insbesondere in komplexen Anwendungen und insbesondere in Threads, verwenden Sie stattdessen Heap. Dafür ist es da 😉

Denken Sie auch daran, dass es möglicherweise nicht sofort fehlschlägt, wenn der Stack deklariert wird, sondern nur beim Zugriff. Meine Vermutung ist, dass der Compiler den Stack unter Windows “optimistisch” deklariert, dh er geht davon aus, dass der Stack deklariert wurde und ausreichend groß ist, bis er verwendet wird, und findet dann heraus, dass der Stack nicht vorhanden ist.

Unterschiedliche Betriebssysteme können unterschiedliche Stack-Deklarationsrichtlinien haben. Bitte hinterlassen Sie einen Kommentar, wenn Sie wissen, was diese Richtlinien sind.

Ich bin mir nicht sicher, was Sie meinen, wenn Sie eine Tiefensuche in einem rechteckigen Array durchführen, aber ich gehe davon aus, dass Sie wissen, was Sie tun.

Wenn das Stapellimit ein Problem darstellt, sollten Sie in der Lage sein, Ihre rekursive Lösung in eine iterative Lösung umzuwandeln, die Zwischenwerte auf einen Stapel legt, der vom Heap zugewiesen wird.

(Hinzugefügt am 26. Sept. 2020)

Am 24. Okt. 2009, wie @pixelbeat hier zum ersten Mal erwähnte, Bruno Haible hat empirisch die folgenden Standard-Thread-Stack-Größen entdeckt für mehrere Systeme. Er hat das gesagt In einem Multithread-Programm ist “die Standard-Thread-Stack-Größe:”

- glibc i386, x86_64    7.4 MB
- Tru64 5.1             5.2 MB
- Cygwin                1.8 MB
- Solaris 7..10           1 MB
- MacOS X 10.5          460 KB
- AIX 5                  98 KB
- OpenBSD 4.0            64 KB
- HP-UX 11               16 KB

Beachten Sie, dass die oben genannten Einheiten alle in MB und KB (Zahlen zur Basis 1000) angegeben sind, NICHT in MiB und KiB (Zahlen zur Basis 1024). Ich habe mir das selbst bewiesen, indem ich den 7,4-MB-Fall verifiziert habe.

Er erklärte auch, dass:

32 KB sind mehr, als Sie in einem Multithread-Programm sicher auf dem Stack zuweisen können

Und er sagte:

Und die Standardstapelgröße für sigaltstack, SIGSTKSZ, ist

• nur 16 KB auf einigen Plattformen: IRIX, OSF/1, Haiku.
• nur 8 KB auf einigen Plattformen: glibc, NetBSD, OpenBSD, HP-UX, Solaris.
• nur 4 KB auf einigen Plattformen: AIX.

Bruno

Er schrieb das folgende einfache Linux-C-Programm, um die obigen Werte empirisch zu bestimmen. Sie können es heute auf Ihrem System ausführen, um schnell zu sehen, wie groß Ihre maximale Thread-Stack-Größe ist, oder Sie können es hier online auf GDBOnline ausführen: https://onlinegdb.com/rkO9JnaHD.

Erläuterung: Es erstellt einfach einen einzigen neuen Thread, um das zu überprüfen Größe des Threadstapels und NICHT die Programmstapelgrößefalls sie sich unterscheiden, muss dieser Thread wiederholt 128 Byte Speicher zuweisen auf dem Stapel (NICHT auf dem Haufen)Verwendung der Linux alloca() Anruf, danach schreibt es eine 0 in das erste Byte dieses neuen Speicherblocks und gibt dann aus, wie viele Bytes es insgesamt zugewiesen hat. Es wiederholt diesen Vorgang und weist 128 weitere Bytes zu auf dem Stapel jedes Mal, bis das Programm mit a abstürzt Segmentation fault (core dumped) Error. Der zuletzt gedruckte Wert ist die geschätzte maximale Thread-Stack-Größe, die für Ihr System zulässig ist.

Wichtiger Hinweis: alloca() ordnet zu auf dem Stapel: obwohl dies sieht aus wie dynamische Speicherzuordnung auf dem Heap, ähnlich wie a malloc() Anruf, alloca() ordnet dem Heap NICHT dynamisch zu. Eher, alloca() ist eine spezialisierte Linux-Funktion zur “pseudodynamischen” (ich bin mir nicht sicher, wie ich das nennen würde, also habe ich diesen Begriff gewählt) direkt zuzuweisen auf den Stapel als wäre es statisch zugewiesener Speicher. Stapelspeicher verwendet und zurückgegeben von alloca() ist am Geltungsbereich Funktionsebeneund wird daher “automatisch freigegeben, wenn die Funktion das rief alloca() kehrt zu seinem Aufrufer zurück.” Deshalb wird sein statischer Gültigkeitsbereich nicht verlassen und Speicher von zugewiesen alloca() wird NICHT jedes Mal freigegeben a for Schleifeniteration ist abgeschlossen und das Ende der for Schleifenbereich erreicht ist. Sehen man 3 alloca für Details. Hier ist das entsprechende Zitat (Hervorhebung hinzugefügt):

BEZEICHNUNG
Die alloca() Funktion zuweist Größe Byte Platz in der Stapelrahmen des Aufrufers. Dieser temporäre Speicherplatz wird automatisch freigegeben, wenn die Funktion das rief alloca() kehrt zurück zu seinem Anrufer.

RÜCKGABEWERT
Die alloca() Die Funktion gibt einen Zeiger auf den Anfang des zugewiesenen Speicherplatzes zurück. Wenn die Zuweisung zu einem Stapelüberlauf führt, ist das Programmverhalten undefiniert.

Hier das Programm von Bruno Haible vom 24. Okt. 2009, direkt von der GNU-Mailingliste hier kopiert:

Auch hier können Sie Führen Sie es hier live online aus.

// By Bruno Haible
// 24 Oct. 2009
// Source: https://lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html

// =============== Program for determining the default thread stack size =========

#include <alloca.h>
#include <pthread.h>
#include <stdio.h>
void* threadfunc (void*p) {
  int n = 0;
  for (;;) {
    printf("Allocated %d bytes\n", n);
    fflush(stdout);
    n += 128;
    *((volatile char *) alloca(128)) = 0;
  }
}

int main()
{
  pthread_t thread;
  pthread_create(&thread, NULL, threadfunc, NULL);
  for (;;) {}
}

Wenn ich es über den obigen Link auf GDBOnline ausführe, erhalte ich jedes Mal, wenn ich es ausführe, genau die gleichen Ergebnisse, sowohl als C- als auch als C++17-Programm. Es dauert ungefähr 10 Sekunden oder so, um zu laufen. Hier sind die letzten paar Zeilen der Ausgabe:

Allocated 7449856 bytes
Allocated 7449984 bytes
Allocated 7450112 bytes
Allocated 7450240 bytes
Allocated 7450368 bytes
Allocated 7450496 bytes
Allocated 7450624 bytes
Allocated 7450752 bytes
Allocated 7450880 bytes
Segmentation fault (core dumped)

Die Thread-Stack-Größe beträgt für dieses System also ~7,45 MB, wie Bruno oben erwähnt hat (7,4 MB).

Ich habe ein paar Änderungen am Programm vorgenommen, hauptsächlich nur aus Gründen der Übersichtlichkeit, aber auch aus Gründen der Effizienz und ein wenig zum Lernen.

Zusammenfassung meiner Änderungen:

1. [learning] Ich bin vorbeigekommen BYTES_TO_ALLOCATE_EACH_LOOP als Argument für die threadfunc() nur zum Üben der Weitergabe und Verwendung von Generika void* Argumente in C.

   1. Hinweis: Dies ist auch der erforderliche Funktionsprototyp, wie von gefordert der pthread_create() Funktionfür die Callback-Funktion (threadfunc() in meinem Fall) weitergegeben pthread_create(). Sehen: https://www.man7.org/linux/man-pages/man3/pthread_create.3.html.

2. [efficiency] Ich habe den Hauptthread in den Ruhezustand versetzt, anstatt ihn verschwenderisch zu drehen.

3. [clarity] Ich habe ausführlichere Variablennamen hinzugefügt, wie z BYTES_TO_ALLOCATE_EACH_LOOP und bytes_allocated.

4. [clarity] Ich habe das geändert:

    *((volatile char *) alloca(128)) = 0;
   

   dazu:

    volatile uint8_t * byte_buff = 
            (volatile uint8_t *)alloca(BYTES_TO_ALLOCATE_EACH_LOOP);
    byte_buff[0] = 0;
   

Hier ist mein modifiziertes Testprogramm, das genau das Gleiche tut wie das von Bruno und sogar die gleichen Ergebnisse hat:

Du kannst Führen Sie es hier online ausoder Laden Sie es hier von meinem Repo herunter. Wenn Sie es lokal von meinem Repo ausführen möchten, hier sind die Build- und Run-Befehle, die ich zum Testen verwendet habe:

1. Erstellen und führen Sie es als C-Programm aus:

    mkdir -p bin && \
    gcc -Wall -Werror -g3 -O3 -std=c11 -pthread -o bin/tmp \
    onlinegdb--empirically_determine_max_thread_stack_size_GS_version.c && \
    time bin/tmp
   

2. Erstellen und führen Sie es als C++-Programm aus:

    mkdir -p bin && \
    g++ -Wall -Werror -g3 -O3 -std=c++17 -pthread -o bin/tmp \
    onlinegdb--empirically_determine_max_thread_stack_size_GS_version.c && \
    time bin/tmp
   

Es dauert < 0,5 Sekunden, um auf einem schnellen Computer mit einer Thread-Stack-Größe von ~7,4 MB lokal ausgeführt zu werden.

Hier ist das Programm:

// =============== Program for determining the default thread stack size =========

// Modified by Gabriel Staples, 26 Sept. 2020

// Originally by Bruno Haible
// 24 Oct. 2009
// Source: https://lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html

#include <alloca.h>
#include <pthread.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <unistd.h> // sleep

/// Thread function to repeatedly allocate memory within a thread, printing
/// the total memory allocated each time, until the program crashes. The last
/// value printed before the crash indicates how big a thread's stack size is.
///
/// Note: passing in a `uint32_t` as a `void *` type here is for practice,
/// to learn how to pass in ANY type to a func by using a `void *` parameter.
/// This is also the required function prototype, as required by the
/// `pthread_create()` function, for the callback function (this function)
/// passed to `pthread_create()`. See:
/// https://www.man7.org/linux/man-pages/man3/pthread_create.3.html
void* threadfunc(void* bytes_to_allocate_each_loop)
{
    const uint32_t BYTES_TO_ALLOCATE_EACH_LOOP =
            *(uint32_t*)bytes_to_allocate_each_loop;

    uint32_t bytes_allocated = 0;
    while (true)
    {
        printf("bytes_allocated = %u\n", bytes_allocated);
        fflush(stdout);
        // NB: it appears that you don't necessarily need `volatile` here,
        // but you DO definitely need to actually use (ex: write to) the
        // memory allocated by `alloca()`, as we do below, or else the
        // `alloca()` call does seem to get optimized out on some systems,
        // making this whole program just run infinitely forever without
        // ever hitting the expected segmentation fault.
        volatile uint8_t * byte_buff =
                (volatile uint8_t *)alloca(BYTES_TO_ALLOCATE_EACH_LOOP);
        byte_buff[0] = 0;
        bytes_allocated += BYTES_TO_ALLOCATE_EACH_LOOP;
    }
}

int main()
{
    const uint32_t BYTES_TO_ALLOCATE_EACH_LOOP = 128;

    pthread_t thread;
    pthread_create(&thread, NULL, threadfunc,
                   (void*)(&BYTES_TO_ALLOCATE_EACH_LOOP));
    while (true)
    {
        const unsigned int SLEEP_SEC = 10000;
        sleep(SLEEP_SEC);
    }

    return 0;
}

Beispielausgabe (gleiche Ergebnisse wie das ursprüngliche Programm von Bruno Haible):

bytes_allocated = 7450240                                                                                                                                                        
bytes_allocated = 7450368                                                                                                                                                        
bytes_allocated = 7450496                                                                                                                                                        
bytes_allocated = 7450624                                                                                                                                                        
bytes_allocated = 7450752                                                                                                                                                        
bytes_allocated = 7450880                                                                                                                                                        
Segmentation fault (core dumped)