Pourquoi (a * b! = 0) est-il plus rapide que (a! = 0 && b! = 0) en Java?

J'écris du code en Java où, à un moment donné, le flux du programme est déterminé par le fait que deux variables int, "a" et "b", sont non nulles (note: a et b ne sont jamais négatives, et jamais dans la plage de dépassement d'entier).

Je peux l'évaluer avec

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

Ou bien

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

Parce que je m'attends à ce que ce morceau de code s'exécute des millions de fois par exécution, je me demandais lequel serait plus rapide. J'ai fait l'expérience en les comparant sur un énorme tableau généré de manière aléatoire, et j'étais également curieux de voir comment la rareté du tableau (fraction de données = 0) affecterait les résultats:

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);
}

Et les résultats montrent que si vous vous attendez à ce que "a" ou "b" soit égal à 0 plus de ~ 3% du temps, a*b != 0c'est plus rapide que a!=0 && b!=0:

Je suis curieux de savoir pourquoi. Quelqu'un pourrait-il faire la lumière? Est-ce le compilateur ou est-ce au niveau matériel?

Edit: Par curiosité ... maintenant que j'ai appris la prédiction de branche, je me demandais ce que la comparaison analogique montrerait pour un OR b est non nul:

Nous voyons le même effet de prédiction de branche que prévu, ce qui est intéressant, le graphique est quelque peu inversé le long de l'axe X.

Mise à jour

1- J'ai ajouté !(a==0 || b==0)à l'analyse pour voir ce qui se passe.

2- J'ai également inclus a != 0 || b != 0, (a+b) != 0et (a|b) != 0par curiosité, après avoir appris la prédiction de branche. Mais elles ne sont pas logiquement équivalentes aux autres expressions, car seul un OR b doit être différent de zéro pour retourner vrai, donc elles ne sont pas censées être comparées pour l'efficacité du traitement.

3- J'ai également ajouté le benchmark réel que j'ai utilisé pour l'analyse, qui est juste une itération d'une variable int arbitraire.

4- Certaines personnes ont suggéré d'inclure a != 0 & b != 0par opposition à a != 0 && b != 0, avec la prédiction qu'elle se comporterait plus étroitement a*b != 0car nous supprimerions l'effet de prédiction de branche. Je ne savais pas que cela &pouvait être utilisé avec des variables booléennes, je pensais que c'était seulement utilisé pour des opérations binaires avec des entiers.

Remarque: Dans le contexte que je considérais tout cela, le débordement int n'est pas un problème, mais c'est certainement une considération importante dans des contextes généraux.

Processeur: Intel Core i7-3610QM @ 2,3 GHz

Version Java: 1.8.0_45
Java (TM) SE Runtime Environment (build 1.8.0_45-b14)
VM Server HotSpot (TM) 64 bits Server (build 25.45-b02, mode mixte)

J'ignore le problème selon lequel votre analyse comparative pourrait être défectueuse et je prends le résultat à sa valeur nominale.

Est-ce le compilateur ou est-ce au niveau matériel?

Ce dernier, je pense:

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

compilera jusqu'à 2 charges de mémoire et deux branches conditionnelles

  if (a * b != 0)

compilera 2 charges de mémoire, une multiplication et une branche conditionnelle.

La multiplication est susceptible d'être plus rapide que la deuxième branche conditionnelle si la prédiction de branche au niveau matériel est inefficace. À mesure que vous augmentez le ratio ... la prédiction de branche devient moins efficace.

La raison pour laquelle les branches conditionnelles sont plus lentes est qu'elles entraînent le blocage du pipeline d'exécution des instructions. La prédiction de branche consiste à éviter le décrochage en prédisant dans quelle direction la branche va aller et en choisissant spéculativement la prochaine instruction en fonction de cela. Si la prédiction échoue, il y a un délai pendant le chargement de l'instruction pour l'autre sens.

(Remarque: l'explication ci-dessus est trop simplifiée. Pour une explication plus précise, vous devez consulter la documentation fournie par le fabricant de CPU pour les codeurs de langage d'assemblage et les rédacteurs de compilateurs. La page Wikipedia sur les prédicteurs de branche est un bon arrière-plan.)

Cependant, il y a une chose que vous devez faire attention avec cette optimisation. Y a-t-il des valeurs a * b != 0qui donneront la mauvaise réponse? Considérez les cas où le calcul du produit entraîne un débordement d'entier.

MISE À JOUR

Vos graphiques tendent à confirmer ce que j'ai dit.

• Il y a également un effet de "prédiction de branche" dans le a * b != 0cas de branche conditionnelle , et cela ressort dans les graphiques.

• Si vous projetez les courbes au-delà de 0,9 sur l'axe X, il semble que 1) elles se rencontreront à environ 1,0 et 2) le point de rencontre sera à peu près la même valeur Y que pour X = 0,0.

MISE À JOUR 2

Je ne comprends pas pourquoi les courbes sont différentes pour le a + b != 0et les a | b != 0cas. Il pourrait y avoir quelque chose d'intelligent dans la logique des prédicteurs de branche. Ou cela pourrait indiquer autre chose.

(Notez que ce genre de chose peut être spécifique à un numéro de modèle de puce ou même à une version particulière. Les résultats de vos tests de performances peuvent être différents sur d'autres systèmes.)

Cependant, ils ont tous les deux l'avantage de fonctionner pour toutes les valeurs non négatives de aet b.

Je pense que votre point de repère a quelques défauts et pourrait ne pas être utile pour déduire des programmes réels. Voici mes pensées:

• (a|b)!=0et (a+b)!=0tester si l'une ou l'autre valeur est non nulle, tandis que a != 0 && b != 0et (a*b)!=0tester si les deux sont non nulles. Donc, vous ne comparez pas seulement le moment de l'arithmétique: si la condition est vraie plus souvent, elle provoque plus d'exécutions du ifcorps, ce qui prend plus de temps aussi.

• (a+b)!=0 fera la mauvaise chose pour les valeurs positives et négatives qui se résument à zéro, vous ne pouvez donc pas l'utiliser dans le cas général, même si cela fonctionne ici.

• De même, (a*b)!=0fera la mauvaise chose pour les valeurs qui débordent. (Exemple aléatoire: 196608 * 327680 est 0 parce que le vrai résultat est divisible par 2 ³² , donc ses 32 bits bas sont 0, et ces bits sont tout ce que vous obtenez si c'est une intopération.)

• La machine virtuelle optimisera l'expression lors des premières exécutions de la fractionboucle externe ( ), lorsqu'elle fractionvaut 0, lorsque les branches ne sont presque jamais prises. L'optimiseur peut faire différentes choses si vous commencez fractionà 0,5.

• À moins que la machine virtuelle ne soit en mesure d'éliminer certaines des vérifications des limites du tableau ici, il y a quatre autres branches dans l'expression juste en raison des vérifications des limites, et c'est un facteur de complication lorsque vous essayez de comprendre ce qui se passe à un bas niveau. Vous pouvez obtenir des résultats différents si vous divisez le tableau bidimensionnel en deux tableaux plats, en changeant nums[0][i]et nums[1][i]vers nums0[i]et nums1[i].

• Les prédicteurs de branche du CPU détectent des modèles courts dans les données, ou des exécutions de toutes les branches prises ou non prises. Vos données de référence générées de manière aléatoire sont le pire des cas pour un prédicteur de branche . Si les données du monde réel ont un modèle prévisible, ou si elles comportent de longues séries de valeurs entièrement nulles et non nulles, les branches pourraient coûter beaucoup moins.

• Le code particulier qui est exécuté après que la condition est remplie peut affecter les performances de l'évaluation de la condition elle-même, car cela affecte des choses comme le fait que la boucle puisse être déroulée ou non, quels registres CPU sont disponibles et si l'une des numsvaleurs extraites doit être réutilisé après avoir évalué la condition. Le simple fait d'incrémenter un compteur dans l'indice de référence n'est pas un espace réservé parfait pour ce que ferait un vrai code.

• System.currentTimeMillis()est sur la plupart des systèmes pas plus précis que +/- 10 ms. System.nanoTime()est généralement plus précis.

Il y a beaucoup d'incertitudes, et il est toujours difficile de dire quoi que ce soit de défini avec ces sortes de micro-optimisations, car une astuce plus rapide sur une VM ou CPU peut être plus lente sur une autre. Si vous exécutez la JVM HotSpot 32 bits, plutôt que la version 64 bits, sachez qu'il existe en deux versions: avec la machine virtuelle "Client" ayant des optimisations différentes (plus faibles) par rapport à la machine virtuelle "Serveur".

Si vous pouvez démonter le code machine généré par la machine virtuelle , faites-le plutôt que d'essayer de deviner ce qu'il fait!

Les réponses ici sont bonnes, même si j'avais une idée qui pourrait améliorer les choses.

Étant donné que les deux branches et la prédiction de branche associée sont le coupable probable, nous pouvons être en mesure de réduire la ramification à une seule branche sans changer la logique du tout.

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

Cela peut aussi fonctionner

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

La raison étant, selon les règles de court-circuitage, si le premier booléen est faux, le second ne doit pas être évalué. Il doit effectuer une branche supplémentaire pour éviter d'évaluer nums[1][i]s'il nums[0][i]était faux. Maintenant, vous ne pouvez pas vous soucier de ce qui nums[1][i]est évalué, mais le compilateur ne peut pas être certain qu'il ne lèvera pas une référence hors plage ou nulle lorsque vous le ferez. En réduisant le bloc if à de simples bools, le compilateur peut être assez intelligent pour se rendre compte que l'évaluation du second booléen n'aura pas d'effets secondaires négatifs.

Quand on prend la multiplication, même si un nombre est 0, alors le produit est 0. Lors de l'écriture

    (a*b != 0)

Il évalue le résultat du produit éliminant ainsi les premières occurrences de l'itération à partir de 0. Par conséquent, les comparaisons sont inférieures à celles lorsque la condition est

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

Où chaque élément est comparé à 0 et évalué. Le temps requis est donc moindre. Mais je crois que la deuxième condition pourrait vous donner une solution plus précise.

Vous utilisez des données d'entrée randomisées qui rendent les branches imprévisibles. Dans la pratique, les branches sont souvent prévisibles (~ 90%), donc dans le code réel, le code avec branches est susceptible d'être plus rapide.

Cela dit. Je ne vois pas comment cela a*b != 0peut être plus rapide que (a|b) != 0. Généralement, la multiplication entière est plus chère qu'un OU au niveau du bit. Mais des choses comme ça deviennent parfois bizarres. Voir par exemple l'exemple "Exemple 7: Complexité matérielle" de la galerie des effets de cache de processeur .