recursividad programacion estructura ejemplos datos con java recursion java-8 stack-overflow stack-size

java - programacion - recursividad estructura de datos



¿Por qué la profundidad máxima de recursión que puedo alcanzar no es determinista? (4)

Decidí probar algunos experimentos para ver qué podía descubrir sobre el tamaño de los cuadros de la pila y qué tan lejos estaba el código que se estaba ejecutando actualmente. Hay dos preguntas interesantes que podríamos investigar aquí:

  1. ¿Cuántos niveles de profundidad en la pila es el código actual?
  2. ¿Cuántos niveles de recursión puede alcanzar el método actual antes de que llegue a un StackOverflowError ?

Profundidad de pila del código actualmente en ejecución

Aquí está lo mejor que se me ocurrió para esto:

public static int levelsDeep() { try { throw new SomeKindOfException(); } catch (SomeKindOfException e) { return e.getStackTrace().length; } }

Esto parece un poco hacky. Genera y captura una excepción, y luego mira para ver cuál es la longitud del seguimiento de la pila.

Desafortunadamente, también parece tener una limitación fatal, que es que la longitud máxima del seguimiento de la pila devuelta es 1024. Cualquier cosa más allá de eso se elimina, por lo que el máximo que este método puede devolver es 1024.

Pregunta:

¿Hay una mejor manera de hacer esto que no sea tan hacky y no tenga esta limitación?

Para lo que vale, supongo que no: Throwable.getStackTraceDepth() es una llamada nativa, lo que sugiere (pero no prueba) que no se puede hacer en Java puro.

Determinar cuánto más profundidad de recursión nos queda

El número de niveles que podemos alcanzar estará determinado por (a) el tamaño del marco de la pila y (b) la cantidad de pila restante. No nos preocupemos por el tamaño del marco de la pila, y solo veamos cuántos niveles podemos alcanzar antes de llegar a un StackOverflowError .

Aquí está mi código para hacer esto:

public static int stackLeft() { try { return 1+stackLeft(); } catch (StackOverflowError e) { return 0; } }

Hace su trabajo admirablemente, incluso si es lineal en la cantidad de pila restante. Pero aquí está la parte muy, muy rara. En Java 7 de 64 bits (OpenJDK 1.7.0_65), los resultados son perfectamente consistentes: 9.923, en mi máquina (Ubuntu 14.04 de 64 bits). Pero Oracle 8 de Java (1.8.0_25) me da resultados no deterministas : obtengo una profundidad registrada de entre 18,500 y 20,700.

Ahora, ¿por qué demonios sería no determinista? Se supone que debe haber un tamaño de pila fijo, ¿no? Y todo el código me parece determinista.

Me preguntaba si era algo extraño con la captura de errores, así que intenté esto en su lugar:

public static long badSum(int n) { if (n==0) return 0; else return 1+badSum(n-1); }

Claramente, esto devolverá la entrada que se le dio o se desbordará.

Nuevamente, los resultados que obtengo no son deterministas en Java 8. Si llamo a badSum(14500) , me dará un StackOverflowError aproximadamente la mitad del tiempo y devolveré 14500 la otra mitad. pero en Java 7 OpenJDK, es consistente: badSum(9160) completa bien y se badSum(9161) .

Pregunta:

¿Por qué la profundidad de recursión máxima no es determinista en Java 8 de Oracle? ¿Y por qué es determinista en OpenJDK 7?

El comportamiento observado se ve afectado por el optimizador HotSpot, sin embargo, no es la única causa. Cuando ejecuto el siguiente código

public static void main(String[] argv) { System.out.println(System.getProperty("java.version")); System.out.println(countDepth()); System.out.println(countDepth()); System.out.println(countDepth()); System.out.println(countDepth()); System.out.println(countDepth()); System.out.println(countDepth()); System.out.println(countDepth()); } static int countDepth() { try { return 1+countDepth(); } catch(Error err) { return 0; } }

con JIT habilitado, obtengo resultados como:

> f:/Software/jdk1.8.0_40beta02/bin/java -Xss68k -server -cp build/classes X 1.8.0_40-ea 2097 4195 4195 4195 12587 12587 12587 > f:/Software/jdk1.8.0_40beta02/bin/java -Xss68k -server -cp build/classes X 1.8.0_40-ea 2095 4193 4193 4193 12579 12579 12579 > f:/Software/jdk1.8.0_40beta02/bin/java -Xss68k -server -cp build/classes X 1.8.0_40-ea 2087 4177 4177 12529 12529 12529 12529

Aquí, el efecto del JIT es claramente visible, obviamente el código optimizado necesita menos espacio en la pila, y se muestra que la compilación en niveles está habilitada (de hecho, usando -XX:-TieredCompilation muestra un solo salto si el programa se ejecuta lo suficiente).

En contraste, con JIT deshabilitado obtengo los siguientes resultados:

> f:/Software/jdk1.8.0_40beta02/bin/java -Xss68k -server -Xint -cp build/classes X 1.8.0_40-ea 2104 2104 2104 2104 2104 2104 2104 > f:/Software/jdk1.8.0_40beta02/bin/java -Xss68k -server -Xint -cp build/classes X 1.8.0_40-ea 2076 2076 2076 2076 2076 2076 2076 > f:/Software/jdk1.8.0_40beta02/bin/java -Xss68k -server -Xint -cp build/classes X 1.8.0_40-ea 2105 2105 2105 2105 2105 2105 2105

Los valores aún varían, pero no dentro del hilo de ejecución único y con una magnitud menor.

Por lo tanto, hay una diferencia (bastante pequeña) que se vuelve mucho mayor si el optimizador puede reducir el espacio de pila requerido por invocación de método, por ejemplo, debido a la alineación.

¿Qué puede causar tal diferencia? No sé cómo lo hace esta JVM, pero un escenario podría ser que la forma en que se aplica un límite de pila requiere una cierta alineación de la dirección final de la pila (por ejemplo, tamaños de página de memoria coincidentes) mientras que la asignación de memoria devuelve la memoria con una dirección de inicio que tiene una garantía de alineación más débil. Combine tal escenario con ASLR y siempre puede haber una diferencia, dentro del tamaño del requisito de alineación.

Está en desuso, pero puedes probar Thread.countStackFrames() como

public static int levelsDeep() { return Thread.currentThread().countStackFrames(); }

Según el Javadoc,

En desuso La definición de esta llamada depende de suspend() , que está en desuso. Además, los resultados de esta convocatoria nunca estuvieron bien definidos.

Cuenta el número de marcos de pila en este hilo. El hilo debe estar suspendido.

En cuanto a por qué observas un comportamiento no determinista, solo puedo suponer que es una combinación del JIT y el recolector de basura.

No necesitas atrapar la excepción, solo crea una como esta:

nuevo Throwable (). getStackTrace ()

O:

Thread.currentThread (). GetStackTrace ()

Todavía es hacky ya que el resultado es la implementación específica de JVM. Y JVM puede decidir recortar el resultado para un mejor rendimiento.