Est la multiplication et la division en utilisant les opérateurs de décalage c vraiment plus rapide ?

Question

Multiplication et division peuvent être réalisés à l’aide des opérateurs de bits, par exemple

et ainsi de suite.

Est-il réellement plus rapide d’utiliser say à multiplier par 10 que d’utiliser directement ? Y a-t-il n’importe quelle sorte d’entrée qui ne peut être multipliée ou divisée de cette façon ?

Answer 1

Réponse courte: Non probable.

Réponse longue: Votre compilateur a un optimiseur qui sait se multiplient aussi vite que votre cible de l'architecture du processeur est capable. Votre meilleur pari est de dire au compilateur de votre intention clairement (c'est à dire i*2 plutôt que i << 1) et le laisser décider de ce que la manière la plus rapide de montage/code machine de la séquence. Il est même possible que le processeur lui-même a mis en œuvre les multiplier instruction comme une séquence de changements et ajoute dans le microcode.

Ligne de fond-ne pas passer beaucoup de temps à se préoccuper de cela. Si vous voulez dire à la maj, maj. Si vous voulez dire à se multiplier, à se multiplier. Faire ce qui est sémantiquement plus clair--vos collègues vous en seront reconnaissantes. Ou, plus probablement, vous maudissent, plus tard, si vous faites le contraire.

Answer 2

Juste un béton de point de mesure: il y a plusieurs années, j'ai comparé les deux versions de mon algorithme de hachage:

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = 127 * h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

et

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = (h << 7) - h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

Sur chaque machine je comparés sur, le premier a été au moins aussi vite que la deuxième. Curieusement, il est parfois plus rapide (par exemple sur un Sun Sparc). Lorsque le matériel ne prend pas en charge rapide de multiplication (et la plupart n'avait pas à l'époque), le compilateur serait de convertir la multiplication dans les combinaisons appropriées de changements et add/sub. Et parce qu'il savait l'objectif final, il peut parfois le faire en moins d'instructions que lorsque vous avez explicitement écrit, les modifications et l'ajout/subs.

Remarque que c'était quelque chose comme il y a 15 ans. Heureusement, les compilateurs ont ne cesse de s'améliorer depuis, alors vous pouvez très bien compter sur l' compilateur de faire la bonne chose, probablement mieux que vous pourrait. (Aussi, la raison pour laquelle le code a l'air tellement C new'ish est parce qu'il a plus de 15 ans. J'avais évidemment std::string et itérateurs d'aujourd'hui).

Answer 3

En plus de toutes les autres bonnes réponses ici, permettez-moi de souligner une autre raison de ne pas utiliser la touche maj enfoncée lorsque vous signifie diviser ou multiplier. Je n'ai jamais vu une fois à quelqu'un de présenter un bug par l'oubli de la priorité relative de multiplication et d'addition. J'ai vu les bugs introduits lors de l'entretien les programmeurs ont oublié que le "multiplier" via une maj est logiquement une multiplication, mais pas du point de vue syntaxique de la même priorité que la multiplication. x * 2 + z et x << 1 + z sont très différents!

Si vous travaillez sur les numéros ensuite utiliser des opérateurs arithmétiques comme + - * / %. Si vous travaillez sur des tableaux de bits, utilisez peu tourner les opérateurs comme & ^ | >> . Ne pas les mélanger; une expression qui est à la fois peu tripoter et de l'arithmétique est un bug en attente de se produire.

Answer 4

Cela dépend du processeur et le compilateur. Certains compilateurs déjà optimiser le code de cette façon, d’autres pas. Vous devez donc vérifier chaque fois que votre code doit être optimisé de cette façon.

Sauf si vous avez désespérément besoin optimiser, je ne serait pas brouiller mon code source juste pour enregistrer un assembly cycle instruction ou processeur.

Answer 5

Est-il réellement plus rapide à utiliser-dire (i<<3)+(i<<1) à multiplier par 10 que l'utilisation de i*10 directement?

Il peut ou peut ne pas être sur votre ordinateur - si vous vous souciez, la mesure dans votre usage du monde réel.

Une étude de cas - à partir de 486 core i7

L'analyse comparative est très difficile de le faire de façon significative, mais nous pouvons regarder un peu les faits. À partir de http://www.penguin.cz/~literakl/intel/s.html#SAL et http://www.penguin.cz/~literakl/intel/je.html#IMUL , nous avons une idée de x86 cycles d'horloge nécessaires pour le décalage et la multiplication. Dis nous en tenir à "486" (le plus récent), 32 bits des registres et immédiates, IMUL prend 13-42 cycles et IDIV 44. Chaque SAL prend 2, et en ajoutant 1, de sorte que même avec un peu de ceux-ensemble décalage superficiellement ressemble à un gagnant.

Ces jours-ci, avec le core i7:

(à partir de http://software.intel.com/en-us/forums/showthread.php?t=61481)

La latence est de 1 cycle pour un entier plus et 3 cycles pour un nombre entier de multiplication. Vous pouvez trouver des latences et des thoughput à l'Annexe C de la "Intel® 64 et IA-32 Optimisation des Architectures Manuel", qui est situé sur http://www.intel.com/products/processor/manuals/.

(d'une certaine Intel blurb)

À l'aide de l'ESS, le Core i7 peut émission simultanée d'ajouter et multiplier les instructions, résultant en un taux maximal de 8 opérations à virgule flottante (le FLOP) par cycle d'horloge

Cela vous donne une idée de la façon dont beaucoup choses ont. L'optimisation de trivia - comme le décalage de bits contre * - qui a été pris au sérieux, même dans les années 90 est juste aujourd'hui obsolète. De décalage de bits est encore plus rapide, mais pour les non-puissance de deux mul/div par le temps de vous faire tous vos déplacements et ajouter les résultats, il est encore plus lent. Alors, plus d'instructions signifie plus de défauts de cache, plus les problèmes potentiels dans le pipelining, plus d'utilisation de ces registres peut signifier plus de sauvegarde et restauration du contenu du registre à partir de la pile... ça devient vite trop compliqué de quantifier tous les impacts définitivement, mais ils sont essentiellement négatifs.

la fonctionnalité dans le code source vs la mise en œuvre

Plus généralement, votre question est balisé le C et le C++. En tant que 3e génération langues, s'ils sont spécifiquement conçus pour cacher les détails de la sous-jacentes du PROCESSEUR à jeu d'instructions. Pour satisfaire leur langue les Normes, ils doivent soutenir la multiplication et le déplacement des opérations (et beaucoup d'autres) , même si le matériel sous-jacent n'est pas. Dans de tels cas, ils doivent synthétiser le résultat requis à l'aide de beaucoup d'autres instructions. De même, ils doivent fournir le logiciel de soutien pour les opérations à virgule flottante si le CPU n'en a pas et il n'y a pas de FPU. Les Processeurs modernes supportent tous * et <<, de sorte que cela peut sembler absurde théoriques et historiques, mais l'importance c'est que la liberté de choisir la mise en œuvre va dans les deux sens: même si le CPU a une instruction qui met en œuvre l'opération demandée dans le code source dans le cas général, le compilateur est libre de choisir quelque chose d'autre qu'il préfère parce que c'est mieux pour le spécifique cas, le compilateur est confronté.

Exemples (avec un hypothétique langage d'assemblage)

source           literal approach         optimised approach
#define N 0
int x;           .word x                xor registerA, registerA
x *= N;          move x -> registerA
                 move x -> registerB
                 A = B * immediate(0)
                 store registerA -> x
  ...............do something more with x...............

Instructions comme ou-exclusif (xor) n'ont aucun rapport avec le code source, mais xor-ing quoi que ce soit avec lui-même efface tous les bits, de sorte qu'il peut être utilisé pour définir quelque chose à 0. Le code Source qui implique des adresses de mémoire ne peut aboutir à être utilisé.

Ce genre de hacks ont été utilisés aussi longtemps que les ordinateurs ont été autour. Dans les premiers jours de 3GLs, pour sécuriser le développeur de l'absorption de la sortie du compilateur a dû satisfaire de l'existant hardcore de la main-optimisation de la langue de l'assembly dev. de la communauté que le code produit n'est pas plus lent, plus détaillé ou sinon pire. Les compilateurs ont rapidement adopté beaucoup d'optimisations - ils devenu un meilleur centralisée magasin de il de toute assemblée de la langue programmeur pourrait éventuellement être, mais il y a toujours la chance qu'ils manquent un précis d'optimisation qui se trouve être essentiel dans un cas particulier - les humains peuvent, parfois, de noix et de tâtonner pour quelque chose de mieux alors que les compilateurs il suffit de faire comme ils ont dit jusqu'à ce que quelqu'un se nourrit que de l'expérience retour.

Donc, même si le décalage et l'ajout est encore plus rapide sur certains matériels, alors le compilateur de l'écrivain susceptibles d'avoir travaillé exactement quand il est à la fois bénéfiques et sans danger.

La maintenabilité

Si vos modifications sur le matériel, vous pouvez recompiler et il va chercher à le PROCESSEUR cible et de faire un autre choix, alors que vous avez peu de chances de jamais vouloir revoir votre "optimisations" ou à la liste qui compilation environnements doivent utiliser la multiplication et de la qui devrait passer. Pensez à tous les non-puissance de deux bits décalés "optimisations" écrite de 10 ans qui sont maintenant en train de ralentir le code qu'ils sont en mesure de l'exécution sur les processeurs modernes...!

Heureusement, de bons compilateurs comme GCC peut généralement remplacer une série de bitshifts et de l'arithmétique avec un direct de multiplication lorsque aucune optimisation est activée (c - ...main(...) { return (argc << 4) + (argc << 2) + argc; } -> imull $21, 8(%ebp), %eax)- une recompilation peut aider, même sans en fixer le code, mais ce n'est pas garanti.

Étrange bitshifting d'application du code de la multiplication ou de la division est beaucoup moins expressif de ce que vous étiez sur le plan conceptuel essaie de l'atteindre, de sorte que les autres développeurs seront confus par ce, et un confus programmeur est plus susceptible d'introduire des bogues ou de supprimer quelque chose d'essentiel dans un effort pour restaurer semblant de santé mentale. Si vous ne le faites non évidente des choses quand ils sont vraiment, de façon tangible, positif, et les documenter (mais ne faites pas de document d'autres trucs qui sont de toute façon intuitive), tout le monde sera plus heureux.

Solutions générales rapport à des solutions partielles

Si vous avez quelques connaissances supplémentaires, tels que votre int ne sera véritablement en stockant les valeurs x, y et z, alors vous pourriez être en mesure de travailler des instructions de travail pour ces valeurs et vous obtenez votre résultat plus rapidement que lorsque le compilateur n'a pas cette idée et a besoin d'une mise en œuvre qui fonctionne pour tous int valeurs. Par exemple, pensez à votre question:

La Multiplication et la division peut être réalisé en utilisant des bits les opérateurs...

Vous illustrer la multiplication, mais combien de division?

int x;
x >> 1;   // divide by 2?

Selon la Norme C++ 5.8:

-3 - La valeur de E1 >> E2 E1 décalés vers la droite E2 positions de bits. Si E1 est un type non signé ou si E1 a un type signé et un non négatif, la valeur du résultat est la partie entière du quotient de E1, divisée par la quantité 2 élevé à la puissance de l'E2. Si E1 a signé un type et une valeur négative, la valeur résultante de la mise en œuvre est définie.

Donc, votre de décalage de bits a une implémentation résultat défini lors de l' x est négatif: il ne peut pas travailler de la même façon sur des machines différentes. Mais, / fonctionne beaucoup plus prévisible. (Il peut ne pas être parfaitement cohérent, car les différentes machines peuvent avoir différentes représentations des nombres négatifs, et donc les différentes gammes, même quand il y a le même nombre de bits qui composent la représentation.)

Vous pouvez dire "je n'aime pas... c' int est le stockage de l'âge de l'employé, il ne peut jamais être négatif". Si vous avez ce genre de perspicacité particulière, alors oui, votre >> sûr d'optimisation peut être passé par le compilateur, sauf si vous explicitement le faire dans votre code. Mais, c'est risqué et rarement utile car la plupart du temps vous n'aurez pas ce genre d'information, et d'autres programmeurs travaillant sur le même code ne saurez pas que vous avez pari de la maison à certaines des attentes des données vous serez manipulation... ce qui semble totalement sûr pour le changement pourrait se retourner contre à cause de votre "optimisation".

Est-il une sorte d'entrée qui ne peut pas être multiplié ou divisé de cette manière?

Oui... comme mentionné ci-dessus, les nombres négatifs ont définie par l'implémentation du comportement lors de l' "divisé" par décalage de bits.