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

performance processing-efficiency

Question

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 gran 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 != 0 es 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 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:

Vemos el mismo efecto de la predicción de ramificación como se esperaba, 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é sucede.

2- También incluí a != 0 || b != 0 a != 0 || b != 0 , (a+b) != 0 y (a|b) != 0 por curiosidad, después de conocer la predicción de rama. 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 sugerían incluir a != 0 & b != 0 en lugar de a a != 0 && b != 0 , con la predicción de que se comportaría más cerca de a a*b != 0 porque 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 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)
Máquina virtual de servidor Java HotSpot (TM) de 64 bits (compilación 25.45-b02, modo mixto)

Answer 1

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)!=0 hará lo incorrecto para 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)!=0 hará lo incorrecto para 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 obtienes si es una operación int .)

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

• La VM optimizará la expresión durante las primeras ejecuciones del bucle externo ( fraction ), cuando la fraction es 0, cuando las ramas casi nunca se toman. El optimizador puede hacer cosas diferentes si comienza la fraction en 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] a 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 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 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 es necesario alguno de los valores de nums obtenidos para 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() está 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!

Answer 2

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.

Answer 3

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 != 0 puede 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 .

Answer 4

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 hacia dónde irá la rama y elegir especulativamente la próxima 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á 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 != 0 dará 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 caso de bifurcación condicional a * b != 0 , 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 != 0 y a | b != 0 a | b != 0 casos. Podría haber algo inteligente en la lógica de predictores de rama. 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 a y b .

Answer 5

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, podemos 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 falso. Ahora, es posible que no le importe que se evalúen nums[1][i] , 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.