ajouter vs mul (IA32-Assemblée)

Question

Je sais que ajouter est plus rapide par rapport à mul fonction.

Je veux savoir comment aller sur l'utilisation ajouter au lieu de mul dans le code suivant afin de le rendre plus efficace.

Exemple de code:

  mov eax, [ebp + 8]    #eax = x1 
      mov ecx, [ebp + 12]    #ecx = x2 
      mov edx, [ebp + 16]    #edx = y1 
      mov ebx, [ebp + 20]    #ebx = y2 

      sub eax,ecx      #eax = x1-x2 
      sub edx,ebx      #edx = y1-y2 

      mul edx       #eax = (x1-x2)*(y1-y2) 

Answer 1

ajouter est plus rapide que mul, mais si vous voulez multiplier deux valeurs générales, mul est beaucoup plus rapide que toute boucle itérer ajouter opérations .

Vous ne pouvez pas utiliser sérieusement ajouter pour faire ce code aller plus vite que ce sera avec mul. Si vous avez besoin de multiplier par une petite valeur constante (comme 2), alors peut-être vous pouvez utiliser ajouter pour accélérer les choses. Mais pour le cas général - non.

Answer 2

En ce qui concerne les instructions d'assemblage, la vitesse d'exécution de toute instruction est mesurée en utilisant le cycle d'horloge. L'instruction Mul prend toujours plus de cycle d'horloge puis ajoute une opération, mais si vous exécutez la même instruction d'ajout dans une boucle alors le cycle d'horloge global pour faire la multiplication en utilisant l'instruction add sera beaucoup plus que l'instruction mul simple. Vous pouvez jeter un coup d'oeil sur l'URL suivante qui parle du cycle d'horloge de l'instruction simple d'addition/mul. Ainsi vous pouvez faire votre calcul, lequel sera plus rapide.

http://home.comcast.net/~fbui/intel_a.html#add

http://home.comcast.net/~fbui/intel_m.html#mul

Ma recommandation est d'utiliser l'instruction mul plutôt que d'ajouter dans la boucle putting, une solution est plus tard très inefficace.

Answer 3

Je devrais faire écho aux réponses que vous avez déjà - pour une multiplication générale, il vaut mieux utiliser MUL - après tout c'est ce qu'il est là pour! Dans certains cas spécifiques, où vous savez que vous voulez multiplier par une valeur fixe spécifique à chaque fois (par exemple, dans l'élaboration d'un index de pixel dans un bitmap), vous pouvez considérer casser la multiplication vers le bas dans une (petite) de la poignée SHLs et ajoute - par exemple:

1280 x 1024 affichage - chaque ligne de l'écran est de 1280 pixels.

1280 = 1024 + 256 = 2^10 + 2^8

y * 1280 = y * (2^10) + y * (2^8) = ADD (SHL y, 10), (SHL y, 8)

... étant donné que le traitement graphique est susceptible de devoir être rapide, une telle approche peut vous faire économiser cycles d'horloge précieux.

Answer 4

À moins que vos multiplications ne soient assez simplistes, le add ne surpasse probablement pas un mul. Cela dit, vous pouvez utiliser add pour faire multiplications:

Multiply by 2: 
    add eax,eax   ; x2 
Multiply by 4: 
    add eax,eax   ; x2 
    add eax,eax   ; x4 
Multiply by 8: 
    add eax,eax   ; x2 
    add eax,eax   ; x4 
    add eax,eax   ; x8 

Ils travaillent bien pour des puissances de deux. Je ne dis pas qu'ils sont plus rapides. Ils étaient certainement nécessaires dans les jours avant les instructions de multiplication fantaisie. C'est de quelqu'un dont l'âme a été forgée dans l'enfer-feu qui ont été les Mostek 6502, Zilog Z80 et RCA1802 :-)

Vous pouvez même multiplier par les non-pouvoirs simplement stocker les résultats intermédiaires:

Multiply by 9: 
    push ebx    ; preserve 
    push eax    ; save for later 
    add eax,eax   ; x2 
    add eax,eax   ; x4 
    add eax,eax   ; x8 
    pop ebx    ; get original eax into ebx 
    add eax,ebx   ; x9 
    pop ebx    ; recover original ebx 

Je suggère généralement que vous écrivez votre code principalement pour la lisibilité et que vous vous souciez uniquement des performances lorsque vous en avez besoin. Cependant, si vous travaillez en assembleur, vous pouvez déjà avoir au point. Mais je ne suis pas sûr que ma "solution" soit vraiment applicable à votre situation puisque vous avez un multiplicande arbitraire.

Vous devrait, cependant, le profil de toujours votre code dans l'environnement cible pour faire en sorte que ce que vous faites est en fait plus rapide. L'assembleur ne change pas du tout cet aspect de l'optimisation.

---

Si vous voulez vraiment voir assembleur but plus général pour l'utilisation add faire la multiplication, voici une routine qui prendra deux valeurs non signées dans ax et bx et retourner le produit dans ax. Il ne gérera pas le débordement avec élégance.

START: MOV AX, 0007 ; Load up registers 
     MOV BX, 0005 
     CALL MULT  ; Call multiply function. 
     HLT    ; Stop. 

MULT: PUSH BX   ; Preserve BX, CX, DX. 
     PUSH CX 
     PUSH DX 

     XOR CX,CX  ; CX is the accumulator. 

     CMP BX, 0  ; If multiplying by zero, just stop. 
     JZ  FIN 

MORE: PUSH BX   ; Xfer BX to DX for bit check. 
     POP DX 

     AND DX, 0001 ; Is lowest bit 1? 
     JZ  NOADD  ; No, do not add. 
     ADD CX,AX 

NOADD: SHL AX,1  ; Shift AX left (double). 
     SHR BX,1  ; Shift BX right (integer halve, next bit). 
     JNZ MORE  ; Keep going until no more bits in BX. 

FIN: PUSH CX   ; Xfer product from CX to AX. 
     POP AX 

     POP DX   ; Restore registers and return. 
     POP CX 
     POP BX 
     RET 

Il repose sur le fait que 123 multiplié par 456 est identique à:

123 x 6 
+ 1230 x 5 
+ 12300 x 4 

qui est de la même façon que vous avez appris la multiplication de retour en classe/école primaire. C'est plus facile avec les binaires puisque vous ne faites que multiplier par zéro ou par un (en d'autres termes, soit en ajoutant ou en ne rajoutant pas).

C'est assez vieux x86 (8086, à partir d'une session DEBUG - je ne peux pas croire qu'ils intègrent encore cette chose dans XP) puisque c'était la dernière fois que j'ai codé directement en assembleur. Il y a quelque chose à dire pour les langages de haut niveau :-)

Answer 5

Si vous multipliez deux valeurs que vous ne connaissez pas à l'avance, il est effectivement impossible de battre l'instruction de multiplication dans l'assembleur x86.

Si vous connaissez à l'avance la valeur de l'un des opérandes, vous pouvez battre l'instruction de multiplication en utilisant un petit nombre d'additions. Cela fonctionne particulièrement bien lorsque l'opérande connu est petit et n'a que quelques bits dans sa représentation binaire. Pour multiplier une valeur inconnue x par une valeur connue composée de 2^p + 2^q + ... 2^r il suffit d'ajouter x * 2^p + x * 2^q + .. x * 2 * r si bits p, q , ... et r sont définis. Ceci est facilement accompli en assembleur en déplaçant à gauche et en ajoutant:

; x in EDX 
; product to EAX 
xor eax,eax 
shl edx,r ; x*2^r 
add eax,edx 
shl edx,q-r ; x*2^q 
add eax,edx 
shl edx,p-q ; x*2^p 
add eax,edx 

Le principal problème avec ceci est qu'il faut au moins 4 horloges pour le faire, en supposant une CPU superscalaire contrainte par les dépendances de registre.Multiplier prend généralement 10 ou moins horloges sur les processeurs modernes, et si cette séquence devient plus longue que dans le temps , vous pouvez aussi faire une multiplication.

multiplier par 9:

mov eax,edx ; same effect as xor eax,eax/shl edx 1/add eax,edx 
shl edx,3 ; x*2^3 
add eax,edx 

Ce beats se multiplient; devrait seulement prendre 2 horloges. Ce qui est moins connu, c'est l'utilisation de l'instruction LEA (adresse effective de charge), pour obtenir une multiplication rapide par petite constante. LEA qui ne prend qu'une seule horloge dans le pire des cas son temps d'exécution peut souvent se chevaucher avec d'autres instructions par des CPU superscalaires.

LEA est essentiellement "ajouter deux valeurs avec de petits multiplicateurs constants". Il calcule t = 2^k * x + y pour k = 1,2,3 (voir le manuel de référence Intel) pour t, x et y étant n'importe quel registre. Si x == y, vous pouvez obtenir 1,2,3,4,5,8,9 fois x, mais en utilisant x et y comme registres séparés, vous pouvez combiner les résultats intermédiaires et vers d'autres registres (par exemple, à t), et cela s'avère remarquablement pratique. utilisant, vous pouvez réaliser une multiplication par 9 en utilisant une seule instruction:

lea eax,[edx*8+edx] ; takes 1 clock 

En utilisant LEA avec soin, vous pouvez multiplier par une variété de constantes particulières dans un petit nombre de cycles:

lea eax,[edx*4+edx] ; 5 * edx 
lea eax,[eax*2+edx] ; 11 * edx 
lea eax,[eax*4] ; 44 * edx 

Pour ce faire, vous devez décomposer votre multiplicateur constant en divers facteurs/sommes impliquant 1,2,3,4,5,8 et 9. Il est remarquable combien de petites constantes vous pouvez faire cela, et encore seulement utiliser 3-4 instructions.

Si vous autorisez l'utilisation d'autres instructions généralement une seule horloge (par exemple, SHL/SUB/GNA/MOV) vous pouvez multiplier par quelques valeurs constantes que LEA pur ne peut pas faire aussi efficacement par lui-même. Pour multiplier par 31:

lea eax,[4*edx] 
lea eax,[8*eax] ; 32*edx 
sub eax,edx; 31*edx ; 3 clocks 

La séquence LEA correspondante est plus longue:

lea eax,[edx*4+edx] 
lea eax,[edx*2+eax] ; eax*7 
lea eax,[eax*2+edx] ; eax*15 
lea eax,[eax*2+edx] ; eax*31 ; 4 clocks 

Comprendre ces séquences est un peu difficile, mais vous pouvez mettre en place une attaque organisée. Puisque LEA, SHL, SOUS, NEG, MOV sont toutes les instructions d'une seule horloge pire cas, et zéro horloges si elles n'ont aucune dépendance à d'autres instructions, vous pouvez calculer le coût d'exeuction de toute une telle séquence. Cela signifie que vous pouvez implémenter un algorithme de programmation dynamique pour générer la meilleure séquence possible de telles instructions. Ceci n'est utile que si le nombre d'horloge est inférieur à la multiplication entière pour votre CPU (j'utilise 5 horloges comme règle de base), et il n'utilise pas tous les registres, ou au moins il doesn doesn n'utilisez pas les registres qui sont déjà occupés (évitez tout débordement).

J'ai effectivement construit ceci dans notre compilateur PARLANSE, et il est très efficace pour calculer des décalages dans des tableaux de structures A [i], où la taille de l'élément de structure dans A est la constante connue.Une personne intelligente mettra probablement la réponse en cache de sorte qu'elle ne doit pas être recalculée chaque fois que la même constante se produit; Je n'ai pas fait cela parce que le temps nécessaire pour générer de telles séquences est inférieur à ce que vous attendiez.

Il est légèrement intéressant d'imprimer les séquences d'instructions nécessaires pour multiplier par toutes les constantes de 1 à 10000. La plupart d'entre elles peuvent être faites dans 5-6 instructions le plus défavorable. Par conséquent, le compilateur PARLANSE utilise rarement une multiplication réelle lors de l'indexation même les tableaux les plus nuls de structures imbriquées.