Est-ce que la multiplication et la division utilisant des opérateurs de postes en C sont réellement plus rapides?

juste un point de mesure concret: il y a de nombreuses années, j'ai versions de mon algorithme de hachage:

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

et

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

sur chaque machine sur laquelle je l'ai placé, la première était au moins aussi rapide que deuxième. Curieusement, il est parfois plus rapide (par exemple sur un Sun Sparc). Lorsque le matériel ne supportait pas la multiplication rapide (et la plupart ne l'ont pas fait à l'époque), le compilateur convertirait la multiplication dans le combinaisons appropriées de postes et add/sub. Et parce qu'il savait l'objectif final, il peut parfois le faire en moins d'instructions que quand vous avez écrit explicitement les shifts et les add / subs.

notez que c'était il y a 15 ans. Heureusement, les compilateurs ont seulement obtenu mieux depuis lors, de sorte que vous pouvez à peu près compter sur le compilateur faisant la bonne chose, probablement mieux que vous pourriez. (Également, la raison pour laquelle le code semble si c'est parce qu'il était plus de 15 ans il ya. J'utiliserais évidemment std::string et des itérateurs aujourd'hui.)

en plus de toutes les autres bonnes réponses ici, permettez-moi de souligner une autre raison de ne pas utiliser le décalage quand vous voulez dire diviser ou multiplier. Je n'ai jamais vu quelqu'un introduire un bogue en oubliant la priorité relative de la multiplication et de l'addition. J'ai vu des bugs introduits quand les programmeurs de maintenance ont oublié que "multiplier" via un décalage est logiquement une multiplication mais pas syntactiquement de la même priorité que multiplication. x * 2 + z et x << 1 + z sont très différents!

si vous travaillez sur nombres alors utilisez des opérateurs arithmétiques comme + - * / % . Si vous travaillez sur des tableaux de bits, utilisez peu tourner les opérateurs comme & ^ | >> . Ne les mélangez pas; une expression qui a à la fois un peu de twiddling et arithmétique est un bug qui attend de se produire.

Cela dépend du processeur et le compilateur. Certains compilateurs optimisent déjà le code de cette façon, d'autres non. 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 d'optimiser, Je ne brouillerais pas mon code source juste pour sauver une instruction d'assemblage ou un cycle de processeur.

est-il réellement plus rapide d'utiliser say (i<<3)+(i<<1) pour multiplier avec 10 que d'utiliser I*10 directement?

il pourrait ou pourrait ne pas être sur votre machine - si vous vous souciez, mesurer dans votre usage réel.

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

L'analyse comparative est très difficile à faire de façon significative, mais nous pouvons examiner quelques faits. De http://www.penguin.cz / ~literakl / intel / s. html#SAL et http://www.penguin.cz / ~literakl / intel/I. html#IMUL nous avons une idée des cycles d'horloge x86 nécessaires pour le décalage arithmétique et la multiplication. Disons que nous nous en tenons à "486" (la plus récente listée), 32 registres de bits et immediates, IMUL prend 13-42 cycles et IDIV 44. Chaque SAL prend 2, et en ajoutant 1, donc même avec quelques-uns de ceux qui se déplacent superficiellement ressemble à un gagnant.

ces jours, avec le noyau i7:

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

la latence est 1 cycle pour une addition entière et 3 cycles pour une multiplication entière . Vous trouverez les latences et le débit dans L'Annexe C du "manuel de référence D'optimisation des Architectures Intel® 64 et IA-32", qui se trouve sur le http://www.intel.com/products/processor/manuals / .

(d'après certains blurb Intel)

à l'aide de L'ESS, le Core i7 peut émettre des instructions d'addition et de multiplication simultanées, ce qui donne un taux de pointe de 8 opérations à virgule flottante (FLOP) par cycle d'horloge.

cela vous donne une idée du chemin parcouru. L'optimisation du BIT shifting par rapport à * - cela a été pris au sérieux même dans les années 90 est juste obsolète maintenant. Bit-shifting est encore plus rapide, mais pour la non-puissance-de-deux mul/div par le temps que vous faites tous vos changements et ajouter les résultats, il est plus lent à nouveau. Ensuite, plus d'instructions signifie plus de défauts de cache, plus de problèmes potentiels dans le pipelinage, plus d'utilisation de registres temporaires peut signifier plus d'économie et de restauration du contenu de Registre à partir de la pile... il devient rapidement trop compliqué de quantifier tous les impacts définitivement, mais ils sont principalement négatif.

fonctionnalité dans le code source vs implémentation

plus généralement, votre question est marquée C et C++. En tant que langages de troisième génération, ils sont spécifiquement conçus pour cacher les détails de L'ensemble D'instruction CPU sous-jacente. Pour satisfaire leurs Standards linguistiques, ils doivent supporter les opérations de multiplication et de déplacement (et beaucoup d'autres) même si le matériel sous-jacent ne . Dans de tels cas, ils doivent synthétiser le résultat requis à l'aide de nombreuses autres instructions. De la même manière, ils doivent fournir un support logiciel pour les opérations en virgule flottante si le CPU n'en a pas et s'il n'y a pas de FPU. Les CPU modernes soutiennent tous * et << , donc cela peut sembler absurde théorique et historique, mais la chose importante 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 autre chose qu'il préfère parce que c'est mieux pour le cas spécifique auquel le compilateur est confronté.

Exemples (avec une hypothétique langue de l'assembly)

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...............

comme exclusive ou ( xor ) n'ont aucun rapport avec le code source, mais xor-ing quelque chose avec lui-même efface tous les bits, de sorte qu'il peut être utilisé pour définir quelque chose à 0. Code Source qui implique la mémoire les adresses 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 l'utilisation par le développeur, la sortie du compilateur devait satisfaire l'existant dev Hardcore hand-optimizing assembly-language. communauté que le code produit n'était pas plus lent, plus verbeux ou autrement pire. Les compilateurs ont rapidement adopté beaucoup d'optimisations - ils devenu un meilleur centralisée magasin de il que tout chaque programmeur de langage d'assemblage pourrait éventuellement l'être, bien qu'il y ait toujours la chance qu'ils manquent une optimisation spécifique qui se trouve être cruciale dans un cas spécifique - les humains peuvent parfois le casser et tâtonner pour quelque chose de mieux tandis que les compilateurs font juste comme ils ont été dit jusqu'à ce que quelqu'un alimente que l'expérience de retour en eux.

donc, même si shifting et adding est encore plus rapide sur un matériel particulier, alors l'auteur du compilateur est susceptible d'avoir travaillé sur exactement quand c'est à la fois sûr et bénéfique.

maintenabilité

si votre matériel change, vous pouvez vous recompiler et regarder le CPU cible et faire un autre meilleur choix, alors qu'il est peu probable que vous vouliez revoir vos" optimisations " ou énumérer les environnements de compilation qui devraient utiliser la multiplication et ceux qui devraient changer. Pensez à tous les non-puissance de deux bits décalés "optimisations" écrite de 10 ans qui sont maintenant en train de ralentir le ils sont en code car il fonctionne sur des processeurs modernes...!

heureusement, de bons compilateurs comme GCC peuvent généralement remplacer une série de changements de bits et d'arithmétique par une multiplication directe quand n'importe quelle optimisation est activée (i.e. ...main(...) { return (argc << 4) + (argc << 2) + argc; } - > imull , 8(%ebp), %eax ) de sorte qu'une recompilation peut aider même sans fixer le code, mais ce n'est pas garanti.

étrange code bitshifting implémentant la multiplication ou la division est beaucoup moins expressif de ce que vous étiez conceptuellement essayer de réaliser, de sorte que d'autres développeurs seront confus par cela, et un programmeur confus est plus susceptible d'introduire des bogues ou de supprimer quelque chose d'essentiel dans un effort de restaurer la santé mentale apparente. Si vous ne faites des choses non évidentes que lorsqu'elles sont réellement bénéfiques, et que vous les documentez bien (mais ne documentez pas d'autres choses intuitives de toute façon), tout le monde sera plus heureux.

solutions Générales rapport à des solutions partielles

si vous avez quelques connaissances supplémentaires, comme le fait que votre int ne stockera que les valeurs x , y et z , alors vous pourrez peut-être élaborer des instructions qui fonctionnent pour ces valeurs et obtenir votre résultat plus rapidement que lorsque le compilateur n'a pas cette vision et a besoin d'une implémentation qui fonctionne pour toutes les valeurs int . Par exemple, considérez votre question:

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

vous illustrez la multiplication, mais qu'en est-il de la division?

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

selon la norme c++ 5.8:

- 3-la valeur de E1 > > E2 est la position des bits E2 décalés vers la droite. Si E1 a un type non signé ou si E1 a un type signé et une valeur non négative, la valeur du résultat est la partie intégrante du quotient de E1 divisé par la quantité 2 montée à la puissance E2. Si E1 a un type signé et une valeur négative, la valeur résultante est définie par la mise en œuvre.

ainsi, votre décalage de bits a un résultat d'implémentation défini lorsque x est négatif: il peut ne pas fonctionner de la même manière sur des machines différentes. Mais, / fonctionne beaucoup plus prévisible. (il ne peut pas être parfaitement cohérent soit, car différentes machines peuvent avoir différentes représentations de nombres négatifs, et donc de plages différentes, même quand il y a le même nombre de bits qui composent la représentation.)

vous pouvez dire "je m'en fous... int est le stockage de l'âge de l'employé, il ne peut jamais être négatif". Si vous avez ce genre de vision particulière, alors oui - votre optimisation sûre >> pourrait être transmise par le compilateur à moins que vous ne le fassiez explicitement dans votre code. Mais, c'est risqué et rarement utile comme la plupart du temps vous n'aurez pas ce genre de perspicacité, et d'autres programmeurs travaillant sur le même code ne sauront pas que vous avez parié la maison sur certaines attentes inhabituelles des données que vous manipulerez... ce qui semble être un changement totalement sûr pour eux pourrait se retourner contre vous à cause de votre "optimisation".

y a-t-il une sorte d'entrée qui ne peut être multipliée ou divisée de cette façon?

Oui... comme mentionné ci-dessus, les nombres négatifs ont un comportement de mise en œuvre défini lorsque "divisé" par bit-shifting.

vient d'essayer sur ma machine de compiler ceci:

int a = ...;
int b = a * 10;

lors du démontage il produit la sortie:

MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX
LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift !
SHL EAX, 1 ; Multiply by 2 using shift

cette version est plus rapide que votre code optimisé à la main avec le déplacement pur et l'addition.

vous ne savez vraiment jamais ce que le compilateur va venir avec, il est donc préférable d'écrire simplement un normale multiplication et laissez-le optimiser la façon dont il veut, sauf dans très cas précis où vous savoir le compilateur ne peut pas optimiser.

changement de vitesse est généralement beaucoup plus rapide que la multiplication à un niveau d'instruction, mais vous pourriez bien perdre votre temps à faire des optimisations prématurées. Le compilateur peut très bien effectuer ces optimisations à la compilation. Le faire vous-même permettra d'affecter la lisibilité et peut avoir aucun effet sur les performances. C'est probablement la peine de faire des choses comme ça si vous avez le profil trouvé ceci pour être un goulot d'étranglement.

en fait, le truc de la division, connu sous le nom de "magie" la division peut rapporter gros. Nouveau profil pour voir si c'est nécessaire. Mais si vous l'utilisez il y a des programmes utiles autour pour vous aider à comprendre quelles instructions sont nécessaires pour la même sémantique de division. Voici un exemple: http://www.masm32.com/board/index.php?topic=12421.0

un exemple que j'ai soulevé du fil de L'OP sur MASM32:

include ConstDiv.inc
...
mov eax,9999999
; divide eax by 100000
cdiv 100000
; edx = quotient

générerait:

mov eax,9999999
mov edx,0A7C5AC47h
add eax,1
.if !CARRY?
    mul edx
.endif
shr edx,16

Shift entier et les instructions de multiplication ont des performances similaires sur la plupart des Processeurs modernes entier instructions de multiplication ont été relativement lente dans les années 1980, mais en général ce n'est plus vrai. Les instructions de multiplication entières peuvent avoir une latence plus élevée 151940920", il peut donc y avoir encore des cas où un décalage est préférable. Idem pour les cas où vous pouvez garder plus d'unités d'exécution occupées (bien que cela peut couper dans les deux sens).

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 5; i >= -5; --i)
    {
        printf("%d / 2 = %d, %d >> 1 = %d\n", i, i / 2, i, i >> 1);
    }
    return 0;
}

5 / 2 = 2, 5 >> 1 = 2
4 / 2 = 2, 4 >> 1 = 2
3 / 2 = 1, 3 >> 1 = 1
2 / 2 = 1, 2 >> 1 = 1
1 / 2 = 0, 1 >> 1 = 0
0 / 2 = 0, 0 >> 1 = 0
-1 / 2 = 0, -1 >> 1 = -1
-2 / 2 = -1, -2 >> 1 = -1
-3 / 2 = -1, -3 >> 1 = -2
-4 / 2 = -2, -4 >> 1 = -2
-5 / 2 = -2, -5 >> 1 = -3