java - JIT no optimiza el bucle que implica Integer.MAX_VALUE

compiler-optimization jvm-hotspot

Question

Mientras escribía una respuesta a otra pregunta , noté un extraño caso de frontera para la optimización de JIT.

El siguiente programa no es un "Microbenchmark" y no tiene la intención de medir confiablemente un tiempo de ejecución (como se señala en las respuestas a la otra pregunta). Su único propósito es reproducir un MCVE para reproducir el problema:

class MissedLoopOptimization
{
    public static void main(String args[])
    {
        for (int j=0; j<3; j++)
        {
            for (int i=0; i<5; i++)
            {
                long before = System.nanoTime();
                runWithMaxValue();
                long after = System.nanoTime();
                System.out.println("With MAX_VALUE   : "+(after-before)/1e6);
            }
            for (int i=0; i<5; i++)
            {
                long before = System.nanoTime();
                runWithMaxValueMinusOne();
                long after = System.nanoTime();
                System.out.println("With MAX_VALUE-1 : "+(after-before)/1e6);
            }
        }
    }

    private static void runWithMaxValue()
    {
        final int n = Integer.MAX_VALUE;
        int i = 0;
        while (i++ < n) {}
    }

    private static void runWithMaxValueMinusOne()
    {
        final int n = Integer.MAX_VALUE-1;
        int i = 0;
        while (i++ < n) {}
    }
}

Básicamente ejecuta el mismo ciclo, while (i++ < n){} , donde el límite n una vez se establece en Integer.MAX_VALUE , y una vez en Integer.MAX_VALUE-1 .

Al ejecutar esto en Win7 / 64 con JDK 1.7.0_21 y

java -server MissedLoopOptimization

los resultados de tiempo son los siguientes:

...
With MAX_VALUE   : 1285.227081
With MAX_VALUE   : 1274.36311
With MAX_VALUE   : 1282.992203
With MAX_VALUE   : 1292.88246
With MAX_VALUE   : 1280.788994
With MAX_VALUE-1 : 6.96E-4
With MAX_VALUE-1 : 3.48E-4
With MAX_VALUE-1 : 0.0
With MAX_VALUE-1 : 0.0
With MAX_VALUE-1 : 3.48E-4

Obviamente, para el caso de MAX_VALUE-1 , el JIT hace lo que uno podría esperar: detecta que el bucle es inútil y lo elimina por completo. Sin embargo, no elimina el ciclo cuando se ejecuta hasta MAX_VALUE .

Esta observación se confirma con un vistazo a la salida del conjunto JIT cuando se comienza con

java -server -XX:+UnlockDiagnosticVMOptions -XX:+TraceClassLoading -XX:+LogCompilation -XX:+PrintAssembly MissedLoopOptimization

El registro contiene el siguiente ensamblaje para el método que se ejecuta hasta MAX_VALUE :

Decoding compiled method 0x000000000254fa10:
Code:
[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} 'runWithMaxValue' '()V' in 'MissedLoopOptimization'
  #           [sp+0x20]  (sp of caller)
  0x000000000254fb40: sub    $0x18,%rsp
  0x000000000254fb47: mov    %rbp,0x10(%rsp)    ;*synchronization entry
                                                ; - MissedLoopOptimization::runWithMaxValue@-1 (line 29)
  0x000000000254fb4c: mov    $0x1,%r11d
  0x000000000254fb52: jmp    0x000000000254fb63
  0x000000000254fb54: nopl   0x0(%rax,%rax,1)
  0x000000000254fb5c: data32 data32 xchg %ax,%ax
  0x000000000254fb60: inc    %r11d              ; OopMap{off=35}
                                                ;*goto
                                                ; - MissedLoopOptimization::runWithMaxValue@11 (line 30)
  0x000000000254fb63: test   %eax,-0x241fb69(%rip)        # 0x0000000000130000
                                                ;*goto
                                                ; - MissedLoopOptimization::runWithMaxValue@11 (line 30)
                                                ;   {poll}
  0x000000000254fb69: cmp    $0x7fffffff,%r11d
  0x000000000254fb70: jl     0x000000000254fb60  ;*if_icmpge
                                                ; - MissedLoopOptimization::runWithMaxValue@8 (line 30)
  0x000000000254fb72: add    $0x10,%rsp
  0x000000000254fb76: pop    %rbp
  0x000000000254fb77: test   %eax,-0x241fb7d(%rip)        # 0x0000000000130000
                                                ;   {poll_return}
  0x000000000254fb7d: retq   
  0x000000000254fb7e: hlt    
  0x000000000254fb7f: hlt    
[Exception Handler]
[Stub Code]
  0x000000000254fb80: jmpq   0x000000000254e820  ;   {no_reloc}
[Deopt Handler Code]
  0x000000000254fb85: callq  0x000000000254fb8a
  0x000000000254fb8a: subq   $0x5,(%rsp)
  0x000000000254fb8f: jmpq   0x0000000002528d00  ;   {runtime_call}
  0x000000000254fb94: hlt    
  0x000000000254fb95: hlt    
  0x000000000254fb96: hlt    
  0x000000000254fb97: hlt    

Uno puede ver claramente el ciclo, con la comparación de 0x7fffffff y el salto de regreso a inc . En contraste con eso, el ensamblaje para el caso donde se ejecuta hasta MAX_VALUE-1 :

Decoding compiled method 0x000000000254f650:
Code:
[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} 'runWithMaxValueMinusOne' '()V' in 'MissedLoopOptimization'
  #           [sp+0x20]  (sp of caller)
  0x000000000254f780: sub    $0x18,%rsp
  0x000000000254f787: mov    %rbp,0x10(%rsp)    ;*synchronization entry
                                                ; - MissedLoopOptimization::runWithMaxValueMinusOne@-1 (line 36)
  0x000000000254f78c: add    $0x10,%rsp
  0x000000000254f790: pop    %rbp
  0x000000000254f791: test   %eax,-0x241f797(%rip)        # 0x0000000000130000
                                                ;   {poll_return}
  0x000000000254f797: retq   
  0x000000000254f798: hlt    
  0x000000000254f799: hlt    
  0x000000000254f79a: hlt    
  0x000000000254f79b: hlt    
  0x000000000254f79c: hlt    
  0x000000000254f79d: hlt    
  0x000000000254f79e: hlt    
  0x000000000254f79f: hlt    
[Exception Handler]
[Stub Code]
  0x000000000254f7a0: jmpq   0x000000000254e820  ;   {no_reloc}
[Deopt Handler Code]
  0x000000000254f7a5: callq  0x000000000254f7aa
  0x000000000254f7aa: subq   $0x5,(%rsp)
  0x000000000254f7af: jmpq   0x0000000002528d00  ;   {runtime_call}
  0x000000000254f7b4: hlt    
  0x000000000254f7b5: hlt    
  0x000000000254f7b6: hlt    
  0x000000000254f7b7: hlt    

Entonces mi pregunta es: ¿qué tiene de especial el Integer.MAX_VALUE que impide que el JIT lo optimice de la misma manera que lo hace con Integer.MAX_VALUE-1 ? Supongo que tiene que ver con la instrucción cmp , que está destinada a la aritmética firmada , pero eso por sí solo no es una razón convincente. ¿Alguien puede explicar esto, y tal vez incluso dar un puntero al código de OpenJDK HotSpot donde se trata este caso?

(A un lado: espero que la respuesta también explique el comportamiento diferente entre i++ y ++i que se solicitó en la otra pregunta, suponiendo que el motivo de la optimización faltante (obviamente) en realidad es causado por el bucle Integer.MAX_VALUE límite)

Answer 1

No he desenterrado la Especificación del lenguaje Java, pero supongo que tiene que ver con esta diferencia:

• i++ < (Integer.MAX_VALUE - 1) nunca se desborda. Una vez que Integer.MAX_VALUE - 1 se incrementa a Integer.MAX_VALUE y luego el ciclo termina.

• i++ < Integer.MAX_VALUE contiene un desbordamiento de enteros. Una vez que Integer.MAX_VALUE , se incrementa en uno causando un desbordamiento y luego el ciclo termina.

Supongo que el compilador JIT es "reacio" a optimizar los bucles con tales condiciones de esquina - había una gran cantidad de errores de optimización de bucle en condiciones de desbordamiento de enteros, por lo que la renuencia es probablemente bastante justificada.

También puede haber algún requisito estricto que no permita optimizar los desbordamientos de enteros, aunque de alguna manera dudo que, dado que los desbordamientos de enteros no sean directamente detectables o manejados en Java.