java - ventajas - ¿Cómo predecir la máxima profundidad de llamada de un método recursivo?

recursividad estructura de datos

Question

A los efectos de estimar la profundidad de llamada máxima que un método recursivo puede alcanzar con una cantidad determinada de memoria, ¿cuál es la fórmula (aproximada) para calcular la memoria utilizada antes de que ocurra un error de desbordamiento de pila?

Editar:

Muchos respondieron con "depende", lo cual es razonable, así que eliminemos algunas de las variables mediante un ejemplo trivial pero concreto:

public static int sumOneToN(int n) {
return n < 2 ? 1 : n + sumOneToN(n - 1);
}

Es fácil mostrar que ejecutar esto en mi Eclipse IDE explota por n justo por debajo de 1000 (sorprendentemente bajo para mí). ¿Se podría haber estimado este límite de profundidad de llamada sin ejecutarlo?

Editar: No puedo evitar pensar que Eclipse tiene una profundidad de llamada máxima fija de 1000, porque llegué a 998 , pero hay uno para el principal, y uno para la llamada inicial al método, lo que hace 1000 en total. Esto es "demasiado redondo" un número en mi humilde opinión como una coincidencia. Investigaré más a fondo. Solo tengo Dux sobre el parámetro -Xss vm; es el tamaño máximo de la pila, por lo que el corredor Eclipse debe tener -Xss1000 establecido en algún lugar

Answer 1

Addig a NPEs responde:

La profundidad máxima de la pila parece ser flexible . El siguiente programa de prueba imprime números muy diferentes:

public class StackDepthTest {
static int i = 0;
public static void main(String[] args) throws Throwable {
for(int i=0; i<10; ++i){
testInstance();
}
}
public static void testInstance() {
StackDepthTest sdt = new StackDepthTest();
try {
i=0;
sdt.instanceCall();
} catch(StackOverflowError e){}
System.out.println(i);
}
public void instanceCall(){
++i;
instanceCall();
}
}

El resultado es:

10825
10825
59538
59538
59538
59538
59538
59538
59538
59538

He usado el valor por defecto de este JRE:

java version "1.7.0_09"
OpenJDK Runtime Environment (IcedTea7 2.3.3) (7u9-2.3.3-0ubuntu1~12.04.1)
OpenJDK 64-Bit Server VM (build 23.2-b09, mixed mode)

Entonces la conclusión es: si tu pus tiene suficiente (es decir, más de dos veces), tienes una segunda oportunidad ;-)

Answer 2

Esto es claramente JVM, y posiblemente también específico de la arquitectura.

He medido lo siguiente:

 static int i = 0;
public static void rec0() {
i++;
rec0();
}
public static void main(String[] args) {
...
try {
i = 0; rec0();
} catch (Error e) {
System.out.println(i);
}
...
}

utilizando

Java(TM) SE Runtime Environment (build 1.7.0_09-b05)
Java HotSpot(TM) 64-Bit Server VM (build 23.5-b02, mixed mode)

corriendo en x86.

Con una pila Java de 20MB ( -Xss20m ), el costo amortizado fluctuó alrededor de 16-17 bytes por llamada. Lo más bajo que he visto fue 16.15 bytes / cuadro. Por lo tanto, concluyo que el costo es de 16 bytes y el resto es otra sobrecarga (fija).

Una función que toma una sola int tiene básicamente el mismo costo, 16 bytes / cuadro.

Curiosamente, una función que requiere diez ints requiere 32 bytes / cuadro. No estoy seguro de por qué el costo es tan bajo.

Los resultados anteriores se aplican después de que el código ha sido compilado JIT. Antes de la compilación, el costo por cuadro es mucho, mucho mayor. Todavía no he descubierto una manera de estimarlo de manera confiable. Sin embargo, esto significa que no tiene ninguna esperanza de predecir con fiabilidad la profundidad máxima de recursión hasta que pueda predecir con fiabilidad si la función recursiva se ha compilado JIT.

Todo esto fue probado con un tamaño de pila ulimit de 128K y 8MB. Los resultados fueron los mismos en ambos casos.

Answer 3

La respuesta es, todo depende.

En primer lugar, se puede cambiar el tamaño de la pila de Java.

En segundo lugar, el tamaño del marco de pila de un método dado puede variar según diferentes variables. Puede consultar la sección Tamaño de marco de la pila de llamadas de Call stack - Wikipedia para obtener más información.

Answer 4

Puede tomar el camino empírico y experimentar con su código y la configuración -Xss . Consulte aquí para obtener más información: opción de JVM -Xss: ¿qué hace exactamente?

Answer 5

Solo una respuesta parcial: de JVM Spec 7, 2.5.2 , los cuadros de pila se pueden asignar en el montón, y el tamaño de pila puede ser dinámico. No podría decirlo con certeza, pero parece que debería ser posible tener el tamaño de tu pila limitado solo por tu tamaño de pila:

Debido a que la pila de la máquina virtual Java nunca se manipula directamente, excepto para los marcos push y pop, los marcos se pueden asignar de manera aleatoria.

y

Esta especificación permite que las pilas de máquinas virtuales de Java tengan un tamaño fijo o se expandan y contraigan dinámicamente según lo requiera el cálculo. Si las pilas de la máquina virtual Java son de un tamaño fijo, el tamaño de cada pila de máquina virtual Java se puede elegir de forma independiente cuando se crea esa pila.

Una implementación de máquina virtual Java puede proporcionar al programador o al usuario control sobre el tamaño inicial de las pilas de máquinas virtuales Java, así como, en el caso de la expansión dinámica o la contratación de pilas de máquinas virtuales Java, controlar los tamaños máximos y mínimos.

Entonces, dependerá de la implementación de JVM.

Answer 6

depende de la arquitectura del sistema (direcciones de 32 o 64 bits), la cantidad de variables locales y los parámetros del método. Si es tail-recursive no hay gastos generales, si el compilador lo optimiza en un bucle.

Ya ves, no hay una respuesta simple.