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

115

Quiero hacer DFS en una matriz de 100 X 100. (Digamos que los elementos de la matriz representan nodos de gráficos) Por lo tanto, asumiendo el peor de los casos, la profundidad de las llamadas a funciones recursivas puede llegar hasta 10000 y cada llamada ocupa hasta 20 bytes. Entonces, ¿es factible? ¿Existe la posibilidad de un desbordamiento de pila?

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

Especifique gcc para
1) cygwin en Windows
2) Unix

¿Cuáles son los límites generales?

c++ c stack avd
fuente
11
Sabes que puedes implementar una búsqueda en profundidad sin recursividad, ¿verdad?
Sebastian
4
No, no lo sé, por favor explique.
avd
1
Hice un pequeño ejemplo de DFS sin recursividad en mi respuesta
Andreas Brinck
56
más uno para una pregunta sobre el desbordamiento de pila real
Sam Watkins
3
@SamWatkins sí, uno de los mayores problemas a mí con el nombre de desbordamiento de pila es que pueda mirar hacia arriba "desbordamiento de pila" en Google y terminar en este sitio web, pero no necesariamente / menos probable en preguntas sobre la pila se desborda ...
lalilulelost

Respuestas:

106

En Visual Studio, el tamaño de pila predeterminado es de 1 MB, creo, por lo que con una profundidad de recursividad de 10,000, cada marco de pila puede tener como máximo ~ 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 algunas versiones de Linux (¿todas?), El tamaño de la pila no es parte del ejecutable sino una variable de entorno en el sistema operativo. A continuación, puede comprobar el tamaño de la pila con ulimit -sy establecerlo en un nuevo valor con, por ejemplo ulimit -s 16384.

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

DFS sin recursividad:

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
fuente
12
Y solo como referencia, un BFS es lo mismo, excepto que usa un FIFO en lugar de una pila.
Steve Jessop
Sí, o en STL-lingo use un std :: deque con pop_front / push_back
Andreas Brinck
su DFS con resultados de pila será diferente de la versión de recursividad. En algunos casos no importa, pero en otros (por ejemplo, en clasificación topológica) obtendrá resultados incorrectos
spin_eight
Sí, el límite predeterminado para VS es de 1 MB. Puede encontrar más información y la forma de establecer un valor diferente en la documentación de Microsoft: msdn.microsoft.com/en-us/library/tdkhxaks(v=vs.140).aspx
FrankS101
Prefiero usar una estructura de datos de pila explícita para tales algoritmos, en lugar de la recursividad, de modo que 1. no dependa del tamaño de la pila del sistema, 2. pueda cambiar el algoritmo para usar una estructura de datos diferente, por ejemplo, cola o cola de prioridad sin lanzar todo el código.
Sam Watkins
47

las pilas de hilos suelen ser más pequeñas. Puede cambiar el valor predeterminado en el momento del enlace o también en el tiempo de ejecución. Como referencia, algunos valores predeterminados son:

  • 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
fuente
14
Determinado empíricamente por Bruno Haible lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html
pixelbeat
17

Dependiente de la plataforma, dependiente de la cadena de herramientas, dependiente de ulimit, dependiente de los parámetros ... No se especifica en absoluto, y hay muchas propiedades estáticas y dinámicas que pueden influir en él.

DrPizza
fuente
4
No hay "límites generales". En Windows, con las opciones predeterminadas del vinculador VC ++ y el comportamiento predeterminado CreateThread, normalmente algo alrededor de 1 MiB por hilo. 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 tienes que preguntar, no deberías usar la pila.
DrPizza
1
En sistemas integrados, es posible que tenga 4k o menos. En cuyo caso, debe preguntar incluso cuando sea razonable usar la pila. La respuesta suele ser un encogimiento de hombros galo.
Steve Jessop
1
Ah, cierto, también suele ser el caso en modo kernel.
DrPizza
6

Sí, existe la posibilidad de que la pila se desborde. El estándar C y C ++ no dicta cosas como la profundidad de la pila, generalmente son un problema ambiental.

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

Debe especificar qué sistema operativo y entorno de desarrollo está utilizando para obtener una 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 al vincular el programa. Utilice la --stackopción de ldpara hacer eso.

paxdiablo
fuente
2
@lex: no hay límites generales. Depende de muchos parámetros.
Michael Foukarakis
@paxdiablo: ¿Qué significa reservado y comprometido?
avd
2
Reservado es la cantidad de espacio de direcciones que se debe asignar, comprometido es a cuánto se adjunta el almacenamiento de respaldo. En otras palabras, reservar espacio de direcciones no significa que la memoria estará allí cuando la necesite. Si nunca usa más de 4K stack, no está desperdiciando memoria real para los otros 1.6M. Si desea garantizar que habrá suficiente pila, reservado y comprometido deben ser idénticos.
paxdiablo
2
@paxdiablo 2M - 4k no es 1.6M. Solo digo. (me confundió las primeras 3 veces que leí su comentario)
griffin
2
@griffin, felicitaciones por ser la primera persona en captar eso en más de 3 años. Por supuesto, quise decir "resto"
Evitaré
5

Me quedé sin pila en el trabajo, era una base de datos y estaba ejecutando algunos subprocesos, 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ó con Microsoft Visual Studio 2015.

A pesar de que el hilo se había quedado sin pila, falló silenciosamente y continuó, solo se desbordó la pila cuando llegó el momento de acceder al contenido de los datos en la pila.

El mejor consejo que puedo dar es no declarar matrices en la pila, especialmente en aplicaciones complejas y particularmente en subprocesos, en su lugar use heap. Para eso está ahí;)

También tenga en cuenta que puede que no falle inmediatamente al declarar la pila, sino solo en el acceso. Supongo que el compilador declara la pila en Windows de forma "optimista", es decir, asumirá que la pila ha sido declarada y tiene el tamaño suficiente hasta que la utilice y luego descubra que la pila no está allí.

Los diferentes sistemas operativos pueden tener diferentes políticas de declaración de pila. Deje un comentario si conoce estas políticas.

Búho
fuente
3

No estoy seguro de lo que quiere decir con hacer una búsqueda en profundidad en una matriz rectangular, pero supongo que 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 inserte valores intermedios en una pila que se asigna desde el montón.

Dave Kirby
fuente