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

Question

Je suis en train d'écrire un peu de code en Java où, à un certain point, le flux du programme est déterminé par le fait que deux variables de type int, "a" et "b", sont non nuls (note: a et b ne sont jamais négatifs, et jamais à l'intérieur de dépassement d'entier).

Je peux l'évaluer avec

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

Ou sinon

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

Parce que j'attends de ce morceau de code à exécuter des millions de fois par run, je me demandais ce qui serait plus rapide. J'ai fait l'expérience, en les comparant sur un énorme généré de façon aléatoire tableau, et j'étais également curieux de voir comment la densité de la matrice (fraction de données = 0) aurait une incidence sur 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 à "a" ou "b" être égal à 0 plus de ~3% du temps, en a*b != 0 plus rapide que de l' a!=0 && b!=0:

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

Edit: par curiosité... maintenant que j'ai appris à propos de la direction de la prévision, je me demandais ce que l'analogique comparaison serait pour OU b est non nul:

Nous voyons le même effet de la direction de la prévision comme prévu, il est intéressant de noter que le graphique est un peu retourné le long de l'axe des abscisses.

Mise à jour

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

2 - j'ai aussi inclus des a != 0 || b != 0, (a+b) != 0 et (a|b) != 0 de la curiosité, après avoir appris direction de la prévision. Mais ils ne sont pas logiquement équivalent aux autres expressions, parce que seulement un OU b doit être non nulle pour renvoyer la valeur true, alors qu'ils ne sont pas destinés à être comparés pour l'efficacité du traitement.

3 - j'ai aussi ajouté le réel de l'indice de référence que j'ai utilisé pour l'analyse, qui est juste une itération à l'arbitraire d'un variable int.

4 - Certaines personnes ont été suggérant d'inclure a != 0 & b != 0 plutôt a != 0 && b != 0, avec la prédiction que celui-ci se comporte de plus près à l' a*b != 0 parce que nous priverait de la direction de la prédiction de l'effet. Je ne savais pas qu' & peut être utilisé avec des variables booléennes, je pensais que c'était seulement utilisé pour les opérations binaires avec des entiers.

Remarque: Dans le contexte que j'ai été en considérant tout cela, int débordement n'est pas un problème, mais c'est certainement un facteur important dans les contextes généraux.

PROCESSEUR: Intel Core i7-3610QM - @ 2.3 GHz

Java version: 1.8.0_45
Java(TM) SE Runtime Environment (build 1.8.0_45-b14)
Java HotSpot(TM) 64-Bit Server VM (build à 25,45-b02, en mode mixte)

Answer 1

Je suis ignorant de la question que votre analyse comparative peut - être imparfait, et en prenant le résultat à la valeur nominale.

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

Cette dernière, je pense que:

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

compiler à 2 mémoire de charges et de deux branches conditionnelles

  if (a * b != 0)

compiler à 2 mémoire des charges, une multiplication et une branche conditionnelle.

Multiplier, est susceptible d'être plus rapide que la seconde branche conditionnelle si le matériel niveau de la direction de la prévision est inefficace. L'augmentation du ratio de ... la direction de la prévision devient de moins en moins efficace.

La raison que les branches conditionnelles sont plus lents, c'est qu'ils provoquent de l'exécution des instructions du pipeline de décrochage. Direction de la prévision consiste à éviter le décrochage par de prédire de quel côté de la direction de la va partir, et même le choix de la prochaine instruction. Si la prédiction d'échec, il existe un délai pendant l'instruction pour l'autre direction est chargé.

(Remarque: l'explication ci-dessus est simplifiée à l'extrême. Pour une explication plus précise, vous avez besoin de regarder la documentation fournie par le fabricant du PROCESSEUR pour le montage de la langue des codeurs et des rédacteurs du compilateur. La page de Wikipedia sur la Direction des Prédicteurs est bon fond.)

---

Cependant, il y a une chose que vous devez être prudent avec cette optimisation. Existe-il des valeurs en a * b != 0 va donner une mauvaise réponse? Examiner les cas où le calcul du produit des résultats dans le débordement d'entier.

---

Mise à JOUR

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

• Il y a aussi une branche "prédiction" en vigueur dans la branche conditionnelle a * b != 0 des cas, ce qui vient dans les graphiques.

• Si vous projet les courbes au-delà de 0,9 sur l'axe des X, il ressemble à 1), ils se rencontrent à environ 1,0 et 2) le point de rencontre sera à peu près la même valeur de Y pour X = 0.0.

---

Mise à JOUR 2

Je ne comprends pas pourquoi les courbes sont différentes pour l' a + b != 0 et de la a | b != 0 des cas. Il pourrait être quelque chose d'intelligent dans la branche des facteurs prédictifs de la logique. Ou elle pourrait indiquer autre chose.

(Notez que ce genre de chose peut être spécifique à une puce numéro de modèle ou la même version. Les résultats de vos critères de référence peut être différente sur les autres systèmes).

Cependant, ils ont tous deux l'avantage de travailler pour tous les non-valeurs négatives de a et b.

Answer 2

Je pense que votre point de référence a des défauts et ne peut pas être utile pour inférer sur de vrais programmes. Voici mes réflexions:

• (a*b)!=0 va faire la mauvaise chose pour les valeurs de dépassement de capacité, et (a+b)!=0 devrez en plus de faire la mauvaise chose pour les valeurs positives et négatives d'un montant de zéro, de sorte que vous ne pouvez pas utiliser l'une de ces expressions dans le cas général, même si ils travaillent ici.

• (a|b)!=0 et (a+b)!=0 sont des tests si soit la valeur est non nulle, alors qu' (a*b)!=0 et a != 0 && b != 0 sont des tests si les deux sont non nuls. Les deux types de conditions qui ne sera pas le cas sur le même pourcentage de données.

• La machine virtuelle permettra d'optimiser l'expression au cours de la première quelques pistes de l'extérieur (fraction) en boucle, lors de l' fraction 0, lorsque les branches sont presque jamais pris. L'optimiseur peut faire des choses différentes si vous commencez fraction à 0.5.

• À moins que la VM est en mesure d'éliminer certaines des limites du tableau vérifie ici, il y a quatre autres branches de l'expression juste en raison des limites des contrôles, et c'est un facteur de complication lors de la tentative de comprendre ce qui se passe à un niveau faible. Vous pouvez obtenir des résultats différents si vous divisez le tableau à deux dimensions dans les plats deux tableaux, l'évolution nums[0][i] et nums[1][i] de nums0[i] et nums1[i].

• CPU direction des prédicteurs essayer de détecter des courts de modèles dans les données, ou les courses de toutes les branches d'être prises ou non. Vos généré de façon aléatoire des données de référence est la pire chose pour une branche prédicteur d'essayer de traiter avec. Si vos données réelles a un schéma prévisible, ou il a de longues courses de zéro pour tous et toutes-les valeurs non nulles, les branches pourraient coûter beaucoup moins.

• Le code qui est exécuté après que la condition est remplie peut affecter les performances de l'évaluation de l'état lui-même, car elle affecte les choses comme si ou non la boucle peut être déroulé, les registres CPU sont disponibles, et si l'un des récupérée nums valeurs doivent être réutilisé après l'évaluation de la condition. Simplement incrémenter un compteur dans l'indice de référence n'est pas un parfait espace réservé pour ce qu'est le vrai code.

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

Comme vous pouvez le voir il y a beaucoup d'incertitudes, et il est toujours difficile de dire quelque chose de précis avec ce genre de micro-optimisations parce qu'un truc qui est plus rapide sur une machine virtuelle ou de l'UC peut être plus lent sur l'autre. Si votre machine virtuelle HotSpot, sachez qu'il existe deux autres variétés, avec le "Client" VM ayant différents (plus faible) optimisations par rapport au "Serveur" de la VM.

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

Answer 3

Les réponses sont bonnes ici, si j'ai eu une idée qui pourrait améliorer les choses.

Depuis les deux branches et des associés de la succursale de prédiction sont probablement coupable, nous pouvons être en mesure de réduire le branchement à une seule branche, sans modification de la logique à tous.

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

Il peut aussi travailler à faire

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

La raison d'être, par les règles de court-circuit, si le premier booléen est faux, la seconde ne doit pas être évaluée. Il doit effectuer un supplément de branche pour éviter d'évaluation nums[1][i] si nums[0][i] était faux. Maintenant, vous ne pouvez pas les soins qu' nums[1][i] obtient évaluée, mais le compilateur ne peut pas être certain qu'il ne va pas faire un hors de portée ou la valeur null réf quand vous le faites. En réduisant le bloc si simple booléens, le compilateur peut être assez intelligent pour réaliser que l'évaluation de la deuxième boolean inutilement de ne pas avoir des effets secondaires négatifs.

Answer 4

Lorsque nous prenons la multiplication, même si un seul numéro est 0, alors le produit est de 0. Lors de l'écriture

    (a*b != 0)

Il évalue le résultat du produit et ainsi d'éliminer les premières occurrences de l'itération à partir de 0. En conséquence, les comparaisons sont moins que lorsque la condition est

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

Où chaque élément est par rapport à 0 et évalués. Donc le temps nécessaire est de moins en moins. Mais je crois que la deuxième condition peut vous donner une solution plus précise.

Answer 5

Vous utilisez randomisés de saisie de données ce qui rend les branches imprévisible. Dans la pratique, les branches sont souvent (~90%) prévisible donc, dans le code réel de l'branchful code est susceptible d'être plus rapide.

Qui a dit. Je ne vois pas comment a*b != 0 peut être plus rapide que l' (a|b) != 0. Généralement entier la multiplication est plus cher qu'un bit à bit OU. Mais ce genre de choses parfois étranges. Voir par exemple la "Exemple 7: Matériel de complexités" exemple à partir de la Galerie de la mémoire Cache du Processeur d'Effets.