Le décalage des bits est-il plus rapide que la multiplication et la division en Java ? .NET ?

Question

Le décalage des bits à gauche et à droite est apparemment plus rapide que les opérations de multiplication et de division sur la plupart (tous ?) des CPU s'il se trouve que vous utilisez une puissance de 2. Cependant, il peut réduire la clarté du code pour certains lecteurs et certains algorithmes. Le décalage des bits est-il vraiment nécessaire pour les performances, ou puis-je espérer que le compilateur/VM remarque le cas et l'optimise (en particulier, lorsque la puissance de 2 est un littéral) ? Je suis principalement intéressé par le comportement de Java et de .NET, mais je serais heureux de recevoir des informations sur les implémentations d'autres langages.

Answer 1

La plupart des compilateurs actuels ne se contentent pas de convertir la multiplication ou la division par une puissance de deux en opérations de décalage. Souvent, un multiplicateur ou un diviseur peut être décomposé en une série de décalages et d'additions, et si cette série d'opérations est plus rapide que le multiplicateur ou le diviseur, le compilateur l'utilisera.

Pour la division par une constante, le compilateur peut souvent convertir l'opération en une multiplication par un "nombre magique" suivi d'un décalage. Cela peut représenter un gain de temps considérable, car la multiplication est souvent beaucoup plus rapide qu'une opération de division.

Le livre d'Henry Warren, Hacker's Delight, contient une mine d'informations sur ce sujet, qui est également très bien couvert sur le site web d'accompagnement :

• http://www.hackersdelight.org/

Voir également une discussion (avec un lien ou deux) ici :

• http://hexblog.com/2005/11/do_you_know_the_division_opera.html

Quoi qu'il en soit, tout cela revient à permettre au compilateur de s'occuper des détails fastidieux des micro-optimisations. Cela fait des années que l'on n'a pas fait ses propres modifications sans tenir compte du compilateur.

Answer 2

Presque tout environnement digne de ce nom optimisera cette tâche pour vous. Et s'il ne le fait pas, vous avez d'autres chats à fouetter. Sérieusement, ne perdez pas une seconde de plus à y penser. Vous saurez quand vous aurez des problèmes de performance. Et après avoir lancé un profileur, vous saurez ce qui en est la cause, et il devrait être assez clair comment le corriger.

Vous n'entendrez jamais quelqu'un dire "mon application était trop lente, puis j'ai commencé à remplacer au hasard". x * 2 avec x << 1 et tout était réparé !" Les problèmes de performance sont généralement résolus en trouvant un moyen de faire un ordre de grandeur de moins de travail, et non en trouvant un moyen de faire le même travail 1% plus vite.

Answer 3

Les humains ont tort dans ces cas-là.

99% quand ils essaient de deviner un compilateur moderne (et tous les compilateurs futurs).
99,9% quand ils essaient de deviner les JIT modernes (et tous les futurs) en même temps.
99,999 % quand ils essaient de deviner les optimisations modernes (et futures) des processeurs.

Programmez d'une manière qui décrit précisément ce que vous voulez accomplir, et non comment le faire. Les futures versions du JIT, de la VM, du compilateur et du CPU peuvent toutes être améliorées et optimisées de manière indépendante. Si vous spécifiez quelque chose d'aussi minuscule et spécifique, vous perdez le bénéfice de toutes les optimisations futures.

Answer 4

Vous pouvez presque certainement compter sur l'optimisation de la multiplication en puissance de deux pour une opération de décalage. C'est l'une des premières optimisations que les étudiants en construction de compilateurs apprendront :)

Cependant, je ne pense pas qu'il y ait de garantie à cet égard. Votre code source devrait refléter votre intention plutôt que d'essayer de dire à l'optimiseur ce qu'il doit faire. Si vous voulez augmenter une quantité, utilisez la multiplication. Si vous déplacez un champ de bits d'un endroit à un autre (pensez à la manipulation des couleurs RVB), utilisez une opération de décalage. Dans tous les cas, votre code source reflétera ce que vous faites réellement.

Answer 5

Notez que le décalage vers le bas et la division donneront (en Java, certainement) des résultats différents pour les nombres négatifs et impairs.

int a = -7;
System.out.println("Shift: "+(a >> 1));
System.out.println("Div:   "+(a / 2));

Imprimés :

Shift: -4
Div:   -3

Comme Java n'a pas de nombres non signés, il n'est pas vraiment possible pour un compilateur Java d'optimiser cela.