java - ¿Por qué el conteo de llamadas de un método recursivo que causa un StackOverflowError varía entre las ejecuciones del programa?

recursion stack-overflow

Question

Esta pregunta ya tiene una respuesta aquí:

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

Una clase simple para demostraciones:

public class Main {
private static int counter = 0;
public static void main(String[] args) {
try {
f();
} catch (StackOverflowError e) {
System.out.println(counter);
}
}
private static void f() {
counter++;
f();
}
}

Ejecuté el programa anterior 5 veces, los resultados son:

22025
22117
15234
21993
21430

¿Por qué los resultados son diferentes cada vez?

Intenté establecer el tamaño máximo de la pila (por ejemplo, -Xss256k ). Los resultados fueron un poco más consistentes, pero nuevamente no iguales cada vez.

Versión de Java:

java version "1.8.0_72"
Java(TM) SE Runtime Environment (build 1.8.0_72-b15)
Java HotSpot(TM) 64-Bit Server VM (build 25.72-b15, mixed mode)

EDITAR

Cuando JIT está desactivado ( -Djava.compiler=NONE ) siempre obtengo el mismo número ( 11907 ).

Esto tiene sentido ya que las optimizaciones de JIT probablemente estén afectando el tamaño de los marcos de pila y el trabajo realizado por JIT definitivamente tiene que variar entre las ejecuciones.

Sin embargo, creo que sería beneficioso si esta teoría se confirma con referencias a alguna documentación sobre el tema y / o ejemplos concretos del trabajo realizado por JIT en este ejemplo específico que conduce a cambios en el tamaño del cuadro.

Answer 1

El funcionamiento exacto de la pila Java no está documentado, pero depende totalmente de la memoria asignada a esa secuencia.

Simplemente intente usar el constructor Thread con stacksize y vea si se vuelve constante. No lo he intentado, así que por favor comparta los resultados.

Answer 2

En primer lugar, lo siguiente no ha sido investigado. No he "buceado" profundamente el código fuente OpenJDK para validar ninguno de los siguientes, y no tengo acceso a ningún conocimiento interno.

Intenté validar tus resultados ejecutando tu prueba en mi máquina:

$ java -version
openjdk version "1.8.0_71"
OpenJDK Runtime Environment (build 1.8.0_71-b15)
OpenJDK 64-Bit Server VM (build 25.71-b15, mixed mode)

Obtengo el "conteo" variando en un rango de ~ 250. (No tanto como lo que está viendo)

Primero algunos antecedentes. Una pila de subprocesos en una implementación típica de Java es una región contigua de la memoria que se asigna antes de que se inicie el subproceso, y que nunca crece ni se mueve. Un desbordamiento de pila ocurre cuando la JVM intenta crear un marco de pila para hacer una llamada a un método, y el cuadro va más allá de los límites de la región de memoria. La prueba se puede hacer probando el SP explícitamente, pero mi entendimiento es que normalmente se implementa usando un truco inteligente con la configuración de la página de memoria.

Cuando se asigna una región de pila, la JVM realiza un syscall para indicar al sistema operativo que marque una página de "zona roja" al final de la zona de pila de solo lectura o no accesible. Cuando un hilo realiza una llamada que desborda la pila, accede a la memoria en la "zona roja" que desencadena una falla de memoria. El sistema operativo le dice a la JVM a través de una "señal", y el manejador de señal de la JVM lo mapea a un Error que se "lanza" en la pila del hilo.

Así que aquí hay un par de posibles explicaciones para la variabilidad:

• La granularidad de la protección de memoria basada en hardware es el límite de página. Entonces, si la pila de subprocesos se ha asignado usando malloc , el inicio de la región no se alineará con la página. Por lo tanto, la distancia desde el inicio del marco de la pila a la primera palabra de la "zona roja" (que> está <alineado con la página) va a ser variable.

• La pila "principal" es potencialmente especial, porque esa región se puede usar mientras la JVM se inicia. Eso podría llevar a que se dejaran algunas "cosas" en la pila antes de que se llamara main . (Esto no es convincente ... y no estoy convencido)

Habiendo dicho esto, la variabilidad "grande" que está viendo es desconcertante. Los tamaños de página son demasiado pequeños para explicar una diferencia de ~ 7000 en los conteos.

ACTUALIZAR

Cuando JIT está desactivado (-Djava.compiler = NONE) siempre obtengo el mismo número (11907).

Interesante. Entre otras cosas, eso podría hacer que la verificación del límite de pila se haga de forma diferente.

Esto tiene sentido ya que las optimizaciones de JIT probablemente estén afectando el tamaño de los marcos de pila y el trabajo realizado por JIT definitivamente tiene que variar entre las ejecuciones.

Plausible. El tamaño del marco de pila podría ser diferente después de que el método f() haya sido compilado JIT. Suponiendo que f() se compiló JIT en algún momento, tu pila tendrá una mezcla de fotogramas "antiguos" y "nuevos". Si la compilación JIT se produjo en diferentes puntos, entonces la relación será diferente ... y por lo tanto, el count será diferente cuando llegue al límite.

Sin embargo, creo que sería beneficioso si esta teoría se confirma con referencias a alguna documentación sobre el tema y / o ejemplos concretos del trabajo realizado por JIT en este ejemplo específico que conduce a cambios en el tamaño del cuadro.

Pocas posibilidades de eso, me temo ... a menos que esté preparado para PAGAR a alguien para que haga una investigación de unos días para usted.

1) No existe tal documentación de referencia (pública), AFAIK. Al menos, nunca he podido encontrar una fuente definitiva para este tipo de cosas ... además de bucear en profundidad el código fuente.

2) Al mirar el código compilado de JIT no se dice nada sobre cómo el intérprete de códigos de bytes manejó las cosas antes de que el código se compilara JIT. Por lo tanto, no podrá ver si el tamaño del marco ha cambiado .

Answer 3

La varianza observada es causada por la compilación JIT de fondo .

Así es como se ve el proceso:

1. El método f() inicia la ejecución en el intérprete.
2. Después de una serie de invocaciones (alrededor de 250), el método está programado para su compilación.
3. El hilo del compilador funciona en paralelo al hilo de la aplicación. Mientras tanto, el método continúa la ejecución en el intérprete.
4. Tan pronto como el hilo compilador finaliza la compilación, se reemplaza el punto de entrada del método, por lo que la siguiente llamada a f() invocará la versión compilada del método.

Básicamente, hay una carrera entre hilo de aplicación y el hilo del compilador JIT. El intérprete puede realizar un número diferente de llamadas antes de que la versión compilada del método esté lista. Al final hay una mezcla de marcos interpretados y compilados.

No es de extrañar que el diseño del marco compilado difiera del interpretado. Los marcos compilados suelen ser más pequeños; no necesitan almacenar todo el contexto de ejecución en la pila (referencia de método, referencia de grupo constante, datos de perfilador, todos los argumentos, variables de expresión, etc.)

Además, hay aún más posibilidades de carrera con la compilación por niveles (por defecto desde JDK 8). Puede haber una combinación de 3 tipos de marcos: intérprete, C1 y C2 (ver a continuación).

Vamos a tener algunos experimentos divertidos para apoyar la teoría.

1. Modo interpretado puro Sin compilación de JIT.
   Sin carreras => resultados estables.

   $ java -Xint Main
   11895
   11895
   11895

2. Deshabilita la compilación de fondo . JIT está activado, pero está sincronizado con el hilo de la aplicación.
   No hay carreras de nuevo, pero el número de llamadas ahora es mayor debido a los marcos compilados.

   $ java -XX:-BackgroundCompilation Main
   23462
   23462
   23462

3. Compila todo con C1 antes de la ejecución. A diferencia del caso anterior, no habrá marcos interpretados en la pila, por lo que el número será un poco más alto.

   $ java -Xcomp -XX:TieredStopAtLevel=1 Main
   23720
   23720
   23720

4. Ahora compila todo con C2 antes de la ejecución. Esto producirá el código más optimizado con el marco más pequeño. La cantidad de llamadas será la más alta.

   $ java -Xcomp -XX:-TieredCompilation Main
   59300
   59300
   59300

   Dado que el tamaño de pila predeterminado es 1M, esto debería significar que el marco ahora tiene solo 16 bytes de longitud. ¿Lo es?

   $ java -Xcomp -XX:-TieredCompilation -XX:CompileCommand=print,Main.f Main
   0x00000000025ab460: mov %eax,-0x6000(%rsp) ; check
   0x00000000025ab467: push %rbp ; frame link
   0x00000000025ab468: sub $0x10,%rsp
   0x00000000025ab46c: movabs $0xd7726ef0,%r10 ; r10 = Main.class
   0x00000000025ab476: addl $0x2,0x68(%r10) ; Main.counter += 2
   0x00000000025ab47b: callq 0x00000000023c6620 ; invokestatic f()
   0x00000000025ab480: add $0x10,%rsp
   0x00000000025ab484: pop %rbp ; pop frame
   0x00000000025ab485: test %eax,-0x23bb48b(%rip) ; safepoint poll
   0x00000000025ab48b: retq

   De hecho, el cuadro aquí es de 32 bytes, pero JIT ha subrayado un nivel de recursión.

5. Finalmente, veamos el rastro de la pila mixta. Para obtenerlo, bloquearemos JVM en Error (opción disponible en versiones de depuración).

   $ java -XX:AbortVMOnException=java.lang.Error Main

   El volcado de bloqueo hs_err_pid.log contiene el rastro de pila detallado donde podemos encontrar marcos interpretados en la parte inferior, cuadros C1 en el medio y, por último, cuadros C2 en la parte superior.

   Java frames: (J=compiled Java code, j=interpreted, Vv=VM code)
   J 164 C2 Main.f()V (12 bytes) @ 0x00007f21251a5958 [0x00007f21251a5900+0x0000000000000058]
   J 164 C2 Main.f()V (12 bytes) @ 0x00007f21251a5920 [0x00007f21251a5900+0x0000000000000020]
   // ... repeated 19787 times ...
   J 164 C2 Main.f()V (12 bytes) @ 0x00007f21251a5920 [0x00007f21251a5900+0x0000000000000020]
   J 163 C1 Main.f()V (12 bytes) @ 0x00007f211dca50ec [0x00007f211dca5040+0x00000000000000ac]
   J 163 C1 Main.f()V (12 bytes) @ 0x00007f211dca50ec [0x00007f211dca5040+0x00000000000000ac]
   // ... repeated 1866 times ...
   J 163 C1 Main.f()V (12 bytes) @ 0x00007f211dca50ec [0x00007f211dca5040+0x00000000000000ac]
   j Main.f()V+8
   j Main.f()V+8
   // ... repeated 1839 times ...
   j Main.f()V+8
   j Main.main([Ljava/lang/String;)V+0
   v ~StubRoutines::call_stub