Vitesses de << >> multiplication et division

Vous pouvez utiliser <<pour multiplier et >>diviser des nombres en python lorsque je les chronomètre. Je trouve que l'utilisation de la méthode de décalage binaire est 10 fois plus rapide que la division ou la multiplication de la manière régulière.

Pourquoi utilise <<et >>beaucoup plus rapide que *et /?

Quels sont les processus en arrière-plan à faire *et /si lents?

Regardons deux petits programmes C qui font un peu de décalage et une division.

#include <stdlib.h>

int main(int argc, char* argv[]) {
        int i = atoi(argv[0]);
        int b = i << 2;
}

#include <stdlib.h>

int main(int argc, char* argv[]) {
        int i = atoi(argv[0]);
        int d = i / 4;
}

Celles-ci sont ensuite compilées avec chacune gcc -Spour voir quel sera l'assemblage réel.

Avec la version bit shift, de l'appel atoiau retour:

    callq   _atoi
    movl    $0, %ecx
    movl    %eax, -20(%rbp)
    movl    -20(%rbp), %eax
    shll    $2, %eax
    movl    %eax, -24(%rbp)
    movl    %ecx, %eax
    addq    $32, %rsp
    popq    %rbp
    ret

Alors que la version divisée:

    callq   _atoi
    movl    $0, %ecx
    movl    $4, %edx
    movl    %eax, -20(%rbp)
    movl    -20(%rbp), %eax
    movl    %edx, -28(%rbp)         ## 4-byte Spill
    cltd
    movl    -28(%rbp), %r8d         ## 4-byte Reload
    idivl   %r8d
    movl    %eax, -24(%rbp)
    movl    %ecx, %eax
    addq    $32, %rsp
    popq    %rbp
    ret

Juste en regardant cela, il y a plusieurs autres instructions dans la version de division par rapport au décalage de bits.

La clé est que font-ils?

Dans la version à décalage de bits, l'instruction clé est la shll $2, %eaxlogique de décalage à gauche - il y a le fossé, et tout le reste ne fait que déplacer des valeurs.

Dans la version diviser, vous pouvez voir le idivl %r8d- mais juste au-dessus de cela est un cltd(convertir long en double) et une logique supplémentaire autour du déversement et du rechargement. Ce travail supplémentaire, sachant que nous avons affaire à des mathématiques plutôt qu'à des bits, est souvent nécessaire pour éviter diverses erreurs qui peuvent se produire en effectuant uniquement des calculs de bits.

Permet de faire une multiplication rapide:

#include <stdlib.h>

int main(int argc, char* argv[]) {
    int i = atoi(argv[0]);
    int b = i >> 2;
}

#include <stdlib.h>

int main(int argc, char* argv[]) {
    int i = atoi(argv[0]);
    int d = i * 4;
}

Plutôt que de passer par tout cela, il y a une ligne différente:

$ diff mult.s bit.s
24c24
> shll $ 2,% eax
---
<sarl $ 2,% eax

Ici, le compilateur a pu identifier que le calcul pouvait être effectué avec un décalage, mais au lieu d'un décalage logique, il effectue un décalage arithmétique. La différence entre ceux-ci serait évidente si nous les exécutions - sarlpréserve le signe. Alors que bien -2 * 4 = -8que le shllne soit pas.

Voyons cela dans un script perl rapide:

#!/usr/bin/perl

$foo = 4;
print $foo << 2, "\n";
print $foo * 4, "\n";

$foo = -4;
print $foo << 2, "\n";
print $foo * 4, "\n";

Production:

16
16
18446744073709551600
-16

Um ... -4 << 2n'est 18446744073709551600pas exactement ce à quoi vous vous attendez probablement en matière de multiplication et de division. C'est vrai, mais ce n'est pas une multiplication entière.

Et donc méfiez-vous de l'optimisation prématurée. Laissez le compilateur optimiser pour vous - il sait ce que vous essayez vraiment de faire et fera probablement un meilleur travail avec moins de bogues.

Les réponses existantes ne traitaient pas vraiment du côté matériel, alors voici un peu cet angle. La sagesse conventionnelle est que la multiplication et la division sont beaucoup plus lentes que les changements, mais l'histoire actuelle est plus nuancée.

Par exemple, il est certainement vrai que la multiplication est une opération plus complexe à implémenter dans le matériel, mais elle ne finit pas nécessairement toujours plus lentement . En fait, il addest également beaucoup plus complexe à mettre en œuvre que xor(ou en général toute opération au niveau du bit), mais add(et sub) obtient généralement suffisamment de transistors dédiés à leur fonctionnement qui finissent par être aussi rapides que les opérateurs au niveau du bit. Vous ne pouvez donc pas simplement considérer la complexité de l'implémentation matérielle comme un guide de vitesse.

Examinons donc en détail le décalage par rapport aux opérateurs "complets" comme la multiplication et le décalage.

Déplacement

Sur presque tout le matériel, le décalage d'une quantité constante (c'est-à-dire une quantité que le compilateur peut déterminer au moment de la compilation) est rapide . En particulier, cela se produira généralement avec une latence d'un seul cycle et avec un débit de 1 par cycle ou mieux. Sur certains matériels (par exemple, certaines puces Intel et ARM), certains décalages par une constante peuvent même être "gratuits" car ils peuvent être intégrés dans une autre instruction ( leasur Intel, les capacités de décalage spéciales de la première source dans ARM).

Le décalage d'une quantité variable correspond davantage à une zone grise. Sur le matériel plus ancien, cela était parfois très lent et la vitesse changeait de génération en génération. Par exemple, lors de la sortie initiale du P4 d'Intel, le décalage d'une quantité variable était notoirement lent - nécessitant un temps proportionnel à la quantité de décalage! Sur cette plate-forme, l'utilisation de multiplications pour remplacer les équipes pourrait être rentable (c'est-à-dire que le monde a basculé). Sur les puces Intel antérieures, ainsi que sur les générations suivantes, le décalage d'une quantité variable n'était pas si douloureux.

Sur les puces Intel actuelles, le décalage d'une quantité variable n'est pas particulièrement rapide, mais ce n'est pas terrible non plus. L'architecture x86 est paralysée en ce qui concerne les décalages variables, car ils ont défini l'opération de manière inhabituelle: les décalages de 0 ne modifient pas les indicateurs de condition, mais tous les autres décalages le font. Cela empêche le changement de nom efficace du registre des drapeaux car il ne peut pas être déterminé jusqu'à ce que le décalage s'exécute si les instructions suivantes doivent lire les codes de condition écrits par le décalage, ou une instruction antérieure. De plus, les décalages n'écrivent que dans une partie du registre des drapeaux, ce qui peut entraîner un blocage partiel des drapeaux.

Le résultat est alors que sur les architectures Intel récentes, le décalage d'une quantité variable prend trois "micro-opérations" tandis que la plupart des autres opérations simples (ajout, opérations au niveau du bit, même multiplication) ne prennent que 1. De tels décalages peuvent s'exécuter au plus une fois tous les 2 cycles .

Multiplication

La tendance du matériel informatique de bureau et portable moderne est de faire de la multiplication une opération rapide. Sur les puces Intel et AMD récentes, en fait, une multiplication peut être émise à chaque cycle (nous appelons cela un débit réciproque ). La latence , cependant, d'une multiplication est de 3 cycles. Cela signifie donc que vous obtenez le résultat d'une multiplication donnée 3 cycles après l'avoir démarré, mais vous pouvez commencer une nouvelle multiplication à chaque cycle. La valeur (1 cycle ou 3 cycles) la plus importante dépend de la structure de votre algorithme. Si la multiplication fait partie d'une chaîne de dépendance critique, la latence est importante. Sinon, le débit réciproque ou d'autres facteurs peuvent être plus importants.

La clé à retenir est que sur les puces portables modernes (ou mieux), la multiplication est une opération rapide, et probablement plus rapide que la séquence d'instructions 3 ou 4 qu'un compilateur émettrait pour "obtenir l'arrondi" correct pour des changements de force réduits. Pour les décalages variables, sur Intel, la multiplication serait également généralement préférée en raison des problèmes susmentionnés.

Sur les plates-formes plus petites, la multiplication peut encore être plus lente, car la construction d'un multiplicateur complet et rapide 32 bits ou surtout 64 bits nécessite beaucoup de transistors et d'énergie. Si quelqu'un peut fournir des détails sur les performances de la multiplication sur les puces mobiles récentes, ce serait très apprécié.

Diviser

La division est à la fois une opération plus complexe, sur le plan matériel, que la multiplication et est également beaucoup moins courante dans le code réel - ce qui signifie que moins de ressources lui sont probablement allouées. La tendance des puces modernes est toujours vers des diviseurs plus rapides, mais même les puces haut de gamme modernes prennent 10 à 40 cycles pour effectuer une division, et elles ne sont que partiellement pipelinées. En général, les divisions 64 bits sont encore plus lentes que les divisions 32 bits. Contrairement à la plupart des autres opérations, la division peut prendre un nombre variable de cycles selon les arguments.

Évitez les divisions et remplacez par des décalages (ou laissez le compilateur le faire, mais vous devrez peut-être vérifier l'assemblage) si vous le pouvez!

BINARY_LSHIFT et BINARY_RSHIFT sont des processus algorithmiques plus simples que BINARY_MULTIPLY et BINARY_FLOOR_DIVIDE et peuvent prendre moins de cycles d'horloge. C'est-à-dire que si vous avez un nombre binaire et que vous devez effectuer un décalage de bits par N, tout ce que vous avez à faire est de déplacer les chiffres sur autant d'espaces et de les remplacer par des zéros. La multiplication binaire est en général plus compliquée , bien que des techniques comme le multiplicateur Dadda le rendent assez rapide.

Certes, il est possible pour un compilateur d'optimisation de reconnaître les cas où vous multipliez / divisez par des puissances de deux et remplacez par le décalage gauche / droite approprié. En regardant le code d'octet désassemblé, python ne fait apparemment pas cela:

>>> dis.dis(lambda x: x*4)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (4)
              6 BINARY_MULTIPLY     
              7 RETURN_VALUE        

>>> dis.dis(lambda x: x<<2)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (2)
              6 BINARY_LSHIFT       
              7 RETURN_VALUE        


>>> dis.dis(lambda x: x//2)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (2)
              6 BINARY_FLOOR_DIVIDE 
              7 RETURN_VALUE        

>>> dis.dis(lambda x: x>>1)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (1)
              6 BINARY_RSHIFT       
              7 RETURN_VALUE        

Cependant, sur mon processeur, je trouve que la multiplication et le décalage gauche / droite ont un timing similaire, et la division du plancher (par une puissance de deux) est environ 25% plus lente:

>>> import timeit

>>> timeit.repeat("z=a + 4", setup="a = 37")
[0.03717184066772461, 0.03291916847229004, 0.03287005424499512]

>>> timeit.repeat("z=a - 4", setup="a = 37")
[0.03534698486328125, 0.03207516670227051, 0.03196907043457031]

>>> timeit.repeat("z=a * 4", setup="a = 37")
[0.04594111442565918, 0.0408930778503418, 0.045324087142944336]

>>> timeit.repeat("z=a // 4", setup="a = 37")
[0.05412912368774414, 0.05091404914855957, 0.04910898208618164]

>>> timeit.repeat("z=a << 2", setup="a = 37")
[0.04751706123352051, 0.04259490966796875, 0.041903018951416016]

>>> timeit.repeat("z=a >> 2", setup="a = 37")
[0.04719185829162598, 0.04201006889343262, 0.042105913162231445]