tutorial paneles example create java performance processing-efficiency microbenchmark branch-prediction

paneles - En Java, ¿puede y ser más rápido que &&?



table swing java (7)

En este código:

if (value >= x && value <= y) {

cuando el value >= x value <= y son tan verdaderos como falsos sin un patrón en particular, ¿sería más rápido usar el operador & que usar && ?

Específicamente, estoy pensando en cómo && evalúa perezosamente la expresión del lado derecho (es decir, solo si el LHS es verdadero), lo que implica un condicional, mientras que en Java & en este contexto garantiza una evaluación estricta de ambas sub-expresiones (booleanas) . El resultado del valor es el mismo en ambos sentidos.

Pero mientras que un operador >= o <= utilizará una instrucción de comparación simple, el && debe involucrar una rama, y esa rama es susceptible al fallo de predicción de rama , según esta Pregunta muy famosa: ¿Por qué es más rápido procesar una matriz ordenada que una matriz sin clasificar?

Por lo tanto, forzar que la expresión no tenga componentes perezosos seguramente será más determinista y no será vulnerable al fracaso de la predicción. ¿Correcto?

Notas:

  • obviamente, la respuesta a mi pregunta sería No si el código se ve así: if(value >= x && verySlowFunction()) . Me estoy centrando en expresiones "suficientemente simples" de RHS.
  • hay una rama condicional allí de todos modos (la declaración if ). No puedo demostrarme a mí mismo que eso es irrelevante, y que las formulaciones alternativas podrían ser mejores ejemplos, como boolean b = value >= x && value <= y;
  • Todo esto cae en el mundo de las horrendas micro optimizaciones. Sí, lo sé :-) ... interesante sin embargo?

Actualización Solo para explicar por qué estoy interesado: he estado mirando los sistemas sobre los que Martin Thompson ha estado escribiendo en su blog Mechanical Sympathy , después de que vino y habló sobre Aeron. Uno de los mensajes clave es que nuestro hardware tiene todas estas cosas mágicas, y nosotros los desarrolladores de software trágicamente no lo aprovechamos. No se preocupe, no voy a ir s / && / / & / en todo mi código :-) ... pero hay una serie de preguntas en este sitio sobre cómo mejorar la predicción de sucursales eliminando sucursales, y ocurrió para mí, los operadores booleanos condicionales están en el centro de las condiciones de prueba.

Por supuesto, @StephenC hace el punto fantástico de que doblar su código en formas extrañas puede hacer que sea menos fácil para los JIT detectar optimizaciones comunes, si no ahora, en el futuro. Y que la Pregunta muy famosa mencionada anteriormente es especial porque empuja la complejidad de la predicción mucho más allá de la optimización práctica.

Soy bastante consciente de que en la mayoría (o casi todas ) de las situaciones, && es la mejor manera más clara, más simple, más rápida, ¡aunque estoy muy agradecido con las personas que han publicado respuestas que demuestran esto! Estoy realmente interesado en ver si realmente hay algún caso en la experiencia de alguien donde la respuesta a "¿Puede & sea ​​más rápido?" podría ser sí ...

Actualización 2 : (Abordar el consejo de que la pregunta es demasiado amplia. No quiero hacer cambios importantes a esta pregunta porque podría comprometer algunas de las respuestas a continuación, ¡que son de calidad excepcional!) Quizás se llame un ejemplo en la naturaleza para; esto es de la clase Guava LongMath ( muchas gracias a @maaartinus por encontrar esto):

public static boolean isPowerOfTwo(long x) { return x > 0 & (x & (x - 1)) == 0; }

¿Ves eso primero? Y si lessThanBranchFree(...) el enlace, el siguiente método se llama lessThanBranchFree(...) , lo que sugiere que estamos en territorio de evitación de ramas, y la guayaba es muy utilizada: cada ciclo guardado hace que los niveles del mar bajen visiblemente. Entonces, planteemos la pregunta de esta manera: ¿ es este uso de & (donde && sería más normal) una optimización real?

La forma en que esto me fue explicado es que && devolverá falso si la primera verificación de una serie es falsa, mientras que & verifica todos los elementos de una serie independientemente de cuántos sean falsos. ES DECIR

if (x> 0 && x <= 10 && x

Correrá más rápido que

si (x> 0 y x <= 10 y x

Si x es mayor que 10, porque los símbolos de enclavamiento únicos continuarán verificando el resto de las condiciones, mientras que los signos de enclavamiento dobles se romperán después de la primera condición no verdadera.

Lo que buscas es algo como esto:

x <= value & value <= y value - x >= 0 & y - value >= 0 ((value - x) | (y - value)) >= 0 // integer bit-or

Interesante, a uno casi le gustaría mirar el código de bytes. Pero difícil de decir. Desearía que esta fuera una pregunta C.

Tenía curiosidad por la respuesta también, así que escribí la siguiente prueba (simple) para esto:

private static final int max = 80000; private static final int size = 100000; private static final int x = 1500; private static final int y = 15000; private Random random; @Before public void setUp() { this.random = new Random(); } @After public void tearDown() { random = null; } @Test public void testSingleOperand() { int counter = 0; int[] numbers = new int[size]; for (int j = 0; j < size; j++) { numbers[j] = random.nextInt(max); } long start = System.nanoTime(); //start measuring after an array has been filled for (int i = 0; i < numbers.length; i++) { if (numbers[i] >= x & numbers[i] <= y) { counter++; } } long end = System.nanoTime(); System.out.println("Duration of single operand: " + (end - start)); } @Test public void testDoubleOperand() { int counter = 0; int[] numbers = new int[size]; for (int j = 0; j < size; j++) { numbers[j] = random.nextInt(max); } long start = System.nanoTime(); //start measuring after an array has been filled for (int i = 0; i < numbers.length; i++) { if (numbers[i] >= x & numbers[i] <= y) { counter++; } } long end = System.nanoTime(); System.out.println("Duration of double operand: " + (end - start)); }

El resultado final es que la comparación con && siempre gana en términos de velocidad, siendo aproximadamente 1.5 / 2 milisegundos más rápido que &.

EDITAR: Como señaló @SvetlinZarev, también estaba midiendo el tiempo que le tomó a Random obtener un número entero. Lo cambió para usar una matriz precargada de números aleatorios, lo que hizo que la duración de la prueba de un solo operando fluctuara enormemente; Las diferencias entre varias carreras fueron de hasta 6-7ms.

El uso de & o & todavía requiere que se evalúe una condición, por lo que es poco probable que ahorre tiempo de procesamiento; incluso podría agregarse considerando que está evaluando ambas expresiones cuando solo necesita evaluar una.

Usar & over && para ahorrar un nanosegundo si eso en algunas situaciones muy raras no tiene sentido, ya ha perdido más tiempo contemplando la diferencia de lo que habría ahorrado usando & over && .

Editar

Me dio curiosidad y decidí hacer algunos puntos de referencia.

Hice esta clase:

public class Main { static int x = 22, y = 48; public static void main(String[] args) { runWithOneAnd(30); runWithTwoAnds(30); } static void runWithOneAnd(int value){ if(value >= x & value <= y){ } } static void runWithTwoAnds(int value){ if(value >= x && value <= y){ } } }

y ejecuté algunas pruebas de perfil con NetBeans. No utilicé ninguna declaración impresa para ahorrar tiempo de procesamiento, solo sé que ambas se evalúan como true .

Primer examen:

Segunda prueba:

Tercera prueba:

Como puede ver en las pruebas de creación de perfiles, usar solo una & realidad tarda 2-3 veces más en ejecutarse en comparación con el uso de dos && . Esto parece sorprendente, ya que esperaba un mejor rendimiento de solo uno.

No estoy 100% seguro de por qué. En ambos casos, ambas expresiones tienen que ser evaluadas porque ambas son verdaderas. Sospecho que la JVM hace una optimización especial detrás de escena para acelerarlo.

Moraleja de la historia: la convención es buena y la optimización prematura es mala.

Editar 2

Rehice el código de referencia teniendo en cuenta los comentarios de @ SvetlinZarev y algunas otras mejoras. Aquí está el código de referencia modificado:

public class Main { static int x = 22, y = 48; public static void main(String[] args) { oneAndBothTrue(); oneAndOneTrue(); oneAndBothFalse(); twoAndsBothTrue(); twoAndsOneTrue(); twoAndsBothFalse(); System.out.println(b); } static void oneAndBothTrue() { int value = 30; for (int i = 0; i < 2000; i++) { if (value >= x & value <= y) { doSomething(); } } } static void oneAndOneTrue() { int value = 60; for (int i = 0; i < 4000; i++) { if (value >= x & value <= y) { doSomething(); } } } static void oneAndBothFalse() { int value = 100; for (int i = 0; i < 4000; i++) { if (value >= x & value <= y) { doSomething(); } } } static void twoAndsBothTrue() { int value = 30; for (int i = 0; i < 4000; i++) { if (value >= x & value <= y) { doSomething(); } } } static void twoAndsOneTrue() { int value = 60; for (int i = 0; i < 4000; i++) { if (value >= x & value <= y) { doSomething(); } } } static void twoAndsBothFalse() { int value = 100; for (int i = 0; i < 4000; i++) { if (value >= x & value <= y) { doSomething(); } } } //I wanted to avoid print statements here as they can //affect the benchmark results. static StringBuilder b = new StringBuilder(); static int times = 0; static void doSomething(){ times++; b.append("I have run ").append(times).append(" times /n"); } }

Y aquí están las pruebas de rendimiento:

Prueba 1:

Prueba 2:

Prueba 3:

Esto tiene en cuenta diferentes valores y diferentes condiciones también.

Usar uno & requiere más tiempo para ejecutarse cuando ambas condiciones son verdaderas, aproximadamente 60% o 2 milisegundos más de tiempo. Cuando una o ambas condiciones son falsas, una se & ejecuta más rápido, pero solo se ejecuta entre 0,30 y 0,50 milisegundos más rápido. Por & lo tanto , funcionará más rápido que && en la mayoría de las circunstancias, pero la diferencia de rendimiento sigue siendo insignificante.

Ok, entonces quieres saber cómo se comporta en el nivel inferior ... ¡Veamos el código de bytes entonces!

EDITAR: se agregó el código de ensamblaje generado para AMD64, al final. Echa un vistazo a algunas notas interesantes.
EDIT 2 (re: "Actualización 2" de OP): también se agregó código asm para el método isPowerOfTwo de Guava .

Fuente de Java

Escribí estos dos métodos rápidos:

public boolean AndSC(int x, int value, int y) { return value >= x && value <= y; } public boolean AndNonSC(int x, int value, int y) { return value >= x & value <= y; }

Como puede ver, son exactamente iguales, salvo por el tipo de operador AND.

Código de bytes de Java

Y este es el bytecode generado:

public AndSC(III)Z L0 LINENUMBER 8 L0 ILOAD 2 ILOAD 1 IF_ICMPLT L1 ILOAD 2 ILOAD 3 IF_ICMPGT L1 L2 LINENUMBER 9 L2 ICONST_1 IRETURN L1 LINENUMBER 11 L1 FRAME SAME ICONST_0 IRETURN L3 LOCALVARIABLE this Ltest/lsoto/AndTest; L0 L3 0 LOCALVARIABLE x I L0 L3 1 LOCALVARIABLE value I L0 L3 2 LOCALVARIABLE y I L0 L3 3 MAXSTACK = 2 MAXLOCALS = 4 // access flags 0x1 public AndNonSC(III)Z L0 LINENUMBER 15 L0 ILOAD 2 ILOAD 1 IF_ICMPLT L1 ICONST_1 GOTO L2 L1 FRAME SAME ICONST_0 L2 FRAME SAME1 I ILOAD 2 ILOAD 3 IF_ICMPGT L3 ICONST_1 GOTO L4 L3 FRAME SAME1 I ICONST_0 L4 FRAME FULL [test/lsoto/AndTest I I I] [I I] IAND IFEQ L5 L6 LINENUMBER 16 L6 ICONST_1 IRETURN L5 LINENUMBER 18 L5 FRAME SAME ICONST_0 IRETURN L7 LOCALVARIABLE this Ltest/lsoto/AndTest; L0 L7 0 LOCALVARIABLE x I L0 L7 1 LOCALVARIABLE value I L0 L7 2 LOCALVARIABLE y I L0 L7 3 MAXSTACK = 3 MAXLOCALS = 4

El AndSC ( && ) genera dos saltos condicionales, como se esperaba:

  1. Carga el value x en la pila, y salta a L1 si el value es menor. De lo contrario, sigue corriendo las siguientes líneas.
  2. Carga value y en la pila, y también salta a L1, si el value es mayor. De lo contrario, sigue corriendo las siguientes líneas.
  3. Lo que resulta ser un return true en caso de que ninguno de los dos saltos se haya realizado.
  4. Y luego tenemos las líneas marcadas como L1 que son un return false .

¡El AndNonSC ( & ), sin embargo, genera tres saltos condicionales!

  1. Carga el value x en la pila y salta a L1 si el value es menor. Debido a que ahora necesita guardar el resultado para compararlo con la otra parte del AND, por lo que debe ejecutar "guardar true " o "guardar false ", no puede hacer ambas cosas con la misma instrucción.
  2. Carga value e y en la pila y salta a L1 si el value es mayor. Una vez más, necesita guardar true o false y eso son dos líneas diferentes dependiendo del resultado de la comparación.
  3. Ahora que ambas comparaciones están hechas, el código realmente ejecuta la operación AND, y si ambas son verdaderas, salta (por tercera vez) para devolver verdadero; o bien continúa la ejecución en la siguiente línea para devolver falso.

(Preliminar) Conclusión

Aunque no tengo mucha experiencia con el código de bytes de Java y es posible que haya pasado por alto algo, me parece que & realidad funcionará peor que && en todos los casos: genera más instrucciones para ejecutar, incluidos más saltos condicionales para predecir y posiblemente fallar en

Una reescritura del código para reemplazar las comparaciones con operaciones aritméticas, como alguien más propuso, podría ser una forma de hacer una mejor opción, pero a costa de hacer que el código sea mucho menos claro.
En mi humilde opinión, no vale la pena el 99% de los escenarios (puede valer la pena para los bucles de 1% que necesitan ser extremadamente optimizados).

EDITAR: montaje AMD64

Como se señaló en los comentarios, el mismo código de bytes de Java puede conducir a un código de máquina diferente en diferentes sistemas, por lo que si bien el código de bytes de Java podría darnos una pista sobre qué versión AND funciona mejor, obtener el ASM real generado por el compilador es la única forma para descubrirlo realmente
Imprimí las instrucciones AMD64 ASM para ambos métodos; a continuación están las líneas relevantes (puntos de entrada eliminados, etc.).

NOTA: todos los métodos compilados con java 1.8.0_91 a menos que se indique lo contrario.

Método AndSC con opciones predeterminadas

# {method} {0x0000000016da0810} ''AndSC'' ''(III)Z'' in ''AndTest'' ... 0x0000000002923e3e: cmp %r8d,%r9d 0x0000000002923e41: movabs $0x16da0a08,%rax ; {metadata(method data for {method} {0x0000000016da0810} ''AndSC'' ''(III)Z'' in ''AndTest'')} 0x0000000002923e4b: movabs $0x108,%rsi 0x0000000002923e55: jl 0x0000000002923e65 0x0000000002923e5b: movabs $0x118,%rsi 0x0000000002923e65: mov (%rax,%rsi,1),%rbx 0x0000000002923e69: lea 0x1(%rbx),%rbx 0x0000000002923e6d: mov %rbx,(%rax,%rsi,1) 0x0000000002923e71: jl 0x0000000002923eb0 ;*if_icmplt ; - AndTest::AndSC@2 (line 22) 0x0000000002923e77: cmp %edi,%r9d 0x0000000002923e7a: movabs $0x16da0a08,%rax ; {metadata(method data for {method} {0x0000000016da0810} ''AndSC'' ''(III)Z'' in ''AndTest'')} 0x0000000002923e84: movabs $0x128,%rsi 0x0000000002923e8e: jg 0x0000000002923e9e 0x0000000002923e94: movabs $0x138,%rsi 0x0000000002923e9e: mov (%rax,%rsi,1),%rdi 0x0000000002923ea2: lea 0x1(%rdi),%rdi 0x0000000002923ea6: mov %rdi,(%rax,%rsi,1) 0x0000000002923eaa: jle 0x0000000002923ec1 ;*if_icmpgt ; - AndTest::AndSC@7 (line 22) 0x0000000002923eb0: mov $0x0,%eax 0x0000000002923eb5: add $0x30,%rsp 0x0000000002923eb9: pop %rbp 0x0000000002923eba: test %eax,-0x1c73dc0(%rip) # 0x0000000000cb0100 ; {poll_return} 0x0000000002923ec0: retq ;*ireturn ; - AndTest::AndSC@13 (line 25) 0x0000000002923ec1: mov $0x1,%eax 0x0000000002923ec6: add $0x30,%rsp 0x0000000002923eca: pop %rbp 0x0000000002923ecb: test %eax,-0x1c73dd1(%rip) # 0x0000000000cb0100 ; {poll_return} 0x0000000002923ed1: retq

Método AndSC con -XX:PrintAssemblyOptions=intel opción -XX:PrintAssemblyOptions=intel

# {method} {0x00000000170a0810} ''AndSC'' ''(III)Z'' in ''AndTest'' ... 0x0000000002c26e2c: cmp r9d,r8d 0x0000000002c26e2f: jl 0x0000000002c26e36 ;*if_icmplt 0x0000000002c26e31: cmp r9d,edi 0x0000000002c26e34: jle 0x0000000002c26e44 ;*iconst_0 0x0000000002c26e36: xor eax,eax ;*synchronization entry 0x0000000002c26e38: add rsp,0x10 0x0000000002c26e3c: pop rbp 0x0000000002c26e3d: test DWORD PTR [rip+0xffffffffffce91bd],eax # 0x0000000002910000 0x0000000002c26e43: ret 0x0000000002c26e44: mov eax,0x1 0x0000000002c26e49: jmp 0x0000000002c26e38

Método AndNonSC con opciones predeterminadas

# {method} {0x0000000016da0908} ''AndNonSC'' ''(III)Z'' in ''AndTest'' ... 0x0000000002923a78: cmp %r8d,%r9d 0x0000000002923a7b: mov $0x0,%eax 0x0000000002923a80: jl 0x0000000002923a8b 0x0000000002923a86: mov $0x1,%eax 0x0000000002923a8b: cmp %edi,%r9d 0x0000000002923a8e: mov $0x0,%esi 0x0000000002923a93: jg 0x0000000002923a9e 0x0000000002923a99: mov $0x1,%esi 0x0000000002923a9e: and %rsi,%rax 0x0000000002923aa1: cmp $0x0,%eax 0x0000000002923aa4: je 0x0000000002923abb ;*ifeq ; - AndTest::AndNonSC@21 (line 29) 0x0000000002923aaa: mov $0x1,%eax 0x0000000002923aaf: add $0x30,%rsp 0x0000000002923ab3: pop %rbp 0x0000000002923ab4: test %eax,-0x1c739ba(%rip) # 0x0000000000cb0100 ; {poll_return} 0x0000000002923aba: retq ;*ireturn ; - AndTest::AndNonSC@25 (line 30) 0x0000000002923abb: mov $0x0,%eax 0x0000000002923ac0: add $0x30,%rsp 0x0000000002923ac4: pop %rbp 0x0000000002923ac5: test %eax,-0x1c739cb(%rip) # 0x0000000000cb0100 ; {poll_return} 0x0000000002923acb: retq

Método AndNonSC con -XX:PrintAssemblyOptions=intel opción -XX:PrintAssemblyOptions=intel

# {method} {0x00000000170a0908} ''AndNonSC'' ''(III)Z'' in ''AndTest'' ... 0x0000000002c270b5: cmp r9d,r8d 0x0000000002c270b8: jl 0x0000000002c270df ;*if_icmplt 0x0000000002c270ba: mov r8d,0x1 ;*iload_2 0x0000000002c270c0: cmp r9d,edi 0x0000000002c270c3: cmovg r11d,r10d 0x0000000002c270c7: and r8d,r11d 0x0000000002c270ca: test r8d,r8d 0x0000000002c270cd: setne al 0x0000000002c270d0: movzx eax,al 0x0000000002c270d3: add rsp,0x10 0x0000000002c270d7: pop rbp 0x0000000002c270d8: test DWORD PTR [rip+0xffffffffffce8f22],eax # 0x0000000002910000 0x0000000002c270de: ret 0x0000000002c270df: xor r8d,r8d 0x0000000002c270e2: jmp 0x0000000002c270c0

  • En primer lugar, el código ASM generado difiere dependiendo de si elegimos la sintaxis AT&T predeterminada o la sintaxis Intel.
  • Con la sintaxis de AT&T:
    • El código ASM es en realidad más largo para el método AndSC , con cada bytecode IF_ICMP* traducido a dos instrucciones de salto de ensamblaje, para un total de 4 saltos condicionales.
    • Mientras tanto, para el método AndNonSC , el compilador genera un código más directo, donde cada bytecode IF_ICMP* se traduce a una sola instrucción de salto de ensamblaje, manteniendo el recuento original de 3 saltos condicionales.
  • Con la sintaxis de Intel:
    • El código ASM para AndSC es más corto, con solo 2 saltos condicionales (sin contar el jmp no condicional al final). En realidad son solo dos CMP, dos JL / E y un XOR / MOV, dependiendo del resultado.
    • ¡El código ASM para AndNonSC ahora es más largo que el de AndSC ! Sin embargo , tiene solo 1 salto condicional (para la primera comparación), utilizando los registros para comparar directamente el primer resultado con el segundo, sin más saltos.

Conclusión después del análisis de código ASM

  • A nivel de lenguaje de máquina AMD64, el operador & parece generar código ASM con menos saltos condicionales, lo que podría ser mejor para altas tasas de falla de predicción ( value aleatorios value por ejemplo).
  • Por otro lado, el operador && parece generar código ASM con menos instrucciones (con la -XX:PrintAssemblyOptions=intel todos modos), lo que podría ser mejor para bucles realmente largos con entradas amigables para la predicción, donde la menor cantidad de ciclos de CPU para cada comparación puede hacer la diferencia a largo plazo.

Como dije en algunos de los comentarios, esto va a variar mucho entre sistemas, por lo que si hablamos de optimización de predicción de sucursales, la única respuesta real sería: depende de su implementación de JVM, su compilador, su CPU y sus datos de entrada

Anexo: Método isPowerOfTwo de Guava

Aquí, los desarrolladores de Guava han ideado una forma ordenada de calcular si un número dado es una potencia de 2:

public static boolean isPowerOfTwo(long x) { return x > 0 & (x & (x - 1)) == 0; }

Citando OP:

¿Es este uso de & (donde && sería más normal) una optimización real?

Para saber si es así, agregué dos métodos similares a mi clase de prueba:

public boolean isPowerOfTwoAND(long x) { return x > 0 & (x & (x - 1)) == 0; } public boolean isPowerOfTwoANDAND(long x) { return x > 0 && (x & (x - 1)) == 0; }

Código ASM de Intel para la versión de Guava

# {method} {0x0000000017580af0} ''isPowerOfTwoAND'' ''(J)Z'' in ''AndTest'' # this: rdx:rdx = ''AndTest'' # parm0: r8:r8 = long ... 0x0000000003103bbe: movabs rax,0x0 0x0000000003103bc8: cmp rax,r8 0x0000000003103bcb: movabs rax,0x175811f0 ; {metadata(method data for {method} {0x0000000017580af0} ''isPowerOfTwoAND'' ''(J)Z'' in ''AndTest'')} 0x0000000003103bd5: movabs rsi,0x108 0x0000000003103bdf: jge 0x0000000003103bef 0x0000000003103be5: movabs rsi,0x118 0x0000000003103bef: mov rdi,QWORD PTR [rax+rsi*1] 0x0000000003103bf3: lea rdi,[rdi+0x1] 0x0000000003103bf7: mov QWORD PTR [rax+rsi*1],rdi 0x0000000003103bfb: jge 0x0000000003103c1b ;*lcmp 0x0000000003103c01: movabs rax,0x175811f0 ; {metadata(method data for {method} {0x0000000017580af0} ''isPowerOfTwoAND'' ''(J)Z'' in ''AndTest'')} 0x0000000003103c0b: inc DWORD PTR [rax+0x128] 0x0000000003103c11: mov eax,0x1 0x0000000003103c16: jmp 0x0000000003103c20 ;*goto 0x0000000003103c1b: mov eax,0x0 ;*lload_1 0x0000000003103c20: mov rsi,r8 0x0000000003103c23: movabs r10,0x1 0x0000000003103c2d: sub rsi,r10 0x0000000003103c30: and rsi,r8 0x0000000003103c33: movabs rdi,0x0 0x0000000003103c3d: cmp rsi,rdi 0x0000000003103c40: movabs rsi,0x175811f0 ; {metadata(method data for {method} {0x0000000017580af0} ''isPowerOfTwoAND'' ''(J)Z'' in ''AndTest'')} 0x0000000003103c4a: movabs rdi,0x140 0x0000000003103c54: jne 0x0000000003103c64 0x0000000003103c5a: movabs rdi,0x150 0x0000000003103c64: mov rbx,QWORD PTR [rsi+rdi*1] 0x0000000003103c68: lea rbx,[rbx+0x1] 0x0000000003103c6c: mov QWORD PTR [rsi+rdi*1],rbx 0x0000000003103c70: jne 0x0000000003103c90 ;*lcmp 0x0000000003103c76: movabs rsi,0x175811f0 ; {metadata(method data for {method} {0x0000000017580af0} ''isPowerOfTwoAND'' ''(J)Z'' in ''AndTest'')} 0x0000000003103c80: inc DWORD PTR [rsi+0x160] 0x0000000003103c86: mov esi,0x1 0x0000000003103c8b: jmp 0x0000000003103c95 ;*goto 0x0000000003103c90: mov esi,0x0 ;*iand 0x0000000003103c95: and rsi,rax 0x0000000003103c98: and esi,0x1 0x0000000003103c9b: mov rax,rsi 0x0000000003103c9e: add rsp,0x50 0x0000000003103ca2: pop rbp 0x0000000003103ca3: test DWORD PTR [rip+0xfffffffffe44c457],eax # 0x0000000001550100 0x0000000003103ca9: ret

Código ASM de Intel para la versión &&

# {method} {0x0000000017580bd0} ''isPowerOfTwoANDAND'' ''(J)Z'' in ''AndTest'' # this: rdx:rdx = ''AndTest'' # parm0: r8:r8 = long ... 0x0000000003103438: movabs rax,0x0 0x0000000003103442: cmp rax,r8 0x0000000003103445: jge 0x0000000003103471 ;*lcmp 0x000000000310344b: mov rax,r8 0x000000000310344e: movabs r10,0x1 0x0000000003103458: sub rax,r10 0x000000000310345b: and rax,r8 0x000000000310345e: movabs rsi,0x0 0x0000000003103468: cmp rax,rsi 0x000000000310346b: je 0x000000000310347b ;*lcmp 0x0000000003103471: mov eax,0x0 0x0000000003103476: jmp 0x0000000003103480 ;*ireturn 0x000000000310347b: mov eax,0x1 ;*goto 0x0000000003103480: and eax,0x1 0x0000000003103483: add rsp,0x40 0x0000000003103487: pop rbp 0x0000000003103488: test DWORD PTR [rip+0xfffffffffe44cc72],eax # 0x0000000001550100 0x000000000310348e: ret

En este ejemplo específico, el compilador JIT genera mucho menos código de ensamblaje para la versión && que para la versión & de Guava (y, después de los resultados de ayer, honestamente me sorprendió esto).
En comparación con Guava''s, la versión && traduce en un 25% menos de bytecode para que JIT compile, un 50% menos de instrucciones de ensamblaje y solo dos saltos condicionales (la versión & tiene cuatro de ellos).

Entonces, todo apunta a que el método & la guayaba es menos eficiente que la versión && más "natural".

... ¿O es eso?

Como se señaló anteriormente, estoy ejecutando los ejemplos anteriores con Java 8:

C:/....>java -version java version "1.8.0_91" Java(TM) SE Runtime Environment (build 1.8.0_91-b14) Java HotSpot(TM) 64-Bit Server VM (build 25.91-b14, mixed mode)

Pero, ¿y si me cambio a Java 7 ?

C:/....>c:/jdk1.7.0_79/bin/java -version java version "1.7.0_79" Java(TM) SE Runtime Environment (build 1.7.0_79-b15) Java HotSpot(TM) 64-Bit Server VM (build 24.79-b02, mixed mode) C:/....>c:/jdk1.7.0_79/bin/java -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,*AndTest.isPowerOfTwoAND -XX:PrintAssemblyOptions=intel AndTestMain ..... 0x0000000002512bac: xor r10d,r10d 0x0000000002512baf: mov r11d,0x1 0x0000000002512bb5: test r8,r8 0x0000000002512bb8: jle 0x0000000002512bde ;*ifle 0x0000000002512bba: mov eax,0x1 ;*lload_1 0x0000000002512bbf: mov r9,r8 0x0000000002512bc2: dec r9 0x0000000002512bc5: and r9,r8 0x0000000002512bc8: test r9,r9 0x0000000002512bcb: cmovne r11d,r10d 0x0000000002512bcf: and eax,r11d ;*iand 0x0000000002512bd2: add rsp,0x10 0x0000000002512bd6: pop rbp 0x0000000002512bd7: test DWORD PTR [rip+0xffffffffffc0d423],eax # 0x0000000002120000 0x0000000002512bdd: ret 0x0000000002512bde: xor eax,eax 0x0000000002512be0: jmp 0x0000000002512bbf .....

¡Sorpresa! El código de ensamblaje generado para el método & por el compilador JIT en Java 7, ahora solo tiene un salto condicional, ¡y es mucho más corto! Mientras que el método && (tendrás que confiar en mí en este caso, ¡no quiero saturar el final!) Sigue siendo el mismo, con sus dos saltos condicionales y un par de instrucciones menos, como máximo.
¡Parece que los ingenieros de Guava sabían lo que estaban haciendo, después de todo! (si intentaban optimizar el tiempo de ejecución de Java 7, eso es ;-)

Volviendo a la última pregunta de OP:

¿Es este uso de & (donde && sería más normal) una optimización real?

Y en mi humilde opinión, la respuesta es la misma , incluso para este (¡muy!) Escenario específico: depende de su implementación de JVM, su compilador, su CPU y sus datos de entrada .

Para ese tipo de preguntas, debe ejecutar un microbenchmark. JMH para esta prueba.

Los puntos de referencia se implementan como

// boolean logical AND bh.consume(value >= x & y <= value);

y

// conditional AND bh.consume(value >= x && y <= value);

y

// bitwise OR, as suggested by Joop Eggen bh.consume(((value - x) | (y - value)) >= 0)

Con valores de value, x and y según el nombre de referencia.

El resultado (cinco calentamientos y diez iteraciones de medición) para la evaluación comparativa de rendimiento es:

Benchmark Mode Cnt Score Error Units Benchmark.isBooleanANDBelowRange thrpt 10 386.086 ▒ 17.383 ops/us Benchmark.isBooleanANDInRange thrpt 10 387.240 ▒ 7.657 ops/us Benchmark.isBooleanANDOverRange thrpt 10 381.847 ▒ 15.295 ops/us Benchmark.isBitwiseORBelowRange thrpt 10 384.877 ▒ 11.766 ops/us Benchmark.isBitwiseORInRange thrpt 10 380.743 ▒ 15.042 ops/us Benchmark.isBitwiseOROverRange thrpt 10 383.524 ▒ 16.911 ops/us Benchmark.isConditionalANDBelowRange thrpt 10 385.190 ▒ 19.600 ops/us Benchmark.isConditionalANDInRange thrpt 10 384.094 ▒ 15.417 ops/us Benchmark.isConditionalANDOverRange thrpt 10 380.913 ▒ 5.537 ops/us

El resultado no es tan diferente para la evaluación en sí. Mientras no se vea ningún impacto en el rendimiento de ese fragmento de código, no intentaré optimizarlo. Dependiendo del lugar en el código, el compilador de puntos de acceso podría decidir hacer alguna optimización. Lo que probablemente no esté cubierto por los puntos de referencia anteriores.

algunas referencias:

AND lógico booleano : el valor del resultado es true si ambos valores de operando son true ; de lo contrario, el resultado es false
condicional AND - es como & , pero evalúa su operando de la derecha solo si el valor de su operando de la izquierda es true
OR bit a bit : el valor del resultado es el OR bit a bit inclusivo de los valores de operando

Voy a llegar a esto desde un ángulo diferente.

Considere estos dos fragmentos de código,

if (value >= x && value <= y) {

y

if (value >= x & value <= y) {

Si asumimos que el value , x , y tiene un tipo primitivo, esas dos declaraciones (parciales) darán el mismo resultado para todos los posibles valores de entrada. (Si están involucrados tipos de envoltura, entonces no son exactamente equivalentes debido a una prueba null implícita para y que podría fallar en la versión & y no en la versión && ).

Si el compilador JIT está haciendo un buen trabajo, su optimizador podrá deducir que esas dos declaraciones hacen lo mismo:

  • Si uno es previsiblemente más rápido que el otro, entonces debería poder usar la versión más rápida ... en el código compilado JIT .

  • De lo contrario, no importa qué versión se use en el nivel del código fuente.

  • Dado que el compilador JIT recopila estadísticas de ruta antes de compilar, potencialmente puede tener más información sobre las características de ejecución que el programador (!).

  • Si el compilador JIT de la generación actual (en cualquier plataforma dada) no se optimiza lo suficientemente bien como para manejar esto, la próxima generación podría hacerlo ... dependiendo de si la evidencia empírica indica que este es un patrón que vale la pena optimizar.

  • De hecho, si escribe su código Java de una manera que se optimice para esto, existe la posibilidad de que al elegir la versión más "oscura" del código, pueda inhibir la capacidad actual o futura del compilador JIT para optimizar.

En resumen, no creo que deba hacer este tipo de microoptimización a nivel de código fuente. Y si acepta este argumento 1 y lo sigue hasta su conclusión lógica, la pregunta de qué versión es más rápida es ... discutible 2 .

1 - No afirmo que esto esté cerca de ser una prueba.

2 - A menos que seas una de la pequeña comunidad de personas que realmente escriben compiladores Java JIT ...

La "Pregunta muy famosa" es interesante en dos aspectos:

  • Por un lado, ese es un ejemplo en el que el tipo de optimización necesaria para marcar la diferencia va más allá de la capacidad de un compilador JIT.

  • Por otro lado, no necesariamente sería lo correcto clasificar la matriz ... solo porque una matriz ordenada se puede procesar más rápido. El costo de ordenar la matriz podría ser (mucho) mayor que el ahorro.