Por que (a * b! = 0) é mais rápido que (a! = 0 && b! = 0) em Java?

Estou escrevendo algum código em Java, onde, em algum momento, o fluxo do programa é determinado por duas variáveis ​​int, "a" e "b", serem diferentes de zero (nota: aeb nunca são negativas e nunca dentro do intervalo de estouro inteiro).

Eu posso avaliar isso com

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

Ou alternativamente

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

Como eu esperava que esse trecho de código fosse executado milhões de vezes por execução, fiquei pensando qual seria o mais rápido. Fiz o experimento comparando-os em uma enorme matriz gerada aleatoriamente e também fiquei curioso para ver como a escarsidade da matriz (fração de dados = 0) afetaria os 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);
}

E os resultados mostram que se você espera que "a" ou "b" seja igual a 0 mais que ~ 3% do tempo, a*b != 0é mais rápido que a!=0 && b!=0:

Estou curioso para saber o porquê. Alguém poderia lançar alguma luz? É o compilador ou está no nível do hardware?

Edit: Por curiosidade ... agora que aprendi sobre a previsão de ramificação, fiquei pensando o que a comparação analógica mostraria para um OR b é diferente de zero:

Vemos o mesmo efeito de previsão de ramificação como esperado, curiosamente, o gráfico é um pouco invertido ao longo do eixo X.

Atualizar

1- Eu adicionei !(a==0 || b==0)à análise para ver o que acontece.

2- Incluí também a != 0 || b != 0, (a+b) != 0e (a|b) != 0por curiosidade, depois de aprender sobre a previsão de ramificações. Mas eles não são logicamente equivalentes às outras expressões, porque apenas um OR b precisa ser diferente de zero para retornar true, portanto, eles não devem ser comparados para obter eficiência de processamento.

3- Também adicionei o benchmark real que usei para a análise, que está apenas repetindo uma variável int arbitrária.

4- Algumas pessoas sugeriam incluir a != 0 & b != 0, ao contrário a != 0 && b != 0, com a previsão de que ele se comportaria mais de perto a*b != 0porque removeríamos o efeito de previsão do ramo. Eu não sabia que &poderia ser usado com variáveis ​​booleanas, pensei que era usado apenas para operações binárias com números inteiros.

Nota: No contexto em que eu estava considerando tudo isso, o excesso de int não é um problema, mas essa é definitivamente uma consideração importante em contextos gerais.

CPU: Intel Core i7-3610QM a 2.3GHz

Versão Java: 1.8.0_45
Java (TM) SE Runtime Environment (build 1.8.0_45-b14)
VM do servidor Java HotSpot (TM) de 64 bits (build 25.45-b02, modo misto)

Estou ignorando o problema de que seu benchmarking pode ter falhas e considerando o resultado pelo valor de face.

É o compilador ou está no nível do hardware?

Acho que esse último:

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

irá compilar para 2 cargas de memória e duas ramificações condicionais

  if (a * b != 0)

irá compilar para 2 cargas de memória, uma multiplicação e uma ramificação condicional.

A multiplicação provavelmente será mais rápida que a segunda ramificação condicional se a previsão de ramificação no nível do hardware for ineficaz. À medida que você aumenta a proporção ... a previsão do ramo se torna menos eficaz.

O motivo pelo qual as ramificações condicionais são mais lentas é que elas causam a interrupção do pipeline de execução das instruções. A previsão de ramificação consiste em evitar a paralisação, prevendo o caminho que a ramificação seguirá e escolhendo especulativamente a próxima instrução com base nisso. Se a previsão falhar, há um atraso enquanto a instrução para a outra direção é carregada.

(Nota: a explicação acima é simplificada demais. Para uma explicação mais precisa, você precisa examinar a literatura fornecida pelo fabricante da CPU para codificadores da linguagem assembly e escritores do compilador. A página da Wikipedia em Predictors de filial é um bom histórico.)

No entanto, há uma coisa que você precisa ter cuidado com essa otimização. Existem valores onde a * b != 0darão a resposta errada? Considere os casos em que a computação do produto resulta em excesso de número inteiro.

ATUALIZAR

Seus gráficos tendem a confirmar o que eu disse.

• Há também um efeito de "previsão de ramificação" no a * b != 0caso de ramificação condicional , e isso sai nos gráficos.

• Se você projetar as curvas além de 0,9 no eixo X, parece que 1) elas se encontrarão em cerca de 1,0 e 2) o ponto de encontro terá aproximadamente o mesmo valor Y que para X = 0,0.

ATUALIZAÇÃO 2

Não entendo por que as curvas são diferentes para a + b != 0os a | b != 0casos. Não poderia ser algo inteligente na lógica preditores de filiais. Ou pode indicar outra coisa.

(Observe que esse tipo de coisa pode ser específico para um número de modelo de chip específico ou mesmo para uma versão. Os resultados dos seus benchmarks podem ser diferentes em outros sistemas.)

No entanto, ambos têm a vantagem de trabalhar com todos os valores não negativos de ae b.

Acho que seu benchmark tem algumas falhas e pode não ser útil para inferir sobre programas reais. Aqui estão os meus pensamentos:

• (a|b)!=0e (a+b)!=0teste se qualquer valor é diferente de zero, enquanto que a != 0 && b != 0e (a*b)!=0de teste, se ambos são diferentes de zero. Portanto, você não está comparando o tempo apenas da aritmética: se a condição é verdadeira com mais frequência, ela causa mais execuções do ifcorpo, o que também leva mais tempo.

• (a+b)!=0 fará a coisa errada com valores positivos e negativos que somam zero, portanto você não pode usá-lo no caso geral, mesmo que funcione aqui.

• Da mesma forma, (a*b)!=0fará a coisa errada para valores que excedem. (Exemplo aleatório: 196608 * 327680 é 0 porque o resultado verdadeiro é divisível por 2 ³² , portanto, seus 32 bits baixos são 0 e esses bits são tudo o que você obtém se for uma intoperação.)

• A VM otimizará a expressão durante as primeiras execuções do fractionloop externo ( ), quando fractionfor 0, quando as ramificações quase nunca serão executadas. O otimizador pode fazer coisas diferentes se você começar fractioncom 0,5.

• A menos que a VM seja capaz de eliminar algumas das verificações de limites de matriz aqui, existem quatro outras ramificações na expressão apenas devido às verificações de limites, e esse é um fator complicador ao tentar descobrir o que está acontecendo em um nível baixo. Você pode obter resultados diferentes se dividir a matriz bidimensional em duas matrizes planas, alterando nums[0][i]e nums[1][i]para nums0[i]e nums1[i].

• Os preditores de ramificação da CPU detectam padrões curtos nos dados ou execuções de todas as ramificações que estão sendo obtidas ou não. Seus dados de referência gerados aleatoriamente são o pior cenário para um preditor de ramificação . Se os dados do mundo real tiverem um padrão previsível ou se houver longas execuções de valores zero e zero, as ramificações poderão custar muito menos.

• O código específico que é executado depois que a condição é atendida pode afetar o desempenho da avaliação da própria condição, porque afeta coisas como se o loop pode ou não ser desenrolado, quais registros da CPU estão disponíveis e se algum dos numsvalores buscados precisa ser reutilizado após avaliar a condição. O simples aumento de um contador no benchmark não é um espaço reservado perfeito para o que o código real faria.

• System.currentTimeMillis()na maioria dos sistemas, não é mais preciso que +/- 10 ms. System.nanoTime()geralmente é mais preciso.

Existem muitas incertezas, e sempre é difícil dizer algo definitivo com esses tipos de micro otimizações, porque um truque mais rápido em uma VM ou CPU pode ser mais lento em outra. Se estiver executando a JVM HotSpot de 32 bits, em vez da versão de 64 bits, saiba que ela tem dois tipos: a VM "Client" possui otimizações diferentes (mais fracas) em comparação com a VM "Server".

Se você pode desmontar o código de máquina gerado pela VM , faça isso em vez de tentar adivinhar o que faz!

As respostas aqui são boas, embora eu tenha uma ideia que possa melhorar as coisas.

Como as duas ramificações e a previsão de ramificação associada são os possíveis culpados, podemos reduzir a ramificação para uma única ramificação sem alterar a lógica.

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

Também pode funcionar para fazer

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

A razão é que, pelas regras do curto-circuito, se o primeiro booleano for falso, o segundo não deve ser avaliado. Ele precisa executar uma ramificação extra para evitar avaliar nums[1][i]se nums[0][i]era falso. Agora, você pode não se importar nums[1][i]com a avaliação, mas o compilador não pode ter certeza de que não lançará uma referência fora do intervalo ou nula quando o fizer. Ao reduzir o bloco if para bools simples, o compilador pode ser inteligente o suficiente para perceber que avaliar o segundo booleano desnecessariamente não terá efeitos colaterais negativos.

Quando tomamos a multiplicação, mesmo que um número seja 0, o produto é 0. Ao escrever

    (a*b != 0)

Ele avalia o resultado do produto, eliminando, assim, as primeiras ocorrências da iteração a partir de 0. Como resultado, as comparações são menores do que quando a condição é

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

Onde cada elemento é comparado com 0 e avaliado. Portanto, o tempo necessário é menor. Mas acredito que a segunda condição possa fornecer uma solução mais precisa.

Você está usando dados de entrada aleatórios, o que torna as ramificações imprevisíveis. Na prática, as ramificações são geralmente previsíveis (~ 90%), portanto, no código real, é provável que o código de ramificação seja mais rápido.

Dito isto. Não vejo como a*b != 0pode ser mais rápido que (a|b) != 0. Geralmente, a multiplicação de números inteiros é mais cara que um OR bit a bit. Mas coisas assim ocasionalmente ficam estranhas. Veja, por exemplo, o exemplo "Exemplo 7: Complexidades de hardware" da Galeria de Efeitos de Cache do Processador .