¿Por qué es (a * b! = 0) más rápido que (a! = 0 && b! = 0) en Java?

412

Estoy escribiendo un código en Java donde, en algún momento, el flujo del programa está determinado por si dos variables int, "a" y "b", no son cero (nota: a y b nunca son negativas, y nunca dentro del rango de desbordamiento de enteros).

Puedo evaluarlo con

if (a != 0 && b != 0) { /* Some code */ }

O alternativamente

if (a*b != 0) { /* Some code */ }

Como espero que ese código se ejecute millones de veces por ejecución, me preguntaba cuál sería más rápido. Hice el experimento comparándolos en una enorme matriz generada aleatoriamente, y también tenía curiosidad por ver cómo la escasez de la matriz (fracción de datos = 0) afectaría los resultados:

long time;
final int len = 50000000;
int arbitrary = 0;
int[][] nums = new int[2][len];

for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) {
    for(int i = 0 ; i < 2 ; i++) {
        for(int j = 0 ; j < len ; j++) {
            double random = Math.random();

            if(random < fraction) nums[i][j] = 0;
            else nums[i][j] = (int) (random*15 + 1);
        }
    }

    time = System.currentTimeMillis();

    for(int i = 0 ; i < len ; i++) {
        if( /*insert nums[0][i]*nums[1][i]!=0 or nums[0][i]!=0 && nums[1][i]!=0*/ ) arbitrary++;
    }
    System.out.println(System.currentTimeMillis() - time);
}

Y los resultados muestran que si espera que "a" o "b" sea igual a 0 más del ~ 3% del tiempo, a*b != 0es más rápido que a!=0 && b!=0:

Gráfico gráfico de los resultados de a AND b no cero

Tengo curiosidad por saber por qué. ¿Alguien podría arrojar algo de luz? ¿Es el compilador o está en el nivel de hardware?

Editar: Por curiosidad ... ahora que aprendí sobre la predicción de rama, me preguntaba qué mostraría la comparación analógica para a OR b no es cero:

Gráfico de aob no distinto de cero

Vemos el mismo efecto de predicción de ramificación que el esperado, curiosamente, el gráfico se voltea un poco a lo largo del eje X.

Actualizar

1- Agregué !(a==0 || b==0)al análisis para ver qué pasa.

2- También incluí a != 0 || b != 0, (a+b) != 0y (a|b) != 0por curiosidad, después de aprender sobre la predicción de ramas. Pero no son lógicamente equivalentes a las otras expresiones, porque solo a OR b no debe ser cero para devolver verdadero, por lo que no deben compararse para la eficiencia del procesamiento.

3- También agregué el punto de referencia real que usé para el análisis, que es solo iterar una variable int arbitraria.

4- Algunas personas sugirieron incluir a != 0 & b != 0en lugar de a != 0 && b != 0, con la predicción de que se comportaría más estrechamente a*b != 0porque eliminaríamos el efecto de predicción de rama. No sabía que &podría usarse con variables booleanas, pensé que solo se usaba para operaciones binarias con enteros.

Nota: En el contexto en el que estaba considerando todo esto, el desbordamiento int no es un problema, pero definitivamente es una consideración importante en contextos generales.

CPU: Intel Core i7-3610QM @ 2.3GHz

Versión de Java: 1.8.0_45
Java (TM) SE Runtime Environment (compilación 1.8.0_45-b14)
Java HotSpot (TM) VM de servidor de 64 bits (compilación 25.45-b02, modo mixto)

Maljam
fuente
11
¿Qué hay de if (!(a == 0 || b == 0))? Los microbenchmarks son notoriamente poco confiables, es poco probable que sea realmente medible (~ 3% me parece un margen de error).
Elliott Frisch
99
O a != 0 & b != 0.
Louis Wasserman
16
La ramificación es lenta si la rama pronosticada es incorrecta. a*b!=0tiene una rama menos
Erwin Bolwidt
19
(1<<16) * (1<<16) == 0Sin embargo, ambos son diferentes de cero.
CodesInChaos
13
@Gene: Su optimización propuesta no es válida. Incluso ignorando el desbordamiento, a*bes cero si uno de ay bes cero; a|bes cero solo si ambos lo son.
hmakholm dejó a Mónica

Respuestas:

240

Estoy ignorando el problema de que su evaluación comparativa podría ser defectuosa y tomo el resultado al pie de la letra.

¿Es el compilador o está en el nivel de hardware?

Eso último, creo:

  if (a != 0 && b != 0)

compilará a 2 cargas de memoria y dos ramas condicionales

  if (a * b != 0)

compilará a 2 cargas de memoria, una rama condicional y una multiplicada.

Es probable que la multiplicación sea más rápida que la segunda rama condicional si la predicción de la rama a nivel de hardware no es efectiva. A medida que aumenta la proporción ... la predicción de rama se vuelve menos efectiva.

La razón por la que las ramas condicionales son más lentas es porque hacen que la tubería de ejecución de instrucciones se detenga. La predicción de rama se trata de evitar el bloqueo al predecir en qué dirección irá la rama y elegir especulativamente la siguiente instrucción en función de eso. Si la predicción falla, hay un retraso mientras se carga la instrucción para la otra dirección.

(Nota: la explicación anterior está demasiado simplificada. Para una explicación más precisa, debe consultar la literatura proporcionada por el fabricante de la CPU para codificadores de lenguaje ensamblador y escritores de compiladores. La página de Wikipedia sobre predictores de sucursal es un buen trasfondo).


Sin embargo, hay una cosa que debe tener cuidado con esta optimización. ¿Hay algún valor donde a * b != 0dará la respuesta incorrecta? Considere casos en los que calcular el producto da como resultado un desbordamiento de enteros.


ACTUALIZAR

Sus gráficos tienden a confirmar lo que dije.

  • También hay un efecto de "predicción de bifurcación" en el a * b != 0caso de bifurcación condicional , y esto aparece en los gráficos.

  • Si proyecta las curvas más allá de 0.9 en el eje X, parece que 1) se encontrarán aproximadamente a 1.0 y 2) el punto de encuentro tendrá aproximadamente el mismo valor Y que para X = 0.0.


ACTUALIZACIÓN 2

No entiendo por qué las curvas son diferentes para a + b != 0los a | b != 0casos. No podría ser algo inteligente en la lógica predictores de salto. O podría indicar algo más.

(Tenga en cuenta que este tipo de cosas puede ser específico para un número de modelo de chip en particular o incluso una versión. Los resultados de sus puntos de referencia podrían ser diferentes en otros sistemas).

Sin embargo, ambos tienen la ventaja de trabajar para todos los valores no negativos de ay b.

Stephen C
fuente
1
@DebosmitRay - 1) No debe haber SW. Los resultados intermedios se guardarán en un registro. 2) En el segundo caso, hay dos ramas disponibles: una para ejecutar "algún código" y la otra para saltar a la siguiente instrucción después de if.
Stephen C
1
@StephenC tienes razón en confundirte acerca de a + by a | b, porque las curvas son las mismas, creo que los colores están muy cerca. ¡Disculpas a las personas daltónicas!
Maljam
3
@ njzk2 desde la perspectiva de probabilidad, esos casos deben ser simétricos según el eje en un 50% (probabilidad de cero de a&by a|b). Ellos son, pero no perfectamente, ese es el rompecabezas.
Antonín Lejsek
3
@StephenC El motivo a*b != 0y el a+b != 0punto de referencia diferente es porque a+b != 0no es en absoluto equivalente y nunca debería haber sido comparado. Por ejemplo, con a = 1, b = 0, la primera expresión se evalúa como falsa pero la segunda se evalúa como verdadera. La multiplicación actúa como un operador y , mientras que la suma actúa como un operador o .
JS1
2
@ AntonínLejsek Creo que las probabilidades serían diferentes. Si tiene nceros, entonces la probabilidad de ambos ay de bser cero aumenta con n. En una ANDoperación, con mayor nprobabilidad de que uno de ellos sea ​​distinto de cero, aumenta y se cumple la condición. Esto es opuesto para una ORoperación (la probabilidad de que cualquiera de ellos sea ​​cero aumenta con n). Esto se basa en una perspectiva matemática. No estoy seguro si así es como funciona el hardware.
WYSIWYG
70

Creo que su punto de referencia tiene algunos defectos y podría no ser útil para inferir sobre programas reales. Aquí están mis pensamientos:

  • (a|b)!=0y (a+b)!=0compruebe si alguno de los valores no es cero, mientras que a != 0 && b != 0y (a*b)!=0compruebe si ambos son distintos de cero. Por lo tanto, no está comparando la sincronización de solo la aritmética: si la condición es verdadera con mayor frecuencia, causa más ejecuciones del ifcuerpo, lo que también lleva más tiempo.

  • (a+b)!=0 hará lo incorrecto para los valores positivos y negativos que suman cero, por lo que no puede usarlo en el caso general, incluso si funciona aquí.

  • Del mismo modo, (a*b)!=0hará lo incorrecto para los valores que se desbordan. (Ejemplo aleatorio: 196608 * 327680 es 0 porque el resultado verdadero resulta ser divisible por 2 32 , por lo que sus 32 bits bajos son 0, y esos bits son todo lo que obtienes si es una intoperación).

  • La VM optimizará la expresión durante las primeras ejecuciones del fractionbucle externo ( ), cuando fractiones 0, cuando las ramas casi nunca se toman. El optimizador puede hacer cosas diferentes si comienza fractionen 0.5.

  • A menos que la VM sea capaz de eliminar algunas de las verificaciones de límites de la matriz aquí, hay otras cuatro ramas en la expresión solo debido a las verificaciones de límites, y eso es un factor complicado cuando se trata de averiguar qué está sucediendo en un nivel bajo. Puede obtener resultados diferentes si divide la matriz bidimensional en dos matrices planas, cambiando nums[0][i]y nums[1][i]hacia nums0[i]y nums1[i].

  • Los predictores de rama de CPU detectan patrones cortos en los datos o ejecuciones de todas las ramas que se toman o no se toman. Sus datos de referencia generados aleatoriamente son el peor de los casos para un predictor de rama . Si los datos del mundo real tienen un patrón predecible, o si tienen largos periodos de valores de cero y de cero, las ramas podrían costar mucho menos.

  • El código particular que se ejecuta después de que se cumpla la condición puede afectar el desempeño de la evaluación de la condición en sí, porque afecta cosas como si el ciclo se puede desenrollar o no, qué registros de CPU están disponibles y si alguno de los numsvalores recuperados necesita ser reutilizado después de evaluar la condición. El simple incremento de un contador en el punto de referencia no es un marcador de posición perfecto para lo que haría el código real.

  • System.currentTimeMillis()es en la mayoría de los sistemas no más precisos que +/- 10 ms. System.nanoTime()Suele ser más preciso.

Hay muchas incertidumbres, y siempre es difícil decir algo definitivo con este tipo de micro optimizaciones porque un truco que es más rápido en una VM o CPU puede ser más lento en otra. Si ejecuta la JVM HotSpot de 32 bits, en lugar de la versión de 64 bits, tenga en cuenta que viene en dos versiones: la VM "Cliente" tiene optimizaciones diferentes (más débiles) en comparación con la VM "Servidor".

Si puede desmontar el código de máquina generado por la VM , ¡haga eso en lugar de tratar de adivinar lo que hace!

Boann
fuente
24

Las respuestas aquí son buenas, aunque tuve una idea que podría mejorar las cosas.

Dado que las dos ramas y la predicción de la rama asociada son el probable culpable, es posible que podamos reducir la ramificación a una sola rama sin cambiar la lógica en absoluto.

bool aNotZero = (nums[0][i] != 0);
bool bNotZero = (nums[1][i] != 0);
if (aNotZero && bNotZero) { /* Some code */ }

También puede funcionar para hacer

int a = nums[0][i];
int b = nums[1][i];
if (a != 0 && b != 0) { /* Some code */ }

La razón es que, según las reglas de cortocircuito, si el primer booleano es falso, el segundo no debe evaluarse. Tiene que realizar una rama adicional para evitar evaluar nums[1][i]si nums[0][i]era falsa. Ahora, puede que no le importe que lo nums[1][i]evalúen, pero el compilador no puede estar seguro de que no arrojará una referencia fuera de rango o nula cuando lo haga. Al reducir el bloque if a bools simples, el compilador puede ser lo suficientemente inteligente como para darse cuenta de que evaluar el segundo boolean innecesariamente no tendrá efectos secundarios negativos.

Pagefault
fuente
3
Upvoted aunque tengo la sensación de que esto no bastante responder a la pregunta.
Pierre Arlaud
3
Esa es una forma de introducir una rama sin cambiar la lógica de no ramificación (si la forma en que obtuvo ay btuvo efectos secundarios los habría mantenido). Todavía tienes, &&así que todavía tienes una rama.
Jon Hanna
11

Cuando tomamos la multiplicación, incluso si un número es 0, entonces el producto es 0. Mientras escribimos

    (a*b != 0)

Evalúa el resultado del producto, eliminando así las primeras ocurrencias de la iteración a partir de 0. Como resultado, las comparaciones son menores que cuando la condición es

   (a != 0 && b != 0)

Donde cada elemento se compara con 0 y se evalúa. Por lo tanto, el tiempo requerido es menor. Pero creo que la segunda condición podría darle una solución más precisa.

Sanket Gupte
fuente
44
En la segunda expresión, si aes cero, entonces bno necesita ser evaluado ya que la expresión completa ya es falsa. Entonces, cada elemento comparado no es cierto.
Kuba Wyrostek
9

Está utilizando datos de entrada aleatorios que hacen que las ramas sean impredecibles. En la práctica, las ramas suelen ser predecibles (~ 90%), por lo que en el código real es probable que el código ramificado sea más rápido.

Eso dicho No veo cómo a*b != 0puede ser más rápido que (a|b) != 0. En general, la multiplicación de enteros es más costosa que un OR bit a bit. Pero cosas como esta ocasionalmente se ponen raras. Consulte, por ejemplo, el ejemplo "Ejemplo 7: Complejidades de hardware" de la Galería de efectos de caché del procesador .

Apilado
fuente
2
&no es un "bit a bit OR" pero (en este caso) un "AND lógico" porque ambos operandos son booleanos y no es |;-)
siegi
1
@siegi TIL Java '&' es en realidad un AND lógico sin cortocircuitos.
StackedCrooked