Lorsque je teste la différence de temps entre le décalage et la multiplication en C, il n'y a pas de différence. Pourquoi?

28

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?

NicholasFolk
la source
47
Celui qui vous a enseigné que c'était clairement une erreur. Cette croyance n'a pas été vraie depuis les années 1970, pour les compilateurs généralement utilisés sur les architectures généralement utilisées. Bon pour vous d'avoir testé cette affirmation. J'ai entendu cette affirmation absurde concernant JavaScript pour l'amour du ciel.
Eric Lippert
21
La meilleure façon de répondre à des questions comme celles-ci est de regarder le code assembleur produit par le compilateur. Les compilateurs ont généralement la possibilité de produire une copie du langage d'assemblage qu'ils génèrent. Pour les compilateurs GNU GCC, il s'agit de '-S'.
Charles E. Grant
8
Il faut souligner qu'après avoir regardé ceci avec gcc -S, le code de test *= 2est en fait compilé en shll $1, %eax Lorsqu'il est appelé avec gcc -O3 -Sil 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
6
"On m'a appris que le déplacement en binaire est beaucoup plus efficace que la multiplication par 2 ^ k"; on nous apprend beaucoup de choses qui se révèlent fausses (ou du moins obsolètes). Un compilateur intelligent utilisera la même opération de décalage pour les deux.
John Bode
9
Toujours, vérifiez toujours le code d'assemblage généré lorsque vous travaillez sur ce type d'optimisation, pour être sûr de mesurer ce que vous pensez mesurer. Un grand nombre de questions «pourquoi est-ce que je vois ces temps» sur SO finissent par se résumer au compilateur, éliminant complètement les opérations parce que les résultats ne sont pas utilisés.
Russell Borogove du

Réponses:

44

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.

Thirler
la source
20
Utilisez toujours l'opération qui est sémantiquement correcte. Si vous manipulez des masques de bits ou positionnez de petits entiers dans des entiers plus grands, le décalage est l'opération appropriée.
ddyer
2
Serait-il jamais (pratiquement parlant) nécessaire d'optimiser une multiplication vers un opérateur de quart dans une application logicielle de haut niveau? Il semble, puisque le compilateur optimise déjà, que le seul moment où il est utile d'avoir cette connaissance est lors de la programmation à un niveau très bas (au moins, en dessous du compilateur).
NicholasFolk
11
@NicholasFolk nope. Faites ce qui est le plus simple à comprendre. Si vous écriviez directement un assemblage, cela peut être utile ... ou si vous écriviez un compilateur d'optimisation, cela pourrait encore être utile. Mais en dehors de ces deux cas, c'est une astuce qui obscurcit ce que vous faites et fait que le prochain programmeur (qui est un meurtre à la hache qui sait où vous vivez ) maudit votre nom et songe à se lancer dans un hobby.
2
@NicholasFolk: Les optimisations à ce niveau sont presque toujours obscurcies ou rendues inutiles par l'architecture du processeur de toute façon. Peu importe si vous enregistrez 50 cycles lorsque vous récupérez les arguments de la mémoire et que vous les réécrivez en prend plus de 100? Les micro-optimisations comme celle-ci avaient un sens lorsque la mémoire fonctionnait à (ou près de) la vitesse du CPU, mais pas tellement aujourd'hui.
TMN
2
Parce que je suis fatigué de voir ces 10% de cette citation, et parce que ça cloue sur la tête ici: "Il ne fait aucun doute que le graal de l'efficacité conduit à des abus. Les programmeurs perdent énormément de temps à réfléchir ou à s'inquiéter sur la vitesse des parties non critiques de leurs programmes, et ces tentatives d'efficacité ont en fait un fort impact négatif lors du débogage et de la maintenance. Nous devons oublier les petites efficacités, disons environ 97% du temps: l'optimisation prématurée est la racine de tout mal ...
cHao
25

Le compilateur reconnaît les constantes et convertit les multiplications en décalages le cas échéant.

ddyer
la source
Le compilateur reconnaît les constantes qui sont des puissances de 2 .... et se convertit en décalages. Toutes les constantes ne peuvent pas être changées en équipes.
quick_now
4
@quickly_now: Ils peuvent être convertis en combinaisons de décalages et d'additions / soustractions.
Mehrdad
2
Un bogue d'optimiseur de compilateur classique consiste à convertir les divisions en décalages à droite, ce qui fonctionne pour les dividendes positifs mais est désactivé de 1 pour les négatifs.
ddyer
1
@quickly_now Je crois que le terme «le cas échéant» recouvre l'idée que certaines constantes ne peuvent pas être réécrites sous forme de changements.
Pharap
21

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.

a *= 320;               // Slower
a = (a<<7) + (a<<9);    // Faster

Mais si vous aviez plus de deux bits ...

a *= 324;                        // About same speed
a = (a<<2) + (a<<7) + (a<<9);    // About same speed

a *= 340;                                 // Faster
a = (a<<2) + (a<<4) + (a<<7) + (a<<9);    // Slower

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.

a  *= 2;   // Exactly the same speed
a <<= 1;   // Exactly the same speed

a  *= 4;   // Faster
a <<= 2;   // Slower

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.

a  *= 4;   // 
b  *= 4;   // 

a <<= 2;   // Both lines execute in a single cycle
b <<= 2;   // 
Rocketmagnet
la source
5
+1 "Que le décalage soit plus rapide que la multiplication dépend de l'architecture de votre CPU." Merci d'être entré dans l'histoire un peu et d'avoir montré que la plupart des mythes informatiques ont en fait une base logique.
Pharap
11

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 des testchoses. 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éfinir runs = 100000000, mais runsn'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, disons test += 1) sont assez faciles à comprendre pour l'optimiseur, et c'est le cas.

Enfin, vous supposez que cela test *= 2va ê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 -O3aide 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 le printf.

derobert
la source
1
Notez également que l'optimiseur peut (et va) optimiser les opérations sur les constantes (même dans une boucle) comme indiqué dans sqrt c # vs sqrt c ++ où l'optimiseur a pu remplacer une boucle sommant une valeur avec la somme réelle. Pour vaincre cette optimisation, vous devez utiliser quelque chose de déterminé au moment de l'exécution (comme un argument de ligne de commande).
@MichaelT Yep. C'est ce que je voulais dire par "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)."
derobert
Je comprends ce que vous dites, mais je ne pense pas que le compilateur supprime la boucle entière. Vous pouvez facilement tester cette théorie en augmentant simplement le nombre d'itérations. Vous verrez que l'augmentation des itérations rend le programme plus long. Si la boucle était entièrement supprimée, ce ne serait pas le cas.
DollarAkshay
@AkshayLAradhya Je ne peux pas dire ce que fait votre compilateur, mais j'ai de nouveau confirmé que 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).
derobert
8

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:

int shift(int i) { return i << 2; }
int multiply(int i) { return i * 2; }

Peut à la fois compiler en

shift(int):
    lea eax, [0+rdi*4]
    ret

Sur GCC sans optimisations, c'est-à-dire en utilisant le drapeau "-O0", vous pouvez obtenir ceci:

shift(int):
    push    rbp
    mov rbp, rsp
    mov DWORD PTR [rbp-4], edi
    mov eax, DWORD PTR [rbp-4]
    sal eax, 2
    pop rbp
    ret
multiply(int):
    push    rbp
    mov rbp, rsp
    mov DWORD PTR [rbp-4], edi
    mov eax, DWORD PTR [rbp-4]
    add eax, eax
    pop rbp
    ret

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:

int shift(int i, int j) { return i << j; }
int multiply(int i, int j) { return i * j; }

Ce qui peut donner le code d'assemblage suivant:

shift(int, int):
    mov eax, edi
    mov ecx, esi
    sal eax, cl
    ret
multiply(int, int):
    mov eax, edi
    imul    eax, esi
    ret

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.

user2880576
la source
6

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:

  • décalage
  • décalage
  • ajouter le numéro d'origine

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 :)

vite_maintenant
la source
3

Essayez de le synchroniser avec:

for (runs = 0; runs < 100000000; runs++) {
      ;
}

Le compilateur doit reconnaître que la valeur de testest inchangée après chaque itération de la boucle, et la valeur finale de testest inutilisée, et éliminer la boucle entièrement.

Russell Borogove
la source
2

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 xpar deux" peut être implémenté comme suit:

  • Déplacez les bits d' xun endroit vers la gauche.
  • Ajouter 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 xpar quatre", (ou n'importe quel autre 2^k, k>1) et c'est un peu différent:

  • Décaler des bits de xdeux endroits vers la gauche.
  • Ajoutez xà xet appelez-le y, ajoutez yà 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 yjusqu'à yce que nous sachions ce qui yest.

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, prenant O(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.

OJFord
la source
1
Qu'est-ce qu'une "opération atomique de base"? Ne pourrait-on pas affirmer que dans un décalage, l'opération peut être appliquée à chaque bit en parallèle, alors qu'en plus les bits les plus à gauche dépendent des autres bits?
Bergi
2
@Bergi: Je suppose qu'il veut dire que les deux shift et add sont des instructions sur une seule machine. Vous devriez consulter la documentation du jeu d'instructions pour voir le nombre de cycles pour chacun, mais oui, un ajout est souvent une opération à plusieurs cycles alors qu'un changement est généralement effectué en un seul cycle.
TMN
Oui, cela pourrait être le cas, mais la multiplication est également une instruction machine unique (bien que cela puisse nécessiter plus de cycles)
Bergi
@Bergi, cela dépend aussi de l'arc. À quel arc pensez-vous qui se déplace en moins de cycles que l'ajout 32 bits (ou x-bit selon le cas)?
OJFord
Je ne connais aucune architecture particulière, non (et mes cours d'ingénierie informatique se sont estompés), probablement les deux instructions prennent moins d'un cycle. Je pensais probablement en termes de microcode ou même de portes logiques, où un changement serait probablement moins cher.
Bergi
1

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)>>4n'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 >>4produira probablement du code plus rapide que /16si le compilateur ne peut prouver que les valeurs ne peuvent pas être négatives.

supercat
la source
0

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

Rich Remer
la source
0

Votre méthodologie est défectueuse. Votre incrément de boucle et votre vérification d'état prennent beaucoup de temps.

  • Essayez d'exécuter une boucle vide et mesurez le temps (appelez-le base).
  • Ajoutez maintenant 1 opération de décalage et mesurez le temps (appelez-le s1).
  • Ajoutez ensuite 10 opérations de décalage et mesurez le temps (appelez-le s2)

Si tout se passe correctement, cela base-s2devrait être 10 fois plus que base-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:

int main(){

    int test = 2;
    clock_t launch = clock();

    test << 6;
    test << 6;
    test << 6;
    test << 6;
    //.... 1 million times
    test << 6;

    clock_t done = clock();
    printf("Time taken : %d\n", done - launch);
    return 0;
}

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.

Résultat de l'opérateur Shiftwise

DollarAkshay
la source