Dimensione massima pila C/C++ del programma

Question

Voglio fare DFS su un array 100 X 100. (Dire elementi dell'array rappresenta i nodi del grafico) Quindi, supponendo il caso peggiore, la profondità delle chiamate ricorsive può arrivare fino a 10000 con ogni chiamata che accetta fino a dire 20 byte. Quindi è fattibile significa c'è una possibilità di stackoverflow?

Qual è la dimensione massima dello stack in C/C++?

Si prega di specificare per gcc sia per Cygwin
1) su Windows
2) Unix

Quali sono i limiti generali?

Answer 1

In Visual Studio la dimensione dello stack predefinita è 1 MB, quindi con una profondità di ricorsione di 10.000 ogni frame dello stack può essere al massimo ~ 100 byte, che dovrebbe essere sufficiente per un algoritmo DFS.

maggior parte dei compilatori tra cui Visual Studio consentono di specificare la dimensione dello stack. Su alcuni (tutti?) I sapori di Linux la dimensione dello stack non fa parte dell'eseguibile ma una variabile di ambiente nel sistema operativo. È quindi possibile controllare le dimensioni dello stack con ulimit -s e impostarlo su un nuovo valore, ad esempio ulimit -s 16384.

Ecco uno link con dimensioni di stack predefinite per gcc.

DFS senza ricorsione:

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

Answer 2

dipendente dalla piattaforma, dipendente dalla toolchain, dipendente da ulimit, dipendente dai parametri .... Non è affatto specificato e ci sono molte proprietà statiche e dinamiche che possono influenzarlo.

Answer 3

Sì, c'è una possibilità di overflow dello stack. Lo standard C e C++ non dettano cose come la profondità dello stack, quelle in genere sono un problema ambientale.

ambienti di sviluppo più decente e/o sistemi operativi vi permetterà di personalizzare la dimensione dello stack di un processo, sia al collegamento o tempo di caricamento.

è necessario specificare quale ambiente OS e lo sviluppo che si sta utilizzando per l'assistenza più mirato.

Per esempio, sotto Ubuntu Karmic Koala, il valore predefinito per gcc è 2M riservato e 4K impegnati, ma questo può essere cambiato quando si collega il programma. Utilizzare l'opzione --stack di ld per farlo.

Answer 4

pile di fili sono spesso più piccoli. È possibile modificare l'impostazione predefinita al momento del collegamento, o modificare in fase di esecuzione anche. Per riferimento alcuni valori di default sono:

• 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

Answer 5

Non sono sicuro di cosa si intende per fare una ricerca in profondità su una matrice rettangolare, ma suppongo si sa cosa si sta facendo.

Se il limite di stack è un problema, dovresti essere in grado di convertire la tua soluzione ricorsiva in una soluzione iterativa che spinge i valori intermedi in uno stack che è allocato dall'heap.

Answer 6

Ho appena esaurito lo stack al lavoro, era un database ed eseguiva alcuni thread, in pratica lo sviluppatore precedente aveva gettato una grande matrice nello stack e lo stack era basso in ogni caso. Il software è stato compilato utilizzando Microsoft Visual Studio 2015.

Anche se il thread aveva esaurito lo stack, è stato interrotto in modo silenzioso e proseguito, esso si è sovrapposto solo quando si è trattato di accedere al contenuto dei dati nello stack.

Il miglior consiglio che posso dare è quello di non dichiarare matrici sullo stack - soprattutto in applicazioni complesse e in particolare nei thread, invece di usare heap. Ecco a cosa serve:)

Inoltre, tieni presente che potrebbe non fallire immediatamente quando si dichiara lo stack, ma solo per l'accesso. La mia ipotesi è che il compilatore dichiari lo stack sotto Windows "ottimisticamente", cioè supporterà che lo stack sia stato dichiarato ed abbia dimensioni sufficienti fino al momento in cui lo si usa e poi scopre che lo stack non è lì.

Diversi sistemi operativi possono avere diverse politiche di dichiarazione dello stack. Per favore lascia un commento se sai quali sono queste politiche.