On m'a appris que le déplacement en binaire est beaucoup plus efficace que la multiplication par 2 ^ k. J'ai donc voulu expérimenter, et j'ai utilisé le code suivant pour tester cela:
#include <time.h>
#include <stdio.h>
int main() {
clock_t launch = clock();
int test = 0x01;
int runs;
//simple loop that oscillates between int 1 and int 2
for (runs = 0; runs < 100000000; runs++) {
// I first compiled + ran it a few times with this:
test *= 2;
// then I recompiled + ran it a few times with:
test <<= 1;
// set back to 1 each time
test >>= 1;
}
clock_t done = clock();
double diff = (done - launch);
printf("%f\n",diff);
}
Pour les deux versions, l'impression était d'environ 440000, donner ou prendre 10000. Il n'y avait pas (visuellement, au moins) de différence significative entre les sorties des deux versions. Ma question est donc la suivante: y a-t-il un problème avec ma méthodologie? Devrait-il même y avoir une différence visuelle? Est-ce que cela a quelque chose à voir avec l'architecture de mon ordinateur, le compilateur ou autre chose?
c
efficiency
bitwise-operators
NicholasFolk
la source
la source
gcc -S
, le code detest *= 2
est en fait compilé enshll $1, %eax
Lorsqu'il est appelé avecgcc -O3 -S
il n'y a même pas de boucle. Les deux appels d'horloge sont séparés par une ligne:callq _clock
movq %rax, %rbx
callq _clock
Réponses:
Comme indiqué dans l'autre réponse, la plupart des compilateurs optimisent automatiquement les multiplications à effectuer avec des décalages de bits.
Il s'agit d'une règle très générale lors de l'optimisation: la plupart des «optimisations» induisent en erreur la compilation sur ce que vous voulez vraiment dire, et peuvent même réduire les performances.
Optimisez uniquement lorsque vous avez remarqué un problème de performances et mesuré le problème. (et la plupart du code que nous écrivons n'est pas exécuté aussi souvent, donc nous n'avons pas besoin de nous embêter)
Le gros inconvénient de l'optimisation est que le code «optimisé» est souvent beaucoup moins lisible. Donc, dans votre cas, optez toujours pour la multiplication lorsque vous cherchez à vous multiplier. Et optez pour le décalage de bits lorsque vous souhaitez déplacer des bits.
la source
Le compilateur reconnaît les constantes et convertit les multiplications en décalages le cas échéant.
la source
Que le décalage soit plus rapide que la multiplication dépend de l'architecture de votre CPU. À l'époque du Pentium et plus tôt, le décalage était souvent plus rapide que la multiplication, selon le nombre de 1 bits dans votre multiplicande. Par exemple, si votre multiplicande était de 320, c'est 101000000, deux bits.
Mais si vous aviez plus de deux bits ...
Sur un petit microcontrôleur comme un PIC18 avec multiplication à cycle unique, mais sans décalage de barillet , la multiplication est plus rapide si vous changez de plus de 1 bit.
Notez que c'est le contraire de ce qui était vrai sur les anciens processeurs Intel.
Mais ce n'est toujours pas aussi simple. Si je me souviens bien, en raison de son architecture Superscalar, un Pentium a pu traiter une instruction de multiplication ou deux instructions de décalage simultanément (tant qu'elles ne dépendaient pas l'une de l'autre). Cela signifie que si vous souhaitez multiplier deux variables par une puissance de 2, alors le décalage peut être préférable.
la source
Vous avez plusieurs problèmes avec votre programme de test.
Tout d'abord, vous n'utilisez pas réellement la valeur de
test
. Il n'y a aucun moyen, dans la norme C, que la valeur destest
choses. L'optimiseur est totalement gratuit pour le supprimer. Une fois qu'il est supprimé, votre boucle est en fait vide. Le seul effet visible serait de définirruns = 100000000
, maisruns
n'est pas non plus utilisé. L'optimiseur peut donc (et devrait!) Supprimer la boucle entière. Solution facile: imprimez également la valeur calculée. Notez qu'un optimiseur suffisamment déterminé pourrait encore optimiser la boucle (il repose entièrement sur des constantes connues au moment de la compilation).Deuxièmement, vous effectuez deux opérations qui s'annulent. L'optimiseur est autorisé à le remarquer et à les annuler . Laissant à nouveau une boucle vide, et supprimé. Celui-ci est carrément difficile à réparer. Vous pouvez passer à un
unsigned int
(donc le débordement n'est pas un comportement indéfini), mais cela se traduit bien sûr par 0. Et les choses simples (comme, disonstest += 1
) sont assez faciles à comprendre pour l'optimiseur, et c'est le cas.Enfin, vous supposez que cela
test *= 2
va être compilé en multipliant. C'est une optimisation très simple; si le décalage est plus rapide, l'optimiseur l'utilisera à la place. Pour contourner ce problème, vous devez utiliser quelque chose comme un assemblage en ligne spécifique à l'implémentation.Ou, je suppose, vérifiez simplement la fiche technique de votre microprocesseur pour voir laquelle est la plus rapide.
Lorsque j'ai vérifié la sortie d'assemblage de la compilation de votre programme à l'
gcc -S -O3
aide de la version 4.9, l'optimiseur a en fait vu toutes les variantes simples ci-dessus, et plusieurs autres. Dans tous les cas, il a supprimé la boucle (en attribuant une constante àtest
), la seule chose qui restait était les appels àclock()
, la conversion / soustraction et leprintf
.la source
gcc -O3
(maintenant avec 7.3) supprime toujours la boucle. (Assurez-vous de passer à long au lieu de int si nécessaire, sinon il l'optimise dans une boucle infinie en raison d'un débordement).Je pense qu'il serait plus utile pour le questionneur d'avoir une réponse plus différenciée, car je vois plusieurs hypothèses non examinées dans les questions et dans certaines des réponses ou des commentaires.
Le temps d'exécution relatif résultant du décalage et de la multiplication n'a rien à voir avec C. Quand je dis C, je ne parle pas de l'instance d'une implémentation spécifique, telle que telle ou telle version de GCC, mais du langage. Je ne veux pas prendre cet ad absurdum, mais utiliser un exemple extrême pour illustrer: vous pouvez implémenter un compilateur C entièrement conforme aux normes et avoir une multiplication prendre une heure, tandis que le décalage prend des millisecondes - ou l'inverse. Je n'ai pas connaissance de telles restrictions de performances en C ou C ++.
Vous ne pouvez pas vous soucier de cette technicité dans l'argumentation. Votre intention était probablement de simplement tester les performances relatives des changements par rapport aux multiplications et vous avez choisi C, car il est généralement perçu comme un langage de programmation de bas niveau, donc on peut s'attendre à ce que son code source se traduise plus directement en instructions correspondantes. De telles questions sont très courantes et je pense qu'une bonne réponse devrait souligner que même en C, votre code source ne se traduit pas en instructions aussi directement que vous le pensez dans un cas donné. Je vous ai donné quelques résultats de compilation possibles ci-dessous.
C'est là que les commentaires qui remettent en question l'utilité de remplacer cette équivalence dans les logiciels du monde réel entrent en jeu. Vous pouvez en voir dans les commentaires de votre question, comme celui d'Eric Lippert. Cela correspond à la réaction que vous obtiendrez généralement d'ingénieurs plus expérimentés en réponse à de telles optimisations. Si vous utilisez des décalages binaires dans le code de production comme moyen de multiplication et de division, les gens vont très probablement grincer des dents à votre code et avoir un certain degré de réaction émotionnelle ("J'ai entendu cette affirmation absurde concernant JavaScript pour l'amour du ciel.") Pour cela peut ne pas avoir de sens pour les programmeurs débutants, à moins qu'ils ne comprennent mieux les raisons de ces réactions.
Ces raisons sont principalement une combinaison de la lisibilité réduite et de la futilité d'une telle optimisation, comme vous l'avez peut-être déjà découvert en comparant leurs performances relatives. Cependant, je ne pense pas que les gens auraient une réaction aussi forte si la substitution du décalage à la multiplication était le seul exemple de telles optimisations. Des questions comme la vôtre se posent fréquemment sous diverses formes et dans différents contextes. Je pense que ce à quoi réagissent les ingénieurs les plus expérimentés, du moins parfois, c'est qu'il existe un risque de dommages beaucoup plus large lorsque les gens utilisent généreusement de telles micro-optimisations dans la base de code. Si vous travaillez dans une entreprise comme Microsoft sur une base de code volumineuse, vous passerez beaucoup de temps à lire le code source d'autres ingénieurs, ou tenterez d'y trouver un certain code. Il se peut même que ce soit votre propre code que vous essayiez de comprendre dans quelques années, en particulier à certains moments les plus inopportuns, comme lorsque vous devez corriger une panne de production suite à un appel que vous avez reçu en étant sur pager. un devoir un vendredi soir, sur le point de partir pour une soirée de plaisir avec des amis… Si vous passez autant de temps à lire le code, vous apprécierez qu'il soit aussi lisible que possible. Imaginez lire votre roman préféré, mais l'éditeur a décidé de sortir une nouvelle édition où ils utilisent abbrv. tout ovr th plc bcs thy thnk it svs spc. Cela ressemble aux réactions que d'autres ingénieurs peuvent avoir à votre code, si vous les saupoudrez de telles optimisations. Comme d'autres réponses l'ont souligné, il vaut mieux dire clairement ce que vous voulez dire,
Même dans ces environnements, cependant, vous pouvez vous retrouver à résoudre une question d'entrevue où vous êtes censé connaître ceci ou une autre équivalence. Les connaître n'est pas mauvais et un bon ingénieur serait conscient de l'effet arithmétique du décalage binaire. Notez que je n'ai pas dit que cela fait un bon ingénieur, mais qu'un bon ingénieur le saurait, à mon avis. En particulier, vous pouvez toujours trouver un gestionnaire, généralement vers la fin de votre boucle d'entrevue, qui vous sourira largement en prévision du plaisir de vous révéler cette "astuce" d'ingénierie intelligente dans une question de codage et de prouver qu'il / elle , aussi, était ou est l'un des ingénieurs avertis et pas "juste" un gestionnaire. Dans ces situations, essayez simplement d'avoir l'air impressionné et de le remercier pour l'interview éclairante.
Pourquoi n'avez-vous pas vu de différence de vitesse en C? La réponse la plus probable est que les deux ont abouti au même code d'assembly:
Peut à la fois compiler en
Sur GCC sans optimisations, c'est-à-dire en utilisant le drapeau "-O0", vous pouvez obtenir ceci:
Comme vous pouvez le voir, passer "-O0" à GCC ne signifie pas qu'il ne sera pas quelque peu intelligent sur le type de code qu'il produit. En particulier, notez que même dans ce cas, le compilateur a évité l'utilisation d'une instruction multiply. Vous pouvez répéter la même expérience avec des décalages par d'autres nombres et même des multiplications par des nombres qui ne sont pas des puissances de deux. Les chances sont que sur votre plate-forme, vous verrez une combinaison de changements et d'ajouts, mais pas de multiplications. Cela semble être une sorte de coïncidence pour le compilateur d'éviter apparemment d'utiliser des multiplications dans tous ces cas si les multiplications et les décalages avaient vraiment le même coût, n'est-ce pas? Mais je ne veux pas fournir de supposition pour preuve, alors continuons.
Vous pouvez relancer votre test avec le code ci-dessus et voir si vous remarquez une différence de vitesse maintenant. Même alors, vous ne testez pas shift versus multiply, comme vous pouvez le voir par l'absence de multiplication, mais le code qui a été généré avec un certain ensemble de drapeaux par GCC pour les opérations C de shift et multiplier dans une instance particulière . Ainsi, dans un autre test, vous pouvez modifier le code d'assemblage à la main et utiliser à la place une instruction "imul" dans le code de la méthode "multiplier".
Si vous vouliez vaincre certaines de ces astuces du compilateur, vous pourriez définir une méthode de décalage et de multiplication plus générale et vous obtiendrez quelque chose comme ceci:
Ce qui peut donner le code d'assemblage suivant:
Ici, nous avons enfin, même au niveau d'optimisation le plus élevé de GCC 4.9, l'expression dans les instructions de montage que vous attendiez lors de votre premier test. Je pense que cela peut être en soi une leçon importante dans l'optimisation des performances. Nous pouvons voir la différence que cela a fait de substituer des variables aux constantes concrètes dans notre code, en termes d'intelligence que le compilateur est capable d'appliquer. Les micro-optimisations comme la substitution shift-multiply sont des optimisations de très bas niveau qu'un compilateur peut généralement facilement faire par lui-même. D'autres optimisations qui ont beaucoup plus d'impact sur les performances nécessitent une compréhension de l' intention du codequi n'est souvent pas accessible par le compilateur ou ne peut être deviné que par une heuristique. C'est là que vous intervenez en tant qu'ingénieur logiciel et cela n'implique certainement pas de remplacer les multiplications par des changements. Cela implique des facteurs tels que l'évitement d'un appel redondant vers un service qui produit des E / S et peut bloquer un processus. Si vous allez sur votre disque dur ou, Dieu nous en préserve, dans une base de données distante pour des données supplémentaires que vous auriez pu tirer de ce que vous avez déjà en mémoire, le temps que vous passez à attendre l'emporte sur l'exécution d'un million d'instructions. Maintenant, je pense que nous nous sommes éloignés un peu de votre question d'origine, mais je pense que le signaler à un intervenant, surtout si nous supposons que quelqu'un qui commence à peine à comprendre la traduction et l'exécution du code,
Alors, lequel sera le plus rapide? Je pense que c'est une bonne approche que vous avez choisie pour tester la différence de performances. En général, il est facile d'être surpris par les performances d'exécution de certains changements de code. Il existe de nombreuses techniques utilisées par les processeurs modernes et l'interaction entre les logiciels peut également être complexe. Même si vous devez obtenir des résultats de performance bénéfiques pour un certain changement dans une situation, je pense qu'il est dangereux de conclure que ce type de changement produira toujours des avantages de performance. Je pense qu'il est dangereux d'exécuter de tels tests une fois, dites "D'accord, maintenant je sais lequel est le plus rapide!" puis appliquez sans discernement cette même optimisation au code de production sans répéter vos mesures.
Et si le changement est plus rapide que la multiplication? Il y a certainement des raisons pour lesquelles cela serait vrai. GCC, comme vous pouvez le voir ci-dessus, semble penser (même sans optimisation) qu'éviter la multiplication directe en faveur d'autres instructions est une bonne idée. Le Manuel de référence de l'optimisation des architectures Intel 64 et IA-32 vous donnera une idée du coût relatif des instructions CPU. Une autre ressource, plus axée sur la latence et le débit des instructions, est http://www.agner.org/optimize/instruction_tables.pdf. Notez qu'ils ne sont pas un bon prédicteur de l'exécution absolue, mais des performances des instructions les unes par rapport aux autres. Dans une boucle étroite, comme votre test est en train de simuler, la métrique de "débit" devrait être la plus pertinente. Il s'agit du nombre de cycles pour lesquels une unité d'exécution sera généralement attachée lors de l'exécution d'une instruction donnée.
Et si le changement n'est PAS plus rapide que la multiplication? Comme je l'ai dit ci-dessus, les architectures modernes peuvent être assez complexes et des éléments tels que la prédiction de branche, la mise en cache, le pipelining et les unités d'exécution parallèle peuvent rendre difficile la prévision des performances relatives de deux morceaux de code logiquement équivalents à certains moments. Je tiens vraiment à le souligner, car c'est là que je ne suis pas satisfait de la plupart des réponses à des questions comme celles-ci et du camp de personnes qui disent carrément qu'il n'est tout simplement pas vrai (plus) que le changement est plus rapide que la multiplication.
Non, autant que je sache, nous n'avons pas inventé de sauce d'ingénierie secrète dans les années 1970 ou chaque fois pour annuler soudainement la différence de coût d'une unité de multiplication et d'un peu de levier de vitesses. Une multiplication générale, en termes de portes logiques, et certainement en termes d'opérations logiques, est toujours plus complexe qu'un changement avec un barillet dans de nombreux scénarios, sur de nombreuses architectures. La façon dont cela se traduit par une exécution globale sur un ordinateur de bureau peut être un peu opaque. Je ne sais pas exactement comment ils sont implémentés dans des processeurs spécifiques, mais voici une explication d'une multiplication: la multiplication entière est-elle vraiment la même vitesse que l'ajout sur un processeur moderne
Alors voici une explication d'un baril shifter . Les documents auxquels j'ai fait référence dans le paragraphe précédent donnent un autre point de vue sur le coût relatif des opérations, par procuration des instructions CPU. Les ingénieurs d'Intel semblent souvent avoir des questions similaires: les cycles d'horloge des forums de la zone de développement Intel pour la multiplication entière et l'ajout dans le processeur Core 2 Duo
Oui, dans la plupart des scénarios réels, et presque certainement en JavaScript, tenter d'exploiter cette équivalence pour la performance est probablement une entreprise futile. Cependant, même si nous avons forcé l'utilisation d'instructions de multiplication et que nous n'avons constaté aucune différence dans l'exécution, cela est davantage dû à la nature de la métrique de coût que nous avons utilisée, pour être précis, et non pas parce qu'il n'y a pas de différence de coût. L'exécution de bout en bout est une métrique et si c'est la seule qui nous intéresse, tout va bien. Mais cela ne signifie pas que toutes les différences de coûts entre la multiplication et le déplacement ont tout simplement disparu. Et je pense que ce n'est certainement pas une bonne idée de transmettre cette idée à un intervenant, par implication ou autrement, qui commence évidemment à se faire une idée des facteurs impliqués dans l'exécution et le coût du code moderne. L'ingénierie est toujours une question de compromis. Une enquête et une explication sur les compromis que les processeurs modernes ont faits pour montrer le temps d'exécution que nous, en tant qu'utilisateurs, finissons par voir, peuvent donner une réponse plus différenciée. Et je pense qu'une réponse plus différenciée que "ce n'est tout simplement plus vrai" est justifiée si nous voulons voir moins d'ingénieurs vérifier la lisibilité du code micro-optimisé, car il faut une compréhension plus générale de la nature de ces "optimisations" pour repérer ses incarnations diverses et diverses que de simplement se référer à certains cas spécifiques comme obsolètes.
la source
Ce que vous voyez, c'est l'effet de l'optimiseur.
Le travail des optimiseurs est de rendre le code compilé résultant soit plus petit, soit plus rapide (mais rarement les deux en même temps ... mais comme beaucoup de choses ... IL DÉPEND DE ce qu'est le code).
Dans PRINCIPLE, tout appel à une bibliothèque de multiplication ou, souvent, même l'utilisation d'un multiplicateur matériel sera plus lent que de simplement effectuer un décalage au niveau du bit.
Donc ... si le compilateur naïf a généré un appel à une bibliothèque pour l'opération * 2, alors bien sûr, il s'exécuterait plus lentement qu'un décalage au niveau du bit *.
Cependant, les optimiseurs sont là pour détecter les modèles et comprendre comment rendre le code plus petit / plus rapide / peu importe. Et ce que vous avez vu, c'est que le compilateur détecte que * 2 est identique à un décalage.
Juste comme une question d'intérêt, je regardais aujourd'hui l'assembleur généré pour certaines opérations comme * 5 ... pas vraiment, mais d'autres choses, et en cours de route, je remarque que le compilateur avait transformé * 5 en:
L'optimiseur de mon compilateur était donc suffisamment intelligent (au moins pour certaines petites constantes) pour générer des décalages en ligne et des ajouts au lieu d'appels à une bibliothèque de multiplication à usage général.
L'art des optimiseurs de compilateur est un sujet à part entière, rempli de magie, et vraiment bien compris par environ 6 personnes sur toute la planète :)
la source
Essayez de le synchroniser avec:
Le compilateur doit reconnaître que la valeur de
test
est inchangée après chaque itération de la boucle, et la valeur finale detest
est inutilisée, et éliminer la boucle entièrement.la source
La multiplication est une combinaison de changements et d'ajouts.
Dans le cas que vous avez mentionné, je ne pense pas qu'il importe que le compilateur l'optimise ou non - "multiplier
x
par deux" peut être implémenté comme suit:x
un endroit vers la gauche.x
àx
.Ce sont chacune des opérations atomiques de base; l'un n'est pas plus rapide que l'autre.
Changez-le en "multipliez
x
par quatre", (ou n'importe quel autre2^k, k>1
) et c'est un peu différent:x
deux endroits vers la gauche.x
àx
et appelez-ley
, ajoutezy
ày
.Sur une architecture de base, il est simple de voir que le changement est plus efficace - en prenant une contre deux opérations, car nous ne pouvons pas ajouter
y
jusqu'ày
ce que nous sachions ce quiy
est.Essayez ce dernier (ou tout autre
2^k, k>1
), avec les options appropriées pour éviter que votre optimisation ne soit la même chose dans la mise en œuvre. Vous devriez trouver que le changement est plus rapide, prenantO(1)
par rapport à l'addition répétée dansO(k)
.Évidemment, lorsque le multiplicande n'est pas une puissance de deux, une combinaison de décalages et d'additions (une où le nombre de chacun n'est pas nul) est nécessaire.
la source
La multiplication des valeurs signées ou non signées par des puissances de deux équivaut à un décalage vers la gauche, et la plupart des compilateurs effectueront la substitution. La division des valeurs non signées ou des valeurs signées que le compilateur peut prouver n'est jamais négative , équivaut à un décalage vers la droite, et la plupart des compilateurs effectueront cette substitution (bien que certains ne soient pas assez sophistiqués pour prouver que les valeurs signées ne peuvent pas être négatives) .
Il convient toutefois de noter que la division des valeurs signées potentiellement négatives n'est pas équivalente à un décalage à droite. Une expression comme
(x+8)>>4
n'est pas équivalente à(x+8)/16
. Le premier, dans 99% des compilateurs, mappera les valeurs de -24 à -9 à -1, -8 à +7 à 0 et +8 à +23 à 1 [arrondir les nombres presque symétriquement autour de zéro]. Ce dernier cartographiera -39 à -24 à -1, -23 à +7 à 0 et +8 à +23 à +1 [largement asymétrique, et probablement pas ce qui était prévu]. Notez que même lorsque les valeurs ne devraient pas être négatives, l'utilisation de>>4
produira probablement du code plus rapide que/16
si le compilateur ne peut prouver que les valeurs ne peuvent pas être négatives.la source
Quelques informations supplémentaires que je viens de consulter.
Sur x86_64, l'opcode MUL a une latence de 10 cycles et un débit de 1/2 cycle. MOV, ADD et SHL ont une latence de 1 cycle, avec un débit de 2,5, 2,5 et 1,7 cycle.
Une multiplication par 15 nécessiterait au minimum 3 opérations SHL et 3 opérations ADD et probablement quelques MOV.
https://gmplib.org/~tege/x86-timing.pdf
la source
Votre méthodologie est défectueuse. Votre incrément de boucle et votre vérification d'état prennent beaucoup de temps.
base
).s1
).s2
)Si tout se passe correctement, cela
base-s2
devrait être 10 fois plus quebase-s1
. Sinon, quelque chose d'autre entre en jeu ici.Maintenant, j'ai essayé cela moi-même et j'ai pensé que si les boucles causaient un problème, pourquoi ne pas les supprimer complètement. J'ai donc continué et j'ai fait ceci:
Et là vous avez votre résultat
1 million d'opérations de quart en moins de 1 millisecondes? .
J'ai fait la même chose pour la multiplication par 64 et j'ai obtenu le même résultat. Donc, probablement le compilateur ignore complètement l'opération car d'autres ont mentionné que la valeur de test n'est jamais modifiée.
la source