C / C ++ tamaño máximo de la stack del progtwig

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?

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

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

¿Cuáles son los límites generales?

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

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

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

DFS sin recursión:

 std::stack 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()) 

las stacks para hilos a menudo son más pequeñas. Puede cambiar el valor predeterminado en tiempo de enlace, o cambiar en tiempo de ejecución tambié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

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

Sí, hay una posibilidad de desbordamiento de stack. Los estándares C y C ++ no dictan cosas como la profundidad de la stack, 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 stack 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 progtwig. Use la opción --stack de ld para hacer eso.

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

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

Me quedé sin stack 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 stack, y la stack estaba baja de todos modos. El software fue comstackdo utilizando Microsoft Visual Studio 2015.

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

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

También tenga en cuenta que no puede fallar inmediatamente al declarar la stack, pero solo en el acceso. Mi suposición es que el comstackdor declara la stack debajo de Windows “de manera optimista”, es decir, asumirá que la stack ha sido declarada y tiene el tamaño suficiente hasta que llegue el momento de usarla, y luego se entera de que la stack no está allí.

Los diferentes sistemas operativos pueden tener diferentes políticas de statement de stack. Por favor, deje un comentario si sabe cuáles son estas políticas.