¿Cuántas son demasiadas llamadas a funciones anidadas?

15

Citado de MSDN sobre StackOverflowException :

La excepción que se produce cuando la pila de ejecución se desborda porque contiene demasiadas llamadas a métodos anidados.

Too manyEs bastante vago aquí. ¿Cómo sé cuando demasiados son realmente demasiados? Miles de llamadas a funciones? Millones? Supongo que debe estar relacionado de alguna manera con la cantidad de memoria en la computadora, pero ¿es posible obtener un orden de magnitud más o menos preciso?

Me preocupa esto porque estoy desarrollando un proyecto que implica un uso intensivo de estructuras recursivas y llamadas a funciones recursivas. No quiero que la aplicación falle cuando empiezo a usarla para algo más que pequeñas pruebas.

.net exceptions recursion stackoverflow marco-fiset
fuente
44
Es relativamente fácil convertir una función recursiva en una función no recursiva. Simplemente pegue sus datos en un Stack<T>.
Brian
1
Qué tan grande es "demasiados" depende totalmente de usted definirlo. Para .NET, use editbin /stack:WHATEVER-NUMBER-YOU-LIKE yourexefile.exe.
SK-logic

Respuestas:

28

Me preocupa esto porque estoy desarrollando un proyecto que implica un uso intensivo de estructuras recursivas y llamadas a funciones recursivas. No quiero que la aplicación falle cuando empiezo a usarla para algo más que pequeñas pruebas.

A menos que su entorno de lenguaje admita la optimización de llamadas de cola (y su recursión es una llamada de cola), una regla básica es: se debe garantizar que la profundidad de recursión sea O (log n), es decir, usando algoritmos o estructuras de datos basadas en dividir y ... conquistar (como árboles, la mayoría de los alogoritmos de clasificación, etc.) está bien, pero nada lineal (como implementaciones recursivas de manejo de listas enlazadas) no lo está.

Michael Borgwardt
fuente
3
+1. Muy buena respuesta, he estado usando esta regla implícitamente pero no estaba al tanto.
Giorgio
En la actualidad, casi cualquier compilador de calidad de producción digno de la frase del adjetivo admitirá la optimización de la cola.
John R. Strohm
1
@ JohnR.Strohm Sin embargo, el OP ha etiquetado la pregunta .NET, por lo que AFAIK solo la fluctuación de fase de 64 bits optimiza las llamadas de cola en este momento.
Mark Hurd
1
Para que no haya confusión, los x86 y x64 siempre honran la "cola" de CIL. prefijo de instrucción Para resumir, en .NET land, F # completa la optimización de llamadas de cola, C # no, y el jitter x64 lo hace si es "fácil" (no se puede depender de él). Ver blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/…
Stephen Swensen
1
Es cierto, pero en algunos casos, como en un infame IIS que aloja ASP.NET, incluso una mera profundidad de recursión O (log n) puede fallar debido a su patético, injustificado y ridículo límite de profundidad de pila, que genera casi cualquier recursión (o incluso una larga cadena de llamadas anidadas no recursivas) imposible. La única forma de hacerlo es editar el binario iis en sí.
SK-logic
17

De manera predeterminada, el CLR asigna 1 MB a la pila para cada subproceso (consulte este artículo ). Por lo tanto, son muchas las llamadas que se necesitan para superar esta cantidad. Eso variará dependiendo de cuánto espacio en la pila esté usando cada llamada para cosas como parámetros y variables locales.

Incluso puede hacer que arroje un StackOverflowExceptioncon una sola llamada si está dispuesto a ser un poco ortodoxo:

private static unsafe void BlowUpTheStack()
{
    var x = stackalloc byte[1000000000];
    Console.WriteLine("Oh no, I've blown up the stack!");
}
Cole Campbell
fuente
Desafortunadamente, este incumplimiento razonable a menudo se viola (por ejemplo, en asp.net).
SK-logic
2

Como Cole Campbell observó el tamaño de la memoria y Michael Borgwardt observó la optimización de las llamadas de cola , no los cubriré.

Otra cosa a tener en cuenta es el CPS, que se puede utilizar para optimizar varias funciones entrelazadas, donde la optimización de llamadas de cola es para funciones individuales.

Puede aumentar el tamaño de la pila como lo hicimos aquí , y tenga en cuenta que el código de 64 bits se come la pila más rápido que el código de 32 bits.

Es de destacar que ejecutamos uno de los ejemplos en F # interactivo durante más de 40 horas sin volar la pila. Sí, fue una llamada de función que se ejecutó de forma continua hasta su finalización exitosa.

Además, si necesita hacer una cobertura de código para descubrir dónde ocurren los problemas y no tiene cobertura de código con VS, puede usar TestDriven.NET

Guy Coder
fuente