Tamaño máximo de pila de programa C/C++ en sistemas operativos convencionales
Quiero hacer DFS en una matriz de 100 X 100. (Digamos que los elementos de la matriz representan nodos del gráfico). Entonces, suponiendo el peor de los casos, la profundidad de las llamadas a funciones recursivas puede llegar hasta 10000 y cada llamada ocupa hasta, digamos, 20 bytes. Entonces, ¿es factible? Significa que existe la posibilidad de que se produzca un desbordamiento de pila.
¿Cuál es el tamaño máximo de pila en C/C++?
Especifique 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 pila predeterminado es 1 MB, 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 (¿todas?) versiones 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 -sy establecerlo en un nuevo valor con, por ejemplo ulimit -s 16384.
Aquí hay un enlace con 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())
Las pilas de hilos suelen ser más pequeñas. Puede cambiar el valor predeterminado en el momento del enlace o también en 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,8MB
- Solaris 7..10: 1MB
- MacOS X 10.5: 460 KB
- AIX 5: 98 KB
- OpenBSD 4.0: 64 KB
- HP-UX 11: 16 KB
Dependiente de la plataforma, dependiente de la cadena de herramientas, dependiente de ulimit, dependiente de parámetros... No está especificado en absoluto y hay muchas propiedades estáticas y dinámicas que pueden influir en él.
(Agregado el 26 de septiembre de 2020)
El 24 de octubre de 2009, como @pixelbeat señaló por primera vez aquí , Bruno Haible descubrió empíricamente los siguientes tamaños de pila de subprocesos predeterminados para varios sistemas. Dijo que en un programa multiproceso, "el tamaño de pila de subprocesos predeterminado es" el siguiente. Agregué en la columna de tamaño "real" porque @Peter.Cordes indica en sus comentarios debajo de mi respuesta, sin embargo, que los números impares probados que se muestran a continuación no incluyen toda la pila de subprocesos, ya que parte de ella se usó en la inicialización. Si corro ulimit -spara ver "el tamaño de pila máximo" para el que está configurada mi computadora Linux, genera 8192kB, que son exactamente 8 MB , no los extraños 7,4 MB que figuran en la siguiente tabla para mi computadora x86-64 con el compilador gcc y glibc. Por lo tanto, probablemente pueda agregar un poco a los números en la siguiente tabla para obtener el tamaño de pila completo real para un subproceso determinado.
Tenga en cuenta también que las siguientes unidades de columna "Probadas" están todas en MB y KB (números de base 1000), NO en MiB y KiB (números de base 1024). Me lo he demostrado a mí mismo verificando el caso de 7,4 MB.
Thread stack sizes
System and std library Tested Actual
---------------------- ------ ------
- glibc i386, x86_64 7.4 MB 8 MiB (8192 KiB, as shown by `ulimit -s`)
- 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 ?
Bruno Haible también afirmó que:
32 KB es más de lo que puede asignar de forma segura en la pila en un programa multiproceso
Y él dijo:
Y el tamaño de pila predeterminado para sigaltstack, SIGSTKSZ, es
- sólo 16 KB en algunas plataformas: IRIX, OSF/1, Haiku.
- sólo 8 KB en algunas plataformas: glibc, NetBSD, OpenBSD, HP-UX, Solaris.
- sólo 4 KB en algunas plataformas: AIX.
bruno
Escribió el siguiente programa sencillo en C para Linux para determinar empíricamente los valores anteriores. Puede ejecutarlo en su sistema hoy para ver rápidamente cuál es el tamaño máximo de pila de subprocesos, o puede ejecutarlo en línea en GDBOnline aquí: https://onlinegdb.com/rkO9JnaHD .
Explicación: Simplemente crea un único subproceso nuevo, para verificar el tamaño de la pila del subproceso y NO el tamaño de la pila del programa , en caso de que difieran, entonces ese subproceso asigna repetidamente 128 bytes de memoria en la pila (NO el montón) . usando la llamada de Linuxalloca() , después de lo cual escribe un 0 en el primer byte de este nuevo bloque de memoria y luego imprime cuántos bytes totales ha asignado. Repite este proceso, asignando 128 bytes más en la pila cada vez, hasta que el programa falla con un Segmentation fault (core dumped)error. El último valor impreso es el tamaño máximo estimado de pila de subprocesos permitido para su sistema.
Nota importante: alloca()asigna en la pila : aunque esto parece una asignación de memoria dinámica en el montón, similar a una malloc()llamada, alloca()NO asigna dinámicamente en el montón. Más bien, alloca()es una función especializada de Linux para asignar "pseudodinámicamente" (no estoy seguro de cómo llamaría a esto, así que ese es el término que elegí) directamente en la pila como si fuera memoria asignada estáticamente. La memoria de pila utilizada y devuelta por alloca()tiene un alcance a nivel de función y, por lo tanto, se "libera automáticamente cuando la función que llamó alloca()regresa a su llamador". Es por eso que no se sale de su alcance estático y la memoria asignada por alloca()NO se libera cada vez que se completa una iteración del bucle y se alcanza forel final del alcance del bucle. forVer man 3 allocapara más detalles. Aquí está la cita pertinente (énfasis añadido):
DESCRIPCIÓN
Laalloca()función asigna bytes de tamaño de espacio en el marco de pila de la persona que llama . Este espacio temporal se libera automáticamente cuando la función que llamóalloca()regresa a su llamador.VALOR DEVUELTO
Laalloca()función devuelve un puntero al comienzo del espacio asignado. Si la asignación provoca un desbordamiento de la pila, el comportamiento del programa no está definido.
Aquí está el programa de Bruno Haible del 24 de octubre de 2009, copiado directamente de la lista de correo de GNU aquí :
Nuevamente, puedes ejecutarlo en vivo en línea aquí .
// By Bruno Haible
// 24 Oct. 2009
// Source: https://lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html
// =============== Program for determining the default thread stack size =========
#include <alloca.h>
#include <pthread.h>
#include <stdio.h>
void* threadfunc (void*p) {
int n = 0;
for (;;) {
printf("Allocated %d bytes\n", n);
fflush(stdout);
n += 128;
*((volatile char *) alloca(128)) = 0;
}
}
int main()
{
pthread_t thread;
pthread_create(&thread, NULL, threadfunc, NULL);
for (;;) {}
}
Cuando lo ejecuto en GDBOnline usando el enlace anterior, obtengo exactamente los mismos resultados cada vez que lo ejecuto, como programa C y C++17. Se tarda unos 10 segundos aproximadamente en ejecutarse. Aquí están las últimas líneas del resultado:
Allocated 7449856 bytes Allocated 7449984 bytes Allocated 7450112 bytes Allocated 7450240 bytes Allocated 7450368 bytes Allocated 7450496 bytes Allocated 7450624 bytes Allocated 7450752 bytes Allocated 7450880 bytes Segmentation fault (core dumped)
Entonces, el tamaño de la pila de subprocesos es ~7,45 MB para este sistema, como Bruno mencionó anteriormente (7,4 MB).
He realizado algunos cambios en el programa, principalmente por claridad, pero también por eficiencia y un poco para aprender.
Resumen de mis cambios:
[aprendizaje] Lo pasé
BYTES_TO_ALLOCATE_EACH_LOOPcomo argumento solothreadfunc()para practicar pasando y usandovoid*argumentos genéricos en C.- Nota: Este también es el prototipo de función requerido, según lo requiere la
pthread_create()función , para la función de devolución de llamada (threadfunc()en mi caso) pasada apthread_create(). Ver: https://www.man7.org/linux/man-pages/man3/pthread_create.3.html .
- Nota: Este también es el prototipo de función requerido, según lo requiere la
[eficiencia] Hice que el hilo principal durmiera en lugar de girarlo desperdiciadamente.
[claridad] Agregué nombres de variables más detallados, como
BYTES_TO_ALLOCATE_EACH_LOOPybytes_allocated.[claridad] Cambié esto:
*((volatile char *) alloca(128)) = 0;a esto:
volatile uint8_t * byte_buff = (volatile uint8_t *)alloca(BYTES_TO_ALLOCATE_EACH_LOOP); byte_buff[0] = 0;
Aquí está mi programa de prueba modificado, que hace exactamente lo mismo que el de Bruno, e incluso tiene los mismos resultados:
Puede ejecutarlo en línea aquí o descargarlo desde mi repositorio aquí . Si elige ejecutarlo localmente desde mi repositorio, aquí están los comandos de compilación y ejecución que utilicé para las pruebas:
Compílelo y ejecútelo como un programa en C:
mkdir -p bin && \ gcc -Wall -Werror -g3 -O3 -std=c11 -pthread -o bin/tmp \ onlinegdb--empirically_determine_max_thread_stack_size_GS_version.c && \ time bin/tmpCompílelo y ejecútelo como un programa C++:
mkdir -p bin && \ g++ -Wall -Werror -g3 -O3 -std=c++17 -pthread -o bin/tmp \ onlinegdb--empirically_determine_max_thread_stack_size_GS_version.c && \ time bin/tmp
Se necesitan <0,5 segundos para ejecutarse localmente en una computadora rápida con un tamaño de pila de subprocesos de ~7,4 MB.
Aquí está el programa:
// =============== Program for determining the default thread stack size =========
// Modified by Gabriel Staples, 26 Sept. 2020
// Originally by Bruno Haible
// 24 Oct. 2009
// Source: https://lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html
#include <alloca.h>
#include <pthread.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <unistd.h> // sleep
/// Thread function to repeatedly allocate memory within a thread, printing
/// the total memory allocated each time, until the program crashes. The last
/// value printed before the crash indicates how big a thread's stack size is.
///
/// Note: passing in a `uint32_t` as a `void *` type here is for practice,
/// to learn how to pass in ANY type to a func by using a `void *` parameter.
/// This is also the required function prototype, as required by the
/// `pthread_create()` function, for the callback function (this function)
/// passed to `pthread_create()`. See:
/// https://www.man7.org/linux/man-pages/man3/pthread_create.3.html
void* threadfunc(void* bytes_to_allocate_each_loop)
{
const uint32_t BYTES_TO_ALLOCATE_EACH_LOOP =
*(uint32_t*)bytes_to_allocate_each_loop;
uint32_t bytes_allocated = 0;
while (true)
{
printf("bytes_allocated = %u\n", bytes_allocated);
fflush(stdout);
// NB: it appears that you don't necessarily need `volatile` here,
// but you DO definitely need to actually use (ex: write to) the
// memory allocated by `alloca()`, as we do below, or else the
// `alloca()` call does seem to get optimized out on some systems,
// making this whole program just run infinitely forever without
// ever hitting the expected segmentation fault.
volatile uint8_t * byte_buff =
(volatile uint8_t *)alloca(BYTES_TO_ALLOCATE_EACH_LOOP);
byte_buff[0] = 0;
bytes_allocated += BYTES_TO_ALLOCATE_EACH_LOOP;
}
}
int main()
{
const uint32_t BYTES_TO_ALLOCATE_EACH_LOOP = 128;
pthread_t thread;
pthread_create(&thread, NULL, threadfunc,
(void*)(&BYTES_TO_ALLOCATE_EACH_LOOP));
while (true)
{
const unsigned int SLEEP_SEC = 10000;
sleep(SLEEP_SEC);
}
return 0;
}
Salida de muestra (los mismos resultados que el programa original de Bruno Haible):
bytes_allocated = 7450240 bytes_allocated = 7450368 bytes_allocated = 7450496 bytes_allocated = 7450624 bytes_allocated = 7450752 bytes_allocated = 7450880 Segmentation fault (core dumped)
