programming languages - ¿Por qué los desbordamientos de pila siguen siendo un problema?
programming-languages stack (11)
Esta pregunta me desconcierta durante años y, teniendo en cuenta el nombre de este sitio, este es el lugar para preguntar.
¿Por qué nosotros, los programadores, todavía tenemos este problema de StackOverflow ?
¿Por qué en todos los lenguajes principales la memoria de la pila de hilos debe asignarse estáticamente en la creación del hilo?
Hablaré en el contexto de C # / Java, porque los uso más, pero este es probablemente un problema más amplio.
El tamaño de pila fijo genera enormes problemas:
- No hay forma de escribir un algoritmo recursivo a menos que esté absolutamente seguro de que la profundidad de la recursión es pequeña. La complejidad de la memoria lineal del algoritmo recursivo a menudo es inaceptable.
- No hay una forma barata de iniciar nuevos hilos. Debe asignar un gran bloque de memoria para que stack tenga en cuenta todos los usos posibles del hilo.
- Incluso si no usa recursividad muy profunda, siempre corre el riesgo de quedarse sin espacio en la pila porque el tamaño de la pila es un número fijo arbitrario. Teniendo en cuenta que el StackOverflow suele ser irrecuperable, este es un gran problema para mí.
Ahora, si la pila se cambiara de tamaño dinámicamente, todos los problemas anteriores se aliviarían mucho, porque el desbordamiento de la pila solo sería posible cuando hay un desbordamiento de la memoria.
Pero este no es el caso todavía. ¿Por qué? ¿Existen algunas limitaciones fundamentales de las CPU modernas que lo harían imposible / ineficiente? Si piensas en el impacto en el rendimiento que impondrían las reasignaciones, debería ser aceptable porque las personas usan estructuras como ArrayList todo el tiempo sin sufrir demasiado.
Entonces, la pregunta es, ¿me estoy perdiendo algo y el StackOverflow no es un problema, o me estoy perdiendo algo y hay muchos idiomas con stack dinámico, o hay alguna razón importante para que esto sea imposible / difícil de implementar?
Editar: Algunas personas dijeron que el rendimiento sería un gran problema, pero considera esto:
- Dejamos intacto el código compilado. El acceso a la pila se mantiene igual, por lo que el rendimiento del "caso habitual" permanece igual.
- Manejamos una excepción de CPU que ocurre cuando el código intenta acceder a la memoria no asignada y ejecuta nuestra rutina de "reasignación". Las reasignaciones no serán frecuentes porque <pone aquí su argumento ArrayList habitual>. Debería funcionar en la mayoría de las CPU en modo protegido sin pérdida de rendimiento. ¿No?
¿Por qué en todos los lenguajes principales la memoria de la pila de hilos debe asignarse estáticamente en la creación del hilo?
El tamaño y la asignación de la pila no está necesariamente relacionado con el idioma que está utilizando. Es más una cuestión de procesador y arquitectura.
Los segmentos de pila están limitados a 4 GB en los procesadores Intel actuales.
Este siguiente enlace es una buena lectura, que puede darle algunas de las respuestas que busca.
http://www.intel.com/Assets/PDF/manual/253665.pdf - Capítulo 6.2
¿Por qué nosotros, los programadores, todavía tenemos este problema de ?
La pila de tamaño fijo es fácil de implementar y es aceptable para el 99% de los programas. "desbordamiento de pila" es un problema menor, que es algo raro. Entonces no hay una razón real para cambiar las cosas. Además, no es un problema de idioma, está más relacionado con el diseño de la plataforma / procesador, por lo que deberá lidiar con él.
No hay forma de escribir un algoritmo recursivo a menos que esté absolutamente seguro de que la profundidad de la recursión es pequeña. La complejidad de la memoria lineal del algoritmo recursivo a menudo es inaceptable.
Ahora esto es incorrecto En el algoritmo recursivo puede (¿casi?) Reemplazar siempre la llamada recursiva real con algún tipo de contenedor -list, std :: vector, stack , array, FIFO queue, etc., que actuará como stack. El cálculo "explotará" argumentos desde el final del contenedor e insertará nuevos argumentos en el extremo o en el principio del contenedor. Normalmente, el único límite de tamaño de dicho contenedor es la cantidad total de RAM.
Aquí hay un ejemplo crudo de C ++:
#include <deque>
#include <iostream>
size_t fac(size_t arg){
std::deque<size_t> v;
v.push_back(arg);
while (v.back() > 2)
v.push_back(v.back() - 1);
size_t result = 1;
for (size_t i = 0; i < v.size(); i++)
result *= v[i];
return result;
}
int main(int argc, char** argv){
int arg = 12;
std::cout << " fac of " << arg << " is " << fac(arg) << std::endl;
return 0;
}
Menos elegante que la recursión, pero no hay problema de acumulación de stack. Técnicamente, estamos "emulando" la recursión en este caso. Puedes pensar que es una limitación de hardware con la que tienes que lidiar.
1) Para cambiar el tamaño de las pilas, debe poder mover la memoria, lo que significa que los punteros a cualquier elemento de una pila pueden dejar de ser válidos después de cambiar el tamaño de la pila. Sí, puedes usar otro nivel de indirección para resolver este problema, pero recuerda que la pila se usa muy, muy frecuentemente.
2) Hace que las cosas sean más complicadas. Las operaciones push / pop en las pilas normalmente funcionan simplemente haciendo aritmética de un puntero en un registro de la CPU. Es por eso que la asignación en una pila es más rápida que la asignación en la tienda libre.
3) Algunas CPU (en particular los microcontroladores) implementan la pila directamente en el hardware, separado de la memoria principal.
Además, puedes establecer el tamaño de una pila de un hilo cuando creas un hilo nuevo usando beginthread() , por lo que si encuentras que el espacio extra de la pila no es necesario, puedes establecer el tamaño de la pila en consecuencia.
Desde mi experiencia, los desbordamientos de pila suelen ser causados por infinitas recursiones o funciones recursivas que asignan enormes matrices a la pila. Según MSDN, el tamaño de pila predeterminado establecido por el vinculador es de 1 MB (el encabezado de los archivos ejecutables puede establecer su propio valor predeterminado) , que parece ser más que suficiente para la mayoría de los casos.
El mecanismo de pila fija funciona lo suficientemente bien para la mayoría de las aplicaciones, por lo que no es necesario cambiarlo. Si no es así, siempre puedes desplegar tu propia pila.
Creo que veremos esta restricción eliminada en unos años.
Simplemente no hay una razón técnica fundamental para los apilamientos de tamaño fijo. Existen por razones históricas y porque los programadores de compiladores y máquinas virtuales son flojos y no optimizan si es lo suficientemente bueno en este momento.
Pero GO, el lenguaje de Google ya comienza con un enfoque diferente. Asigna la pila en pequeñas piezas de 4K. También hay muchas extensiones de lenguaje de programación "apilables" como python sin pila, etc. que hacen lo mismo.
La razón de esto es bastante simple, cuantos más hilos tenga, más espacio de direcciones se desperdicia. Para los programas que son más lentos con punteros de 64 bits, es un problema grave. Realmente no puedes tener más hilos de caza en la práctica. Esto no es bueno si escribe un servidor que podría querer server 60000 clientes con un hilo para cada uno (espere los 100 sistemas core / cpu en el futuro cercano).
En sistemas de 64 bits no es tan grave, pero aún requiere más recursos. Por ejemplo, las entradas de TLB para páginas son extremadamente serias para un buen rendimiento. Si puede satisfacer 4000 apilamientos de subprocesos normales con una sola entrada TLB (dado un tamaño de página de 16 MB y 4 KB de espacio de pila activa), puede ver la diferencia. No desperdicie 1020KB solo por pilas que casi nunca usa.
El multihilado de grano pequeño será una técnica muy muy importante en el futuro.
Cualquier código que causaría un desbordamiento de pila en una pila típica de longitud estática es incorrecto de todos modos.
- Podrías hacer de la pila un objeto estándar como un vector, pero tendrías un rendimiento extremadamente impredecible cuando decidiera redimensionar, y de todos modos, lo más probable es que sigas haciéndolo hasta que todo el montón se haya agotado también, y eso es más molesto
- Puede hacer que sea como una lista estándar, donde creció en O (1). Sin embargo, la aritmética del puntero utilizada en una pila estática es tan absolutamente crítica en todos los sentidos para que el rendimiento del programa sea inútilmente lento. Los lenguajes se inventaron para tener un valor de retorno y un número arbitrario de parámetros de entrada porque eso es lo que se ajusta al paradigma aritmético de pila / puntero estático.
Así que una pila dinámicamente redimensionable sería A) una pesadilla de rendimiento y B) sin valor de todos modos, ya que tu stack no debería haber llegado tan profundo.
Las implementaciones de idiomas antiguos tienen un tamaño de pila estático, por lo que la mayoría de los nuevos lenguajes populares (que solo copiaron idiomas antiguos y rompieron / arreglaron lo que sintieran) tienen el mismo problema.
No hay ninguna razón lógica para tener un tamaño de pila estática a menos que esté en una configuración de métodos formales. ¿Por qué introducir fallas donde el código es correcto? Erlang, por ejemplo, no hace esto, ya que maneja fallas, como debería hacer cualquier lenguaje de programación parcial.
Las pilas se cambian de tamaño dinámicamente o, para ser precisas, se cultivan dinámicamente. Obtiene un desbordamiento cuando una pila no puede crecer más, lo que no quiere decir que agota el espacio de direcciones, sino que crece para entrar en conflicto con una parte de la memoria utilizada para otros fines (por ejemplo, un montón de procesos).
¿Quizás quieres decir que las pilas no se pueden mover dinámicamente? La raíz de eso es, probablemente, que las pilas están íntimamente acopladas al hardware. Las CPU tienen registros y montones de lógica dedicados a la administración de la pila de hilos (esp, ebp, instrucciones call / return / enter / leave en x86). Si tu lenguaje está compilado (o incluso jodido), estás vinculado al mecanismo de hardware y no puedes mover pilas.
Esta ''limitación'' de hardware probablemente haya llegado para quedarse. Volver a basar una pila de subprocesos durante la ejecución del subproceso parece lejos de una demanda razonable de una plataforma de hardware (y la complejidad añadida obstaculizaría gravemente todo el código ejecutado en una CPU tan imaginaria, incluso compilada). Uno puede imaginar un entorno completamente virtualizado donde esta limitación no se cumple, pero dado que tal código no podría ser jodido, sería insoportablemente lento. No hay posibilidad de que puedas hacer algo interactivo con eso.
No puedo hablar por "idiomas principales". Muchos lenguajes "menores" hacen registros de activación asignados en el montón, con cada llamada usando un pedazo de espacio de almacenamiento dinámico en lugar de un bloque lineal. Esto permite que la recursión sea tan profunda como tenga espacio de direcciones para asignar.
Algunas personas afirman que la recursividad es tan profunda, y que usar una "gran pila lineal" está bien. Eso no es correcto. Estoy de acuerdo en que si tiene que usar todo el espacio de direcciones, usted hace un problema de algún tipo. Sin embargo, cuando uno tiene estructuras de árbol o gráfico muy grandes, quiere permitir una recursión profunda y no quiere adivinar cuánto espacio de pila lineal necesita primero, porque adivinará mal.
Si decides ir en paralelo, y tienes muchos (miles o millones de "granos" [piense, pequeños hilos]) no puedes tener 10Mb de espacio de pila asignados a cada hilo, porque estarás desperdiciando gigabytes de RAM. ¿Cómo demonios podrías tener un millón de granos? Fácil: muchos granos que se entrelazan entre sí; cuando un grano está congelado esperando un bloqueo, no puede deshacerse de él, y aún así desea ejecutar otros granos para usar sus CPU disponibles. Esto maximiza la cantidad de trabajo disponible y, por lo tanto, permite que muchos procesadores físicos se utilicen de manera efectiva.
El PARLANSE programación paralelo PARLANSE utiliza este gran número de modelos de granos paralelos y asignación de pila en llamadas a funciones. Diseñamos PARLANSE para permitir el análisis simbólico y la transformación de programas informáticos fuente muy grandes (por ejemplo, varios millones de líneas de código). Estos producen ... árboles de sintaxis abstractos gigantes, gráficos gigantescos de control / flujo de datos, tablas de símbolos gigantes, con decenas de millones de nodos. Mucha oportunidad para trabajadores paralelos.
La asignación de montón permite que los programas PARLANSE tengan un alcance léxico, incluso a través de los límites de paralelismo, porque uno puede implementar "la pila" como una pila de cactus, donde las horquillas se encuentran en "la pila" para subgranos, y cada grano puede ver los registros de activación ( ámbitos primarios) de sus llamadores. Esto hace que las estructuras de Big Data sean baratas cuando se repiten; simplemente haz referencia a ellos léxicamente.
Uno podría pensar que la asignación del montón ralentiza el programa. Lo hace; PARLANSE paga aproximadamente un 5% de penalización en el rendimiento, pero obtiene la capacidad de procesar estructuras muy grandes en paralelo, con tantos granos como pueda contener el espacio de direcciones.
Nunca he encontrado personalmente un desbordamiento de pila que no haya sido causado por una recursión infinita. En estos casos, un tamaño dinámico de pila no ayudaría, solo tardaría un poco más en quedarse sin memoria.
Tener un espacio de pila prácticamente infinito sería muy malo en el caso de una recursión infinita, ya que convertiría un error fácilmente diagnosticado (desbordamiento de pila) en un error mucho más problemático (sin memoria). Con un desbordamiento de la pila, un vistazo al rastro de la pila le dirá con bastante rapidez qué está sucediendo. Alternativamente, cuando el sistema se queda sin memoria, puede intentar otros métodos para solucionarlo, como el uso de espacio de intercambio, lo que da como resultado una degradación grave del rendimiento.
Por otro lado, raramente tuve problemas para golpear la barrera de desbordamiento de la pila debido a la recursión. Sin embargo, puedo pensar en un par de circunstancias donde sucedió. Sin embargo, pasar a mi propia pila implementada como std :: vector era una solución simple al problema.
Ahora, lo que sería genial es si el lenguaje me permitiera marcar una función en particular como "altamente recursiva", y luego hacer que opere en su propio espacio de pila. De esa manera, generalmente tendría la ventaja de parar cuando mi recursión está fuera de control, pero aún podría hacer uso de la recursión extensiva cuando quisiera.
Voy a resumir los argumentos en las respuestas hasta ahora porque no encuentro una respuesta que cubra este tema lo suficientemente buena.
Investigación de pila estática
Motivación
No todos lo necesitan.
- La mayoría de los algoritmos no utilizan recursiones profundas o muchos subprocesos, por lo que no mucha gente necesita pilas dinámicas.
- La pila dinámica haría un desbordamiento de la pila de recursión infinita, que es un error fácil de realizar, más difícil de diagnosticar. (El desbordamiento de la memoria, aunque es tan mortal como un desbordamiento de la pila en el proceso actual, también es peligroso para otros procesos)
- Cada algoritmo recursivo se puede emular con un iterativo similar.
Dificultades de implementación
La implementación dinámica de la pila no es tan directa como parece.
- El cambio de tamaño de pila solo no es suficiente a menos que tenga espacio de direcciones ilimitado. A veces también tendrás que reubicar la pila.
- La reubicación de la pila requerirá actualizaciones para todos los punteros a las estructuras de datos asignadas en la pila. Si bien es sencillo (al menos en los idiomas administrados) para los datos en la memoria, no hay una manera fácil de hacer lo mismo para los datos en los registros de la CPU del hilo.
- Algunas CPU (en particular los microcontroladores) implementan la pila directamente en el hardware, separado de la memoria principal.
Implementaciones existentes
Hay algunos idiomas o bibliotecas de tiempo de ejecución que ya tienen la función de pila dinámica o algo similar.
- Algunas bibliotecas de tiempo de ejecución (¿qué?) No comprometen previamente todo el bloque de memoria asignado para la pila. Esto puede aliviar el problema, especialmente para sistemas de 64 bits, pero no eliminarlo por completo.
- nos habló de PARLANSE , un lenguaje específicamente diseñado para tratar estructuras de datos complejas con alto grado de paralelismo. Utiliza pequeños "granos" de trabajo asignados en el montón en lugar de pila.
- fuzzy lolipop nos dijo que "¡Erlang correctamente escrito no tiene s !"
- Se dice que el lenguaje de programación Google Go tiene una pila dinámica. (Un enlace estaría bien)
Me gustaría ver más ejemplos aquí.
Espero no haberme olvidado ninguna información importante sobre este tema. Hacer esto una wiki de la comunidad para que cualquiera pueda agregar nueva información.