Maksymalny rozmiar stosu programu w C / C ++

115

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?

avd
źródło
11
Wiesz, że możesz zaimplementować przeszukiwanie w głąb bez rekursji, prawda?
Sebastian
4
Nie, nie wiem, proszę wyjaśnij.
śr.
1
Zrobiłem mały przykład DFS bez rekursji w mojej odpowiedzi
Andreas Brinck,
56
plus jeden za pytanie dotyczące rzeczywistego przepełnienia stosu
Sam Watkins,
3
@SamWatkins tak, jednym z największych problemów związanych z nazwą Stack Overflow jest to, że mogę sprawdzić „przepełnienie stosu” w Google i znaleźć się na tej stronie, ale niekoniecznie / mniej prawdopodobne w pytaniach o przepełnienie stosu ...
lalilulelost

Odpowiedzi:

106

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())
Andreas Brinck
źródło
12
I tak dla odniesienia, BFS jest taki sam, z wyjątkiem tego, że zamiast stosu używasz FIFO.
Steve Jessop
Tak, lub w STL-lingo użyj std :: deque z pop_front / push_back
Andreas Brinck,
Twój DFS z wynikami na stosie będzie inny niż wersja rekurencyjna. W niektórych przypadkach nie ma to znaczenia, ale w innych (np. W sortowaniu topologicznym) otrzymasz błędne wyniki
spin_eight
Tak, domyślny limit dla VS to rzeczywiście 1 MB. Więcej informacji i sposób ustawienia innej wartości można znaleźć w dokumentacji firmy Microsoft: msdn.microsoft.com/en-us/library/tdkhxaks(v=vs.140).aspx
FrankS101
Wolę używać jawnej struktury danych stosu dla takich algorytmów, zamiast rekurencji, aby 1. nie zależały od rozmiaru stosu systemowego, 2. Mogły zmienić algorytm, aby używał innej struktury danych, np. Kolejka lub kolejka priorytetowa bez rzucania cały kod.
Sam Watkins
47

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
pixelbeat
źródło
14
Określone empirycznie przez Bruno Haible lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html
pixelbeat
17

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ć.

DrPizza
źródło
4
Nie ma „ogólnych ograniczeń”. W systemie Windows, z domyślnymi opcjami konsolidatora VC ++ i domyślnym zachowaniem CreateThread, zwykle około 1 MB na wątek. Uważam, że w systemie Linux z nieograniczoną liczbą użytkowników nie ma ograniczeń (stos może po prostu rosnąć w dół, aby zająć prawie całą przestrzeń adresową). Zasadniczo, jeśli musisz zapytać, nie powinieneś używać stosu.
DrPizza
1
W systemach wbudowanych możesz mieć 4k lub mniej. W takim przypadku musisz zapytać, nawet jeśli rozsądne jest użycie stosu. Odpowiedzią jest zwykle galijskie wzruszenie ramionami.
Steve Jessop
1
Ach, prawda, także często w trybie jądra.
DrPizza
6

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ć.

paxdiablo
źródło
2
@lex: nie ma żadnych ogólnych ograniczeń. To zależy od wielu parametrów.
Michael Foukarakis
@paxdiablo: Co oznacza zarezerwowanie i zobowiązanie?
śr.
2
Zarezerwowana to ilość przestrzeni adresowej do przydzielenia, zatwierdzona to ilość, do której należy dołączyć pamięć zapasową. Innymi słowy, zarezerwowanie przestrzeni adresowej nie oznacza, że ​​pamięć będzie tam, gdy jej potrzebujesz. Jeśli nigdy nie użyjesz stosu więcej niż 4K, nie marnujesz prawdziwej pamięci na pozostałe 1,6 MB. Jeśli chcesz zagwarantować, że będzie wystarczająco dużo stosu, zarezerwowane i zatwierdzone powinny być identyczne.
paxdiablo
3
@paxdiablo 2M - 4k to nie 1,6M. Tylko mówię. (wprawił mnie w zakłopotanie, gdy przeczytałem twój komentarz w pierwszych 3 przypadkach)
griffin
2
@griffin, chwała dla pierwszej osoby, która to złapie od ponad 3 lat. Oczywiście chodziło mi o „resztę” - uniknę rzeczywistej liczby, żeby nie popełnić kolejnego możliwego błędu :-)
paxdiablo
5

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.

Sowa
źródło
3

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.

Dave Kirby
źródło