Les compilateurs modernes optimisent-ils l’opération x * 2 à x << 1?

En réalité, VS2008 optimise cela en x + x:

 01391000 push ecx int x = 0; scanf("%d", &x); 01391001 lea eax,[esp] 01391004 push eax 01391005 push offset ssortingng "%d" (13920F4h) 0139100A mov dword ptr [esp+8],0 01391012 call dword ptr [__imp__scanf (13920A4h)] int y = x * 2; 01391018 mov ecx,dword ptr [esp+8] 0139101C lea edx,[ecx+ecx] 

Dans une construction x64, il est encore plus explicite et utilise:

  int y = x * 2; 000000013FB9101E mov edx,dword ptr [x] printf("%d", y); 000000013FB91022 lea rcx,[ssortingng "%d" (13FB921B0h)] 000000013FB91029 add edx,edx 

Ce sont les parameters d’optimisation sur «Maximiser la vitesse» (/ O2)

Cet article de Raymond Chen pourrait être intéressant:

Quand x / 2 est-il différent de x >> 1? : http://blogs.msdn.com/oldnewthing/archive/2005/05/27/422551.aspx

Citant Raymond:

Bien entendu, le compilateur est libre de reconnaître cela et de réécrire votre opération de multiplication ou de décalage. En fait, il est très probable que cela se produise, car x + x est plus facilement appariable qu’une multiplication ou un décalage. Votre quart de travail ou multiplication par deux sera probablement réécrit en quelque chose de plus proche d’une instruction add eax, eax.

[…]

Même si vous supposez que le décalage se remplit avec le bit de signe, le résultat du décalage et de la division sont différents si x est négatif.

(-1) / 2 0
(-1) >> 1 ≡ -1

[…]

La morale de l’histoire est d’écrire ce que vous voulez dire. Si vous voulez diviser par deux, écrivez “/ 2” et non “>> 1”.

Nous pouvons seulement supposer qu’il est sage de dire au compilateur ce que vous voulez, et non ce que vous voulez qu’il fasse: le compilateur est meilleur qu’un humain pour optimiser le code à petite échelle (merci à Daemin de lui avoir signalé ce point subtil): voulez une optimisation, utilisez un profileur et étudiez l’efficacité de vos algorithmes.

VS 2008 a optimisé le mien à x << 1.

  x = x * 2; 004013E7 mov eax,dword ptr [x] 004013EA shl eax,1 004013EC mov dword ptr [x],eax 

EDIT: Cela utilisait la configuration “Debug” par défaut du VS avec l’optimisation désactivée (/ Od). L’utilisation de l’un des commutateurs d’optimisation (/ O1, / O2 (VS “Retail”), ou / Ox) génère l’ajout du code que Rob a posté. Aussi, juste pour faire bonne mesure, j’ai vérifié que x = x << 1 est en effet traité de la même manière que x = x * 2 par le compilateur cl dans les deux / Od et / Ox. Donc, en résumé, la version 15.00.30729.01 de cl.exe pour x86 traite * 2 et << 1 identique et je m'attends à ce que presque tous les autres compilateurs récents fassent de même.

Pas si x est un float, ce ne sera pas le cas.

Oui. Ils optimisent également d’autres opérations similaires, telles que la multiplication par des non-puissances de deux pouvant être réécrites sous la forme de la sum de certains changements. Ils vont également optimiser les divisions par des puissances de 2 en décalages à droite, mais attention, lorsque vous travaillez avec des entiers signés, les deux opérations sont différentes! Le compilateur doit émettre des instructions supplémentaires pour s’assurer que les résultats sont les mêmes pour les nombres positifs et négatifs, mais cela rest plus rapide que de faire une division. De même, il optimise les modules par des puissances de 2.

La réponse est “si c’est plus rapide” (ou plus petit). Cela dépend fortement de l’architecture cible ainsi que du modèle d’utilisation du registre pour un compilateur donné. En général, la réponse est “oui, toujours” car il s’agit d’une optimisation de judas très simple à mettre en œuvre et constitue généralement une victoire décente.

Ce n’est que le début de ce que les optimiseurs peuvent faire. Pour voir ce que fait votre compilateur, recherchez le commutateur qui lui permet d’émettre une source d’assembleur. Pour les compilateurs Digital Mars, l’assembleur de sortie peut être examiné à l’aide de l’outil OBJ2ASM. Si vous voulez savoir comment votre compilateur fonctionne, il peut être très éclairant de regarder la sortie de l’assembleur.

Je suis sûr qu’ils font tous ce genre d’optimisations, mais je me demande si elles sont toujours pertinentes. Les processeurs plus anciens effectuaient la multiplication par décalage et addition, ce qui pouvait prendre plusieurs cycles. Les processeurs modernes, quant à eux, disposent d’un ensemble de mécanismes de changement de baril pouvant effectuer tous les changements et ajouts nécessaires simultanément en un seul cycle ou moins. Quelqu’un at-il réellement évalué si ces optimisations étaient réellement utiles?

Oui, il le feront.

À moins que quelque chose ne soit spécifié dans un standard de langues, vous n’obtiendrez jamais de réponse garantie à une telle question. En cas de doute, demandez à votre compilateur de cracher le code et de le vérifier. Ce sera le seul moyen de savoir vraiment.

@Ferruccio Barletta

C’est une bonne question. Je suis allé sur Google pour essayer de trouver la réponse.

Je ne pouvais pas trouver de réponses directes pour les processeurs Intel, mais cette page a une personne qui a essayé de chronométrer les choses. Il montre que les changements sont plus de deux fois plus rapides que les annonces et les multiplications. Les décalages de bits sont si simples (où une multiplication pourrait être un décalage et un ajout) que cela a du sens.

Alors, j’ai cherché sur Google un vieux guide d’optimisation de l’Athlon de 2002 qui répertorie les moyens les plus rapides de multiplier les nombres par des valeurs comsockets entre 2 et 32. Fait intéressant, cela dépend du nombre. Certains sont des annonces, certains changements. C’est à la page 122 .

Un guide pour l’ Athlon 64 indique la même chose (page 164 environ). Il dit que les multiplications sont des opérations de cycle de 3 (en 32 bits) ou de 4 (en 64 bits), les décalages étant de 1 et les ajouts de 2.

Il semble que cela rest utile comme optimisation.

En ignorant le nombre de cycles, ce type de méthode vous empêcherait de lier (éventuellement) les unités d’exécution de multiplication. Par conséquent, si vous effectuez de nombreuses multiplications dans une boucle étroite où certaines constantes utilisent et d’autres pas la salle de planification supplémentaire. utile.

Mais c’est de la spéculation.

Pourquoi pensez-vous que c’est une optimisation?

Pourquoi pas 2*x → x+x ? Ou peut-être que l’opération de multiplication est aussi rapide que l’opération de décalage à gauche (peut-être que si un seul bit est défini dans le multiplicande)? Si vous n’utilisez jamais le résultat, pourquoi ne pas le laisser de la sortie compilée? Si le compilateur a déjà chargé 2 dans un registre, peut-être que l’instruction de multiplication sera plus rapide, par exemple si nous devions charger le nombre d’équipes en premier. L’opération de décalage est peut-être plus importante et votre boucle interne ne rentre plus dans la mémoire tampon de prélecture de la CPU, ce qui pénalise donc les performances. Peut-être que le compilateur peut prouver que la seule fois où vous appelez votre fonction x aura la valeur 37 et que x*2 peut être remplacé par 74 ? Peut-être que vous faites 2*x où x est un nombre de boucles (très commun, bien que implicite, lorsque vous passez en boucle sur des objects de deux octets)? Ensuite, le compilateur peut changer la boucle de

  for(int x = 0; x < count; ++x) ...2*x... 

à l'équivalent (en laissant de côté les pathologies)

  int count2 = count * 2 for(int x = 0; x < count2; x += 2) ...x... 

qui remplace les multiplications de count par une seule multiplication, ou peut être en mesure de tirer parti de l'instruction lea qui combine la multiplication avec une lecture en mémoire.

Mon argument est le suivant : des millions de facteurs déterminent si le remplacement de x*2 par x<<1 génère un binary plus rapide. Un compilateur optimiseur essaiera de générer le code le plus rapide pour le programme qui lui est atsortingbué, pas pour une opération isolée. Par conséquent, les résultats d'optimisation pour le même code peuvent varier considérablement en fonction du code environnant et peuvent ne pas être sortingviaux du tout.

En règle générale, très peu de points de référence montrent de grandes différences entre les compilateurs. Il est donc raisonnable de penser que les compilateurs font du bon travail, car s’il restait des optimisations peu coûteuses, au moins un des compilateurs les implémenterait - et tous les autres suivraient dans leur prochaine version.

Cela dépend de votre compilateur. Visual C ++, par exemple, est notoirement pauvre en optimisation. Si vous modifiez votre message pour indiquer le compilateur que vous utilisez, il sera plus facile de répondre.