Pregunta ¿Por qué es "while (i ++

Aparentemente en mi computadora portátil con Windows 8 con HotSpot JDK 1.7.0_45 (con todas las opciones de compilador / máquina virtual configuradas de manera predeterminada), el ciclo siguiente

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

es al menos 2 órdenes de magnitud más rápido (~ 10 ms contra ~ 5000 ms) que:

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

Me dio cuenta de este problema al escribir un ciclo para evaluar otro problema de rendimiento irrelevante. Y la diferencia entre ++i < n y i++ < n fue lo suficientemente grande como para influir significativamente en el resultado.

Si miramos el bytecode, el cuerpo del bucle de la versión más rápida es:

iinc
iload
ldc
if_icmplt

Y para la versión más lenta:

iload
iinc
ldc
if_icmplt

Entonces para ++i < n, primero incrementa la variable local i por 1 y luego empújelo en la pila de operandos mientras i++ < n hace esos 2 pasos en orden inverso. Pero eso no parece explicar por qué el primero es mucho más rápido. ¿Hay alguna copia temporal involucrada en este último caso? ¿O es algo más allá del bytecode (implementación de máquina virtual, hardware, etc.) que debería ser responsable de la diferencia de rendimiento?

He leído alguna otra discusión con respecto a ++i y i++ (aunque no exhaustivamente), pero no encontró ninguna respuesta que sea específica de Java y esté directamente relacionada con el caso donde ++i o i++ está involucrado en una comparación de valores.


73
2017-08-15 07:24


origen


Respuestas:


Como otros han señalado, la prueba es defectuosa de muchas maneras.

No nos dijiste exactamente cómo Hiciste esta prueba. Sin embargo, traté de implementar una prueba "ingenua" (sin ofender) como esta:

class PrePostIncrement
{
    public static void main(String args[])
    {
        for (int j=0; j<3; j++)
        {
            for (int i=0; i<5; i++)
            {
                long before = System.nanoTime();
                runPreIncrement();
                long after = System.nanoTime();
                System.out.println("pre  : "+(after-before)/1e6);
            }
            for (int i=0; i<5; i++)
            {
                long before = System.nanoTime();
                runPostIncrement();
                long after = System.nanoTime();
                System.out.println("post : "+(after-before)/1e6);
            }
        }
    }

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

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

Al ejecutar esto con la configuración predeterminada, parece haber una pequeña diferencia. Pero el real defecto del punto de referencia se vuelve obvio cuando ejecuta esto con el -server bandera. Los resultados en mi caso son similares a

...
pre  : 6.96E-4
pre  : 6.96E-4
pre  : 0.001044
pre  : 3.48E-4
pre  : 3.48E-4
post : 1279.734543
post : 1295.989086
post : 1284.654267
post : 1282.349093
post : 1275.204583

Obviamente, la versión de preincremento ha sido completamente optimizado lejos. La razón es bastante simple: el resultado no se usa. No importa en absoluto si el ciclo se ejecuta o no, por lo que el JIT simplemente lo elimina.

Esto se confirma con un vistazo al desensamblaje del punto de acceso: La versión de preincremento da como resultado este código:

[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x0000000055060500} &apos;runPreIncrement&apos; &apos;()V&apos; in &apos;PrePostIncrement&apos;
  #           [sp+0x20]  (sp of caller)
  0x000000000286fd80: sub    $0x18,%rsp
  0x000000000286fd87: mov    %rbp,0x10(%rsp)    ;*synchronization entry
                                                ; - PrePostIncrement::runPreIncrement@-1 (line 28)

  0x000000000286fd8c: add    $0x10,%rsp
  0x000000000286fd90: pop    %rbp
  0x000000000286fd91: test   %eax,-0x243fd97(%rip)        # 0x0000000000430000
                                                ;   {poll_return}
  0x000000000286fd97: retq   
  0x000000000286fd98: hlt    
  0x000000000286fd99: hlt    
  0x000000000286fd9a: hlt    
  0x000000000286fd9b: hlt    
  0x000000000286fd9c: hlt    
  0x000000000286fd9d: hlt    
  0x000000000286fd9e: hlt    
  0x000000000286fd9f: hlt    

La versión de incremento posterior da como resultado este código:

[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x00000000550605b8} &apos;runPostIncrement&apos; &apos;()V&apos; in &apos;PrePostIncrement&apos;
  #           [sp+0x20]  (sp of caller)
  0x000000000286d0c0: sub    $0x18,%rsp
  0x000000000286d0c7: mov    %rbp,0x10(%rsp)    ;*synchronization entry
                                                ; - PrePostIncrement::runPostIncrement@-1 (line 35)

  0x000000000286d0cc: mov    $0x1,%r11d
  0x000000000286d0d2: jmp    0x000000000286d0e3
  0x000000000286d0d4: nopl   0x0(%rax,%rax,1)
  0x000000000286d0dc: data32 data32 xchg %ax,%ax
  0x000000000286d0e0: inc    %r11d              ; OopMap{off=35}
                                                ;*goto
                                                ; - PrePostIncrement::runPostIncrement@11 (line 36)

  0x000000000286d0e3: test   %eax,-0x243d0e9(%rip)        # 0x0000000000430000
                                                ;*goto
                                                ; - PrePostIncrement::runPostIncrement@11 (line 36)
                                                ;   {poll}
  0x000000000286d0e9: cmp    $0x7fffffff,%r11d
  0x000000000286d0f0: jl     0x000000000286d0e0  ;*if_icmpge
                                                ; - PrePostIncrement::runPostIncrement@8 (line 36)

  0x000000000286d0f2: add    $0x10,%rsp
  0x000000000286d0f6: pop    %rbp
  0x000000000286d0f7: test   %eax,-0x243d0fd(%rip)        # 0x0000000000430000
                                                ;   {poll_return}
  0x000000000286d0fd: retq   
  0x000000000286d0fe: hlt    
  0x000000000286d0ff: hlt    

No está del todo claro para mí por qué parece que sí no eliminar la versión de incremento posterior. (De hecho, considero hacer esto como una pregunta separada). Pero al menos, esto explica por qué puede ver las diferencias con un "orden de magnitud" ...


EDITAR: Curiosamente, cuando se cambia el límite superior del ciclo de Integer.MAX_VALUE a Integer.MAX_VALUE-1, entonces ambos las versiones se optimizan y requieren un tiempo "cero". De alguna manera este límite (que todavía aparece como 0x7fffffff en el conjunto) impide la optimización. Presumiblemente, esto tiene algo que ver con la comparación que se asigna a un (¡chamuscado!) cmp instrucción, pero no puedo dar una razón profunda más allá de eso. El JIT funciona de manera misteriosa ...


117
2017-08-15 08:40



La diferencia entre ++ i y i ++ es que ++ i efectivamente incrementa la variable y 'devuelve' ese nuevo valor. i ++, por otro lado, crea efectivamente una variable temporal para mantener el valor actual en i, luego incrementa la variable 'devolviendo' el valor de la variable de temperatura. Aquí es de donde viene la sobrecarga adicional.

// i++ evaluates to something like this
// Imagine though that somehow i was passed by reference
int temp = i;
i = i + 1;
return temp;

// ++i evaluates to
i = i + 1;
return i;

En su caso, parece que el incremento no será optimizado por la JVM porque está utilizando el resultado en una expresión. La JVM puede, por otro lado, optimizar un ciclo como este.

for( int i = 0; i < Integer.MAX_VALUE; i++ ) {}

Esto se debe a que el resultado de i ++ nunca se usa. En un ciclo como este, debería poder usar tanto ++ i como i ++ con el mismo rendimiento que si usara ++ i.


19
2017-08-15 07:27



EDIT 2

Deberías mirar realmente aquí:

http://hg.openjdk.java.net/code-tools/jmh/file/f90aef7f1d2c/jmh-samples/src/main/java/org/openjdk/jmh/samples/JMHSample_11_Loops.java

EDITAR Cuanto más lo pienso, me doy cuenta de que esta prueba es incorrecta de alguna manera, el bucle se verá seriamente optimizado por la JVM.

Creo que deberías dejar caer el @Param y deja n=2.

De esta manera probarás el rendimiento de while sí mismo. Los resultados que obtengo en este caso:

o.m.t.WhileTest.testFirst      avgt         5        0.787        0.086    ns/op
o.m.t.WhileTest.testSecond     avgt         5        0.782        0.087    ns/op

El casi no hay diferencia

La primera pregunta que debes hacerte es cómo pruebas y mides esto. Esto es micro-benchmarking y en Java esto es un arte, y casi siempre un usuario simple (como yo) obtendrá los resultados incorrectos. Debe confiar en una prueba de referencia y una muy buena herramienta para eso. Usé JMH para probar esto:

    @Measurement(iterations=5, time=1, timeUnit=TimeUnit.MILLISECONDS)
@Fork(1)
@Warmup(iterations=5, time=1, timeUnit=TimeUnit.SECONDS)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@State(Scope.Benchmark)
public class WhileTest {
    public static void main(String[] args) throws Exception {
        Options opt = new OptionsBuilder()
            .include(".*" + WhileTest.class.getSimpleName() + ".*")
            .threads(1)
            .build();

        new Runner(opt).run();
    }


    @Param({"100", "10000", "100000", "1000000"})
    private int n;

    /*
    @State(Scope.Benchmark)
    public static class HOLDER_I {
        int x;
    }
    */


    @Benchmark
    public int testFirst(){
        int i = 0;
        while (++i < n) {
        }
        return i;
    }

    @Benchmark
    public int testSecond(){
        int i = 0;
        while (i++ < n) {
        }
        return i;
    }
}

Una persona con más experiencia en JMH podría corregir estos resultados (¡realmente lo espero !, ya que todavía no soy tan versátil en JMH), pero los resultados muestran que la diferencia es bastante pequeña:

Benchmark                        (n)   Mode   Samples        Score  Score error    Units
o.m.t.WhileTest.testFirst        100   avgt         5        1.271        0.096    ns/op
o.m.t.WhileTest.testFirst      10000   avgt         5        1.319        0.125    ns/op
o.m.t.WhileTest.testFirst     100000   avgt         5        1.327        0.241    ns/op
o.m.t.WhileTest.testFirst    1000000   avgt         5        1.311        0.136    ns/op
o.m.t.WhileTest.testSecond       100   avgt         5        1.450        0.525    ns/op
o.m.t.WhileTest.testSecond     10000   avgt         5        1.563        0.479    ns/op
o.m.t.WhileTest.testSecond    100000   avgt         5        1.418        0.428    ns/op
o.m.t.WhileTest.testSecond   1000000   avgt         5        1.344        0.120    ns/op

El campo Puntaje es el que le interesa.


18
2017-08-15 07:45



probablemente esta prueba no sea suficiente para sacar conclusiones, pero diría que si este es el caso, la JVM puede optimizar esta expresión cambiando i ++ a ++ i ya que el valor almacenado de i ++ (valor pre) nunca se usa en este ciclo.


0
2017-08-18 07:47



Sugiero que debe (siempre que sea posible) siempre utilizar ++c más bien que c++ como lo hará el primero Nunca ser más lento ya que, conceptualmente, una copia profunda de c tiene que tomarse en este último caso para devolver el valor anterior.

De hecho, muchos optimizadores optimizarán una copia profunda innecesaria, pero no podrán hacerlo fácilmente si está utilizando el valor de la expresión. Y lo estás haciendo en tu caso.

Sin embargo, mucha gente está en desacuerdo: lo ven como una micro-optimización.


-3
2017-08-15 07:35