La division est l'une des opérations les plus coûteuses des processeurs modernes. Vous n'avez pas à aller loin pour la preuve: Agner Fog [
1 ] diffuse que sur les processeurs Intel / AMD, nous pouvons facilement obtenir une latence en 25-119 cycles d'horloge et un débit réciproque - 25-120. Traduit en russe -
LENT ! Néanmoins, il est possible d'éviter l'instruction de division dans votre code. Et dans cet article, je vais vous expliquer comment cela fonctionne, en particulier dans les compilateurs modernes (ils sont capables de le faire depuis 20 ans déjà), et je vais également vous expliquer comment les connaissances acquises peuvent être utilisées pour rendre le code meilleur, plus rapide, plus puissant.
En fait, je parle: si le diviseur est connu au stade de la compilation, il est possible de remplacer la division entière par la multiplication et un décalage logique vers la droite (et parfois vous pouvez vous en passer - je parle certainement de l'implémentation dans le langage de programmation). Cela semble très encourageant: l'opération de multiplication d'entiers et un décalage vers la droite par exemple par Intel Haswell ne prendra pas plus de 5 cycles d'horloge. Il ne reste plus qu'à comprendre comment, par exemple, en effectuant une division entière par 10, pour obtenir le même résultat par multiplication entière et un décalage logique vers la droite? La réponse à cette question réside dans la compréhension ... Arithmétique à virgule fixe (ci-après FPA). Un peu de bases.
Lors de l'utilisation de FP, l'exposant (exposant 2 => la position du point dans la représentation binaire du nombre) n'est pas enregistré dans le nombre (contrairement à l'arithmétique à virgule flottante, voir IEE754), mais il est considéré comme une quantité convenue connue des programmeurs. Seule la mantisse (ce qui vient après le point décimal) est conservée. Un exemple:
0,1 - en notation binaire, il a une `` représentation infinie '', qui est indiquée par des parenthèses dans l'exemple ci-dessus - cette partie sera répétée de temps en temps, se succédant en notation binaire FP du nombre 0,1.Dans l'exemple ci-dessus, si nous utilisons des registres 16 bits pour stocker des nombres FP, nous ne pouvons pas ajuster la représentation FP du nombre 0,1 dans un tel registre sans perdre en précision, ce qui à son tour affectera le résultat de tous les calculs ultérieurs dans lesquels la valeur de ce registre est impliquée.
Supposons que l'on nous donne un entier A de 16 bits et une partie fraction de 16 bits de B. Le produit de A par B donne un nombre avec 16 bits dans la partie entière et 16 bits dans la partie fractionnaire. Pour obtenir uniquement la partie entière, vous devez évidemment déplacer le résultat de 16 bits vers la droite.
Félicitations, l'introduction au FPA est terminée.
Nous formons l'hypothèse suivante: pour effectuer une division entière par 10, nous devons multiplier le nombre divisible par la représentation FP du nombre 0,1, prendre la partie entière et la matière dans le chapeau ... attendez une minute ... Mais le résultat sera-t-il précis, plus précisément sa partie entière? - Après tout, comme nous nous en souvenons, dans notre mémoire, seule une version approximative du nombre 0,1 est stockée. Ci-dessous, j'ai écrit trois représentations différentes de 0,1: une représentation infiniment précise de 0,1, tronquée après le 16e bit sans arrondi, une représentation de 0,1, et tronquée après le 16e bit avec arrondi, une représentation de 0,1.
0001100110011001|10011001....−infiniprécision :0001100110011001|00000000....−tronquantsansarrondi0001100110011010|00000000....−tronqueravecarrondirverslehaut
Estimons les erreurs de représentations tronquées du nombre 0,1:
infinityprecision−truncatingwithoutrounding=0.6∗2−16truncatingwithroundingup−infinityprecision=0.1∗2−14
Pour que le résultat de la multiplication de l'entier A par l'approximation de 0,1 donne la partie entière exacte, nous devons:
IntegerPart(A∗0,1)=IntegerPart(A∗(0,1+0,1∗2−14)),
soit
IntegerPart(A∗0,1)=IntegerPart(A∗(0,1+0,6∗2−16))
Il est plus pratique d'utiliser la première expression: quand
nous obtenons toujours l'identité (mais, rappelez-vous, toutes les décisions ne sont pas plus que suffisantes dans le cadre de ce problème). Résoudre, nous obtenons
A<214 . Autrement dit, en multipliant tout nombre A de 14 bits en tronquant en arrondissant la représentation de 0,1, nous obtenons toujours la partie entière exacte, que nous obtiendrions en multipliant infiniment exactement 0,1 par A. Mais, par convention, nous multiplions les nombres de 16 bits, ce qui signifie , dans notre cas, la réponse sera inexacte et nous ne pouvons pas faire confiance à une simple multiplication en tronquant avec arrondi à 0,1. Maintenant, si nous pouvions enregistrer dans la représentation FP du nombre 0,1 et non 16 bits, mais disons 19, 20, alors tout irait bien. Et après tout, nous pouvons!
Nous examinons attentivement la représentation binaire - tronquée avec arrondi à 0,1: les trois bits les plus élevés sont nuls, ce qui signifie qu'ils ne contribuent pas au résultat de la multiplication (nouveaux bits).
Par conséquent, nous pouvons décaler notre nombre vers la gauche de trois bits, arrondir et, après avoir fait la multiplication et le décalage logique vers la droite, d'abord par 16, puis par 3 (c'est-à-dire en général à la fois par 19) - nous obtenons la partie entière exacte souhaitée . La preuve de l'exactitude de cette multiplication de «19» bits est similaire à la précédente, à la seule différence qu'elle fonctionne correctement pour les nombres de 16 bits. Un raisonnement similaire est également valable pour les nombres de plus grande capacité, et pas seulement pour la division par 10.
Plus tôt, j'ai écrit que, d'une manière générale, vous pouvez vous passer de tout changement, en vous limitant à la multiplication. Comment? Assembleur x86 / x64 sur le tambour:
Dans les processeurs modernes, il existe une commande MUL (il existe également des analogues de IMUL, MULX - BMI2), qui, en prenant un paramètre, disons 32/64 bits, est capable d'effectuer une multiplication 64/128 bits, enregistrant le résultat en parties dans deux registres (32/64 bits élevés et plus jeune, respectivement):
MUL RCX ; RCX RAX, (128 ) RDX:RAX
Laissez un entier 62 bits A être stocké dans le registre RCX, et laissez la représentation FA 64 bits tronquant avec l'arrondi du nombre 0,1 être stockée dans le registre RAX (notez qu'il n'y a pas de décalage vers la gauche). Après avoir terminé la multiplication 64 bits, nous obtenons que les 64 bits les plus élevés du résultat soient stockés dans le registre RDX, ou, plus précisément, la partie entière, qui sera exacte pour les nombres de 62 bits. Autrement dit, un décalage vers la droite (SHR, SHRX) n'est pas nécessaire. La présence d'un tel décalage charge le Pipeline du processeur, qu'il prenne en charge OOOE ou non: au moins il existe une dépendance supplémentaire dans la chaîne déjà très probable de ces dépendances (aka Dependency Chain). Et ici, il est très important de mentionner que les compilateurs modernes, voyant une expression de la forme some_integer / 10, génèrent automatiquement du code assembleur pour toute la gamme des nombres divisibles. Autrement dit, si vous savez que vous avez toujours des nombres de 53 bits (c'est exactement ce que c'était dans ma tâche), vous obtenez toujours l'instruction de décalage supplémentaire. Mais, maintenant que vous comprenez comment cela fonctionne, vous pouvez facilement remplacer vous-même la division par la multiplication, sans compter sur la merci du compilateur. Soit dit en passant, obtenir les bits hauts d'un produit 64 bits en code C ++ est implémenté par quelque chose comme mulh, qui selon le code Asm devrait être équivalent aux lignes de l'instruction {I} MUL {X} ci-dessus.
Peut-être qu'avec l'avènement des contrats (en C ++ 20 on n'attend pas) la situation va s'améliorer, et dans certains cas, on peut faire confiance à la voiture! Bien qu'il s'agisse de C ++, le programmeur est responsable de tout ici - pas autrement.
Le raisonnement décrit ci-dessus - s'applique à tous les diviseurs de constantes, et voici une liste de liens utiles:
[1] https://www.agner.org/optimize/instruction_tables.pdf[2] Plus raide qu'Agner Fogh[3] Canal télégramme contenant des informations utiles sur les optimisations pour Intel / AMD / ARM[4] À propos de la division entièrement, mais en anglais