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

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", son distintas de cero (nota: ayb 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 fragmento de 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:

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

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

Vemos el mismo efecto de predicción de rama como se esperaba, curiosamente el gráfico está algo volteado 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 conocer la predicción de ramas. Pero no son lógicamente equivalentes a las otras expresiones, porque solo un OR b debe ser distinto de 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 solo está iterando 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 de cerca 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 números enteros.

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

CPU: Intel Core i7-3610QM a 2,3 GHz

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

Estoy ignorando el problema de que su evaluación comparativa podría tener fallas y estoy tomando el resultado al pie de la letra.

¿Es el compilador o es a nivel de hardware?

Eso último, creo:

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

se compilará en 2 cargas de memoria y dos ramas condicionales

  if (a * b != 0)

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

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 eficaz. A medida que aumenta la proporción ... la predicción de ramas se vuelve menos efectiva.

La razón por la que las ramas condicionales son más lentas es que provocan que la canalización de ejecución de instrucciones se detenga. La predicción de rama consiste en evitar la pérdida al predecir en qué dirección se dirigirá la rama y elegir especulativamente la siguiente instrucción basada en 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á muy simplificada. Para obtener una explicación más precisa, debe consultar la literatura proporcionada por el fabricante de la CPU para codificadores de lenguaje ensamblador y redactores de compiladores. La página de Wikipedia sobre Predictores de ramas es una buena información)

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

ACTUALIZAR

Tus gráficos tienden a confirmar lo que dije.

• También hay un efecto de "predicción de rama" en el a * b != 0caso de rama condicional , y esto se refleja 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 en 1,0 y 2) el punto de encuentro tendrá aproximadamente el mismo valor de Y que para X = 0,0.

ACTUALIZACIÓN 2

No entiendo por qué las curvas son diferentes para a + b != 0los a | b != 0casos y. 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 evaluaciones comparativas podrían ser diferentes en otros sistemas).

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

Creo que su punto de referencia tiene algunas fallas y podría no ser útil para inferir sobre programas reales. Estos son mis pensamientos:

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

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

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

• La VM optimizará la expresión durante las primeras ejecuciones del fractionciclo 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 máquina virtual pueda eliminar algunas de las comprobaciones de los límites de la matriz aquí, hay otras cuatro ramas en la expresión solo debido a las comprobaciones de los límites, y eso es un factor de complicación cuando se trata de averiguar qué está sucediendo en un nivel bajo. Es posible obtener resultados diferentes si se divide la matriz bidimensional en dos matrices planas, cambiando nums[0][i]y nums[1][i]que nums0[i]y nums1[i].

• Los predictores de ramas de la CPU detectan patrones cortos en los datos o ejecuciones de todas las ramas que se toman o no. Sus datos de referencia generados aleatoriamente son el ¿Por qué procesar una matriz ordenada es más rápido que procesar una matriz no ordenada? . Si los datos del mundo real tienen un patrón predecible, o tienen series largas de valores todos cero y todos distintos de cero, las ramas podrían costar mucho menos.

• El código particular que se ejecuta después de que se cumple la condición puede afectar el rendimiento de la evaluación de la condición en sí, porque afecta cosas como si el bucle se puede desenrollar o no, qué registros de CPU están disponibles y si alguno de los numsvalores recuperados necesita reutilizarse después de evaluar la condición. Incrementar simplemente 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()en la mayoría de los sistemas no es más preciso que +/- 10 ms. System.nanoTime()suele ser más precisa.

Hay muchas incertidumbres y siempre es difícil decir algo definitivo con este tipo de microoptimizaciones porque un truco que es más rápido en una máquina virtual o CPU puede ser más lento en otra. Si está ejecutando 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 , ¡hágalo en lugar de intentar adivinar qué hace!

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

Dado que las dos ramas y la predicción de la rama asociada son los posibles culpables, es posible que podamos reducir la rama 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

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 del cortocircuito, si el primer booleano es falso, el segundo no debe evaluarse. Tiene que realizar una rama extra para evitar evaluar nums[1][i]si nums[0][i]era falso. Ahora, es posible que no le importe que nums[1][i]se evalúe, 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 booleano innecesariamente no tendrá efectos secundarios negativos.

Cuando hacemos 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 apariciones de la iteración comenzando desde 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 tanto, el tiempo necesario es menor. Pero creo que la segunda condición podría brindarle una solución más precisa.

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

Dicho eso. No veo cómo a*b != 0puede ser más rápido que (a|b) != 0. Generalmente, la multiplicación de enteros es más cara 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 .