Si thens sont plus rapides que la multiplication et l'affectation?
https://stackoverflow.com/questions/4024201
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai une petite question, je suppose que le code suivant et il est répété de manière simliar 10 fois par exemple.
if blah then
number = number + 2^n
end if
Ne serait-il plus rapide d'évaluer:
number = number + blah*2^n?
Ce qui nous amène aussi la question, pouvez-vous multiplier un temps de valeur booléenne un entier (bien que je ne suis pas sûr du type qui est renvoyée par 2 ^ n, est-il un entier ou unsigned..etc)? (Je travaille en Ada, mais nous allons essayer de généraliser ce peut-être?)
EDIT: Désolé je dois préciser que je suis à la recherche à 2 à la puissance n, et je mis c là parce que je me suis intéressé à mon propre apprentissage à l'avenir si jamais je tombe sur ce problème dans c et je pense qu'il sont plus programmeurs c là-bas sur ces cartes alors Ada (je suppose, et vous savez ce que cela signifie), mais mon problème actuel est dans la langue Ada, mais la question devrait être assez indépendant de la langue (je l'espère).
La solution
si nous parlons C et bla ne relève pas de votre contrôle, alors il suffit de faire ceci:
if(blah) number += (1<<n);
Il n'y a vraiment pas un booléen en C et n'a pas besoin d'être faux est nul et vrai n'est pas nul, de sorte que vous ne pouvez pas supposer que zéro est 1 qui est ce que vous avez besoin pour votre solution, et vous ne pouvez assumer qu'un bit particulier en bla est réglé, par exemple:
number += (blah&1)<<n;
travaillerais pas nécessairement soit parce que 0x2 ou 0x4 ou quoi que ce soit non nul avec bit zéro clair est considéré comme un vrai. En règle générale, vous trouverez 0xfff ... FFFF (moins un, ou tous les) utilisés comme vrai, mais vous ne pouvez pas compter sur typique.
Maintenant, si vous êtes un contrôle total sur la valeur blah, et le garder strictement à 0 pour faux et 1 pour vrai alors vous pourriez faire ce que vous posiez sur:
number += blah<<n;
Et éviter le risque d'une branche, remplissage supplémentaire de ligne de cache, etc.
Retour au cas générique si, en prenant cette solution générique:
unsigned int fun ( int blah, unsigned int n, unsigned int number )
{
if(blah) number += (1<<n);
return(number);
}
Et la compilation pour les deux plates-formes / utilisées les plus populaires:
testl %edi, %edi
movl %edx, %eax
je .L2
movl $1, %edx
movl %esi, %ecx
sall %cl, %edx
addl %edx, %eax
.L2:
Les utilisations ci-dessus une branche conditionnelle.
L'une des utilisations ci-dessous d'exécution conditionnelle, aucune branche, sans chasse d'eau de pipeline, est déterministe.
cmp r0,#0 movne r3,#1 addne r2,r2,r3,asl r1 mov r0,r2 bx lr
aurait pu sauver le mov r0, instruction par r2 réorganisant les arguments dans l'appel de fonction, mais ce qui est académique, vous ne seriez pas brûler un appel de fonction sur ce normalement.
EDIT:
Comme suggéré:
unsigned int fun ( int blah, unsigned int n, unsigned int number )
{
number += ((blah!=0)&1)<<n;
return(number);
}
subs r0, r0, #0 movne r0, #1 add r0, r2, r0, asl r1 bx lr
Certes, moins cher, et le code semble bon, mais je ne reviendrai pas faire des hypothèses que le résultat de bla! = 0, ce qui est égal à zéro ou quel que soit le compilateur a défini comme vrai a toujours l'ensemble de LSBit. Il n'a pas besoin d'avoir ce bit pour le compilateur de générer du code de travail. Peut-être que les normes dictent la valeur spécifique pour vrai. par réarranger les paramètres de la fonction du nombre si (bla) + = ... se traduira également par trois instructions d'horloge unique et ne pas avoir des hypothèses.
EDIT2:
En regardant ce que je crois être la norme C99:
Le == (égal) et! = (Pas égal à) Les opérateurs sont analogues à la opérateurs relationnels, à l'exception de leur priorité inférieure. Chacun de opérateurs rendements 1 si le spécifié relation est vraie et 0 si elle est fausse.
Ce qui explique pourquoi les travaux d'édition ci-dessus et pourquoi vous obtenez le movne r0, # 1 et pas un autre nombre aléatoire.
L'affiche a posé la question en ce qui concerne C, mais a également noté que l'ADA était la langue actuelle, d'une langue point de vue indépendant, vous ne devriez pas supposer « caractéristiques » comme la fonction C ci-dessus et utiliser un if (bla) nombre = nombre + (1 << n). Mais cela a été demandé avec une étiquette C de sorte que le génériquement (processeur indépendant) résultat le plus rapide C est, je pense, le nombre + = << n (bla = 0!); Donc, le commentaire de Steven Wright avait raison et il devrait obtenir un crédit pour cela.
si vous pouvez obtenir blah dans un 0 ou 1 sous forme puis l'utiliser dans le calcul est plus rapide dans le sens qu'il n'y a pas de branche L'hypothèse d'affiches est fondamentalement correcte,. Obtenir dans cette forme sans qu'il soit plus cher qu'une branche est le truc.
Autres conseils
Il n'y a pas de réponse générale à cette question, cela dépend beaucoup de votre compilateur et CPU. CPU modernes ont instructions conditionnelles, donc tout est possible.
Les seuls moyens de savoir ici doivent inspecter l'assembleur qui est produit (généralement -S comme option du compilateur) et de mesurer.
En Ada ...
La formulation d'origine:
if Blah then
Number := Number + (2 ** N);
end if;
L'alternative formulation générale, en supposant que Blah est de type booléen et le nombre et N sont des types appropriés:
Number := Number + (Boolean'pos(Blah) * (2 ** N));
(Pour N et Number de nombre entier défini par l'utilisateur ou les types à virgule flottante, les définitions appropriées et les conversions de type peut être nécessaire, le point clé est la construction Boolean'pos() ici, ce qui garantit Ada vous donnera un 0 ou 1 pour l'opérateur booléen prédéfini Type.)
Quant à savoir si cela est plus rapide ou pas, je souscris à @Cthutu:
je garderais avec le conditionnel. Vous ne devriez pas vous soucier de bas niveau détails optimisation à ce stade. Recopiez le code qui décrit votre meilleur algorithme et la confiance de votre compilateur.
je garderais avec le conditionnel. Vous ne devriez pas se soucier des détails d'optimisation de bas niveau à ce stade. Ecrire le code qui décrit votre algorithme le mieux et faire confiance à votre compilateur. Sur certains processeurs de la multiplication est plus lente (par exemple les processeurs ARM qui ont conditionals sur chaque instruction). Vous pouvez également utiliser le: expression qui optimise mieux sous certains compilateurs. Par exemple:
number += (blah ? 2^n : 0);
Si pour une raison quelconque ce petit calcul est le goulot d'étranglement de votre application après profilage puis vous soucier de l'optimisation de bas niveau.
En C, en ce qui concerne blah * 2 ^ n: Avez-vous des raisons de croire que blah prend les valeurs 0 et 1? La langue promet seulement que 0 <-> FAUX et (tout le reste) <-> TRUE. C vous permet de multiplier temporaire « booléen » avec un autre numéro, mais ne définit pas le résultat, sauf dans la mesure où result = 0 la bool était <=> faux ou le nombre était égal à zéro.
En Ada, en ce qui concerne blah * 2 ^ n: La langue ne définit pas un opérateur de multiplication du type Boolean. Ainsi blah ne peut pas être un bool et être multipliés.
Si votre langue permet la multiplication entre un booléen et un certain nombre, alors oui, qui est plus rapide qu'un conditionnel. Conditionals ont besoin de branchement, qui peut invalider le pipeline de la CPU. De plus, si la branche est assez grand, il peut même provoquer un défaut de cache dans les instructions, bien que ce soit peu probable dans votre petit exemple.
Généralement, et en particulier lorsque vous travaillez avec Ada, vous ne devriez pas vous soucier des problèmes de micro-optimisation comme celui-ci. Écrivez votre code afin qu'il soit clair pour un lecteur, et ne vous inquiétez pas sur les performances lorsque vous avez un problème avec des performances, et l'ont traqué à cette partie du code.
Les différents processeurs ont des besoins différents, et ils peuvent être incroyablement complexe. Par exemple, dans ce cas, qui est plus rapide dépend beaucoup sur la configuration du pipeline de votre CPU, ce qui est dans le cache à l'époque, et comment ses travaux de l'unité de prédiction de branchement. Une partie du travail de votre compilateur est d'être un expert en ces choses, et il fera un meilleur travail que tous, mais les meilleurs programmeurs de montage. Certianly mieux que vous (ou moi).
Alors que vous venez de vous soucier d'écrire un bon code, et laisser le souci du compilateur de faire du code machine efficace hors de celui-ci.
Pour le problème posé, il y a en effet des expressions simples en C qui peuvent produire du code efficace.
Le pouvoir nth de 2 peut être calculée avec l'opérateur << comme 1 << n, à condition n est inférieur au nombre de bits de valeur dans un int.
Si blah est boolean , à savoir un int avec une valeur de 0 ou 1, votre fragment de code peut être écrit:
number += blah << n;
Si blah est un scalaire qui peut être testé pour sa valeur de vérité if (blah), l'expression est un peu plus complexe:
number += !!blah << n;
ce qui équivaut à number += (blah != 0) << n;
Le test est toujours présent, mais, pour les architectures modernes, le code généré pas de sauts, comme peut être vérifiée à l'aide en ligne explorateur de compilateur de Godbolt.
Dans les deux cas, vous ne pouvez pas éviter une branche (en interne), donc ne pas essayer!
Dans
number = number + blah*2^n
la pleine expression devra toujours être évalué, à moins que le compilateur est assez intelligent pour arrêter quand blah est 0. Si elle est, vous aurez une branche si blah est 0. Si ce n'est pas, vous obtenez toujours un cher multiplier. En cas blah est faux, vous aurez également l'ajout inutile et l'affectation.
Dans le « if then » déclaration, la déclaration ne fait l'ajout et l'affectation quand blah est vrai.
En bref, la réponse à votre question dans ce cas est « oui ».
Ce code montre qu'ils fonctionnent de manière semblable, mais la multiplication est généralement un peu plus rapide.
@Test
public void manual_time_trial()
{
Date beforeIfElse = new Date();
if_else_test();
Date afterIfElse = new Date();
long ifElseDifference = afterIfElse.getTime() - beforeIfElse.getTime();
System.out.println("If-Else Diff: " + ifElseDifference);
Date beforeMultiplication = new Date();
multiplication_test();
Date afterMultiplication = new Date();
long multiplicationDifference = afterMultiplication.getTime() - beforeMultiplication.getTime();
System.out.println("Mult Diff : " + multiplicationDifference);
}
private static long loopFor = 100000000000L;
private static short x = 200;
private static short y = 195;
private static int z;
private static void if_else_test()
{
short diff = (short) (y - x);
for(long i = 0; i < loopFor; i++)
{
if (diff < 0)
{
z = -diff;
}
else
{
z = diff;
}
}
}
private static void multiplication_test()
{
for(long i = 0; i < loopFor; i++)
{
short diff = (short) (y - x);
z = diff * diff;
}
}
