Maksymalny rozmiar stosu programu w C / C ++

Chcę zrobić DFS na macierzy 100 x 100. (Powiedzmy, że elementy tablicy reprezentują węzły grafów) Zatem zakładając najgorszy przypadek, głębokość wywołań funkcji rekurencyjnych może dochodzić do 10000, a każde wywołanie zajmuje do powiedzmy 20 bajtów. Czy jest to wykonalne oznacza, że ​​istnieje możliwość przepełnienia stosu?

Jaki jest maksymalny rozmiar stosu w C / C ++?

Proszę określić dla gcc dla obu
1) cygwin w Windows
2) Unix

Jakie są ogólne ograniczenia?

W programie Visual Studio domyślny rozmiar stosu to 1 MB, więc przy głębokości rekurencji wynoszącej 10 000 każda ramka stosu może mieć maksymalnie ~ 100 bajtów, co powinno być wystarczające dla algorytmu DFS.

Większość kompilatorów, w tym program Visual Studio, umożliwia określenie rozmiaru stosu. W niektórych (wszystkich?) Wersjach Linuksa rozmiar stosu nie jest częścią pliku wykonywalnego, ale jest zmienną środowiskową w systemie operacyjnym. Następnie możesz sprawdzić rozmiar stosu za pomocą ulimit -si ustawić go na nową wartość, na przykład ulimit -s 16384.

Oto link z domyślnymi rozmiarami stosu dla gcc.

DFS bez rekursji:

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())

stosy nici są często mniejsze. Możesz zmienić wartość domyślną w czasie łączenia lub zmienić również w czasie wykonywania. Dla odniesienia niektóre wartości domyślne to:

• 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

Zależne od platformy, zależne od łańcucha narzędzi, zależne od ulimitów, zależne od parametrów ... Nie jest w ogóle określone i istnieje wiele statycznych i dynamicznych właściwości, które mogą na to wpływać.

Tak, istnieje możliwość przepełnienia stosu. Standardy C i C ++ nie narzucają takich rzeczy, jak głębokość stosu, są to zazwyczaj kwestie środowiskowe.

Większość przyzwoitych środowisk programistycznych i / lub systemów operacyjnych umożliwia dostosowanie rozmiaru stosu procesu, zarówno w czasie łącza, jak i wczytywania.

Powinieneś określić, którego systemu operacyjnego i środowiska programistycznego używasz, aby uzyskać bardziej ukierunkowaną pomoc.

Na przykład w systemie Ubuntu Karmic Koala domyślnym ustawieniem gcc jest zarezerwowane 2M i zatwierdzone 4K, ale można to zmienić po połączeniu programu. Skorzystaj z --stackopcji, ldaby to zrobić.

Po prostu zabrakło mi stosu w pracy, to była baza danych i uruchamiała kilka wątków, w zasadzie poprzedni programista wrzucił dużą tablicę na stos, a stos i tak był niski. Oprogramowanie zostało skompilowane przy użyciu Microsoft Visual Studio 2015.

Mimo że w wątku zabrakło stosu, po cichu zawiódł i kontynuował działanie, przepełnił się tylko wtedy, gdy przyszedł dostęp do zawartości danych na stosie.

Najlepszą radą, jaką mogę dać, jest nie deklarowanie tablic na stosie - szczególnie w złożonych aplikacjach, a zwłaszcza w wątkach, zamiast tego używaj sterty. Po to tam jest;)

Pamiętaj też, że może się to nie udać natychmiast po zadeklarowaniu stosu, ale tylko przy dostępie. Domyślam się, że kompilator deklaruje stos pod oknami „optymistycznie”, tj. Zakłada, że ​​stos został zadeklarowany i ma wystarczającą wielkość, dopóki nie zacznie go używać, a następnie stwierdzi, że stosu tam nie ma.

Różne systemy operacyjne mogą mieć różne zasady deklaracji stosu. Proszę zostaw komentarz, jeśli znasz te zasady.

Nie jestem pewien, co masz na myśli, wykonując najpierw wyszukiwanie w głębi na prostokątnej tablicy, ale zakładam, że wiesz, co robisz.

Jeśli limit stosu jest problemem, powinieneś być w stanie przekonwertować rozwiązanie rekurencyjne na rozwiązanie iteracyjne, które wypycha wartości pośrednie na stos przydzielony ze sterty.