java - ¿Por qué es "while(i++<n){}" significativamente más lento que "while(++ i<n){}"
performance compiler-optimization (5)
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 en 1 y luego la inserta en la pila del operando mientras que 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 e i++ (sin embargo, no exhaustivamente), pero no encontré ninguna respuesta que sea específica de Java y esté directamente relacionada con el caso en el que ++i o i++ participan en una comparación de valores.
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 verdadero defecto del benchmark se vuelve obvio cuando ejecuta esto con el indicador -server . 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 se ha optimizado completamente . 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} 'runPreIncrement' '()V' in 'PrePostIncrement'
# [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} 'runPostIncrement' '()V' in 'PrePostIncrement'
# [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é aparentemente no elimina la versión posterior al incremento. (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 bucle de Integer.MAX_VALUE a Integer.MAX_VALUE-1 , ambas 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 asignada a una instrucción cmp (¡chamuscada!), Pero no puedo dar una razón más profunda más allá de eso. El JIT funciona de manera misteriosa ...
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.
Sugiero que siempre (siempre que sea posible) utilice siempre ++c lugar de c++ ya que el primero nunca será más lento ya que, conceptualmente, una copia profunda de c debe 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.
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.
EDIT 2
Deberías mirar realmente aquí:
EDITAR Cuanto más lo pienso, me doy cuenta de que esta prueba es de alguna manera incorrecta, el bucle será optimizado seriamente por la JVM.
Creo que deberías descartar el @Param y dejar que n=2 .
De esta forma probarás el rendimiento del while . 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 evaluar y medir 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.