C/C++ tamaño de pila máximo del programa

Quiero hacer DFS en una matriz de 100 X 100. (Diga los elementos de la matriz representa los nodos de gráfico) Asumiendo el peor de los casos, la profundidad de las llamadas a funciones recursivas puede llegar a 10000 con cada llamada que tome hasta 20 bytes. Entonces, ¿es factible significa que hay una posibilidad de stackoverflow?C/C++ tamaño de pila máximo del programa

¿Cuál es el tamaño máximo de la pila en C/C++?

Por favor especificar para gcc para ambos
1) cygwin en Windows
2) Unix

Cuáles son los límites generales?

Fuente

2009-12-01 avd

¿Sabía que puede implementar búsquedas en profundidad sin recurrencia, ¿verdad? – Sebastian

No, no lo sé, por favor explique. – avd

He hecho un pequeño ejemplo de DFS sin recursividad en mi respuesta –

En Visual Studio, el tamaño de pila predeterminado es de 1 MB, por lo que con una profundidad de recursión de 10.000, cada marco de pila puede tener como mucho ~ 100 bytes, lo que debería ser suficiente para un algoritmo DFS.

La mayoría de los compiladores, incluido Visual Studio, le permiten especificar el tamaño de la pila. En algunos (todos) los sabores de Linux, el tamaño de la pila no es parte del ejecutable, sino una variable de entorno en el sistema operativo. Luego puede verificar el tamaño de la pila con ulimit -s y establecerlo en un nuevo valor con, por ejemplo, ulimit -s 16384.

Aquí hay un link con tamaños de pila predeterminados para gcc.

DFS sin recursión:

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

Fuente

2009-12-01 12:47:58

Muchas gracias – avd

Y solo como referencia, una BFS es la misma excepto que usted usa una FIFO en lugar de una pila. –

Sí, o en STL-lingo use std :: deque con pop_front/push_back –

Dependiente de la plataforma, dependiente de la cadena de herramientas, dependiente de ulimit, dependiente del parámetro .... No está especificado del todo, y hay muchas propiedades estáticas y dinámicas que pueden influir en él.

Fuente

2009-12-01 12:44:22 DrPizza

¿Cuáles son los límites generales? – avd

No hay "límites generales". En Windows, con las opciones del enlazador de VC++ por defecto y el comportamiento de CreateThread predeterminado, típicamente algo alrededor de 1 MiB por subproceso. En Linux, con un usuario ilimitado, creo que normalmente no hay límite (la pila puede crecer hacia abajo para ocupar casi todo el espacio de direcciones). Básicamente, si tiene que preguntar, no debería usar la pila. – DrPizza

En los sistemas integrados, es posible que tenga 4k o menos. En ese caso, tiene que preguntar incluso si es razonable usar la pila. La respuesta suele ser un encogimiento de hombros galo. –

Sí, existe la posibilidad de desbordamiento de la pila. Los estándares C y C++ no dictan cosas como la profundidad de la pila, generalmente son un problema ambiental.

La mayoría de los entornos de desarrollo decentes y/o sistemas operativos le permitirán adaptar el tamaño de la pila de un proceso, ya sea en el enlace o en el tiempo de carga.

Debe especificar qué sistema operativo y entorno de desarrollo está utilizando para obtener asistencia más específica.

Por ejemplo, en Ubuntu Karmic Koala, el valor predeterminado para gcc es 2M reservado y 4K comprometido, pero esto se puede cambiar cuando se vincula el programa. Use la opción --stack de ld para hacer eso.

Fuente

2009-12-01 12:44:42 paxdiablo

¿Cuáles son los límites generales? – avd

@lex: no hay límites generales. Depende de muchos parámetros. –

@paxdiablo: ¿qué sentido tiene reservado y comprometido? – avd

Stacks para hilos son a menudo más pequeñas. Puede cambiar el valor predeterminado en tiempo de enlace, o cambiar también en tiempo de ejecución. Como referencia algunos valores por defecto son: i386

glibc, 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

Fuente

2009-12-01 13:01:53 pixelbeat

¿Alguna referencia sobre esta información? –

Determinado empíricamente por Bruno Haible http://lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html – pixelbeat

No estoy seguro de lo que entendemos por hacer una primera búsqueda en profundidad en una matriz rectangular, pero supongo que usted sabe lo que está haciendo.

Si el límite de la pila es un problema, debería poder convertir su solución recursiva en una solución iterativa que inserta valores intermedios en una pila que se asigna desde el montón.

Fuente

2009-12-01 13:09:26

Me acabo de quedar sin pila en el trabajo, era una base de datos y estaba ejecutando algunos hilos, básicamente el desarrollador anterior había lanzado una gran matriz en la pila, y la pila estaba baja de todos modos. El software se compiló utilizando Microsoft Visual Studio 2015.

Aunque el hilo se había quedado sin pila, silenciosamente falló y continuó, solo se desbordó la pila cuando se trataba de acceder al contenido de la pila.

El mejor consejo que puedo dar es que no declare matrices en la pila, especialmente en aplicaciones complejas y particularmente en hilos, en su lugar use el montón. Eso es lo que está ahí;)

También tenga en cuenta que no puede fallar inmediatamente al declarar la pila, pero solo en el acceso. Mi suposición es que el compilador declara la pila bajo Windows "de manera optimista", es decir, asumirá que la pila ha sido declarada y tiene el tamaño suficiente hasta que se usa y luego descubre que la pila no está allí.

Diferentes sistemas operativos pueden tener diferentes políticas de declaración de pila. Por favor, deje un comentario si sabe cuáles son estas políticas.

Fuente

2017-08-18 18:13:56 Owl

C/C++ tamaño de pila máximo del programa

Respuesta

Cuestiones relacionadas