temps d'exécution et multiplication par 2

Bonjour

Ce bout de code

Code:

---

1 2	int a; a = a * 2;

---

et celui-ci

Code:

---

1 2	int a; a = a << 1;

---

font la même chose : multiplier a par 2. Par contre, quel est le code le plus rapide à l'exécution et comment le vérifier ?

Moi je commencerais déjà par désassembler tout ça pour voir comment le compilateur l'a optimisé. Ensuite, si tu n'arrives toujours pas à voir, il reste la méthode itérative : tu lances 1 000 000 000 de multiplications avec les 2 méthodes et tu compares les temps d'exécutions sachant que de toutes façons ça peux varier en fonction de ton compilateur, de ton architecture, ...

Mon avis : ne te prend pas la tête.

Ecrit un code simple à comprendre et en accord avec ton contexte de développement.

Si dans ton contexte, l'instruction "*" a plus de sens que "<<" utilise la multiplication, si tu manipules des bits, utilise l'instruction "<<".

Après c'est le boulot de l'optimiseur de changer/remplacer certaines instructions par d'autres parce qu'il sait que celle la va plus vite et fait le même boulot que l'autre.

Citation:

---

Envoyé par corentin59

Bonjour

Ce bout de code

Code:

---

1 2	int a; a = a * 2;

---

et celui-ci

Code:

---

1 2	int a; a = a << 1;

---

font la même chose : multiplier a par 2. Par contre, quel est le code le plus rapide à l'exécution et comment le vérifier ?

---

C'est la même chose, à part peut-être si tu utilises un compilateur complètement dépassé. La plupart des compilateurs sont capables de simplifier aussi n'importe quelle multiplication ou division par constante.

Le code suivant:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

int f1(int n) { int res = 2 * n; return res; }   int f2(int n) { int res = n << 1; return res; }   int main(void) { f1(100); f2(100); return 0; }

---

donne (après compilation avec gcc -S -O2 -c):

Code:

---

1 2 3 4 5 6 7

_f1: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax popl %ebp addl %eax, %eax ret

---

et

Code:

---

1 2 3 4 5 6 7

_f2: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax popl %ebp addl %eax, %eax ret

---

On voit que le code généré est strictement identique dans les deux cas. Et même avec un niveau d'optimisation -O0, gcc génère un code identique pour f1() et f2():

Code:

---

1 2 3 4 5 6 7 8 9

pushl %ebp movl %esp, %ebp subl $16, %esp movl 8(%ebp), %eax addl %eax, %eax movl %eax, -4(%ebp) movl -4(%ebp), %eax leave ret

---

Donc, inutile de se tourmenter avec ce genre de micro-optimisations qui ne t'apportera pas grand chose. L'essentiel est d'écrire du code lisible et de se concentrer sur l'optimisation au niveau du choix et de la conception de l'algo.

Thierry

OK, merci pour vos réponses.

Citation:

---

Envoyé par Thierry Chappuis

Code:

---

1 2 3 4 5 6

_f1: pushl %ebp movl %esp, %ebp movl 8(%ebp), %eax popl %ebp addl %eax, %eax ret

---

---

Et même si mes souvenirs en assembleurs ne sont pas trop rouillés, l'optimiseur a remplacé dans les 2 cas la multiplication et le décalage par une addition

Code:

---

1 2	addl %eax, %eax

---

Cela revient à ajouter dans eax, le contenu de eax donc à multiplier par 2 le registre eax. L'optimiseur pense donc que dans ce cas, une addition est encore plus rapide.

Citation:

---

Par contre, quel est le code le plus rapide à l'exécution [...]

---

ça dépend sur quel processeur tu veux faire tourner ce code.
Si tu as un processeur Intel Pentium III l'instruction shl sera plus rapide que mul et add par contre si tu tournes sur un processeur Intel récent Pentium 4 et après l'instruction add est plus rapide que mul et shl.

Une petite remarque aussi sur la fonction codé par Thierry :
sa fonction :

Code:

---

1 2 3 4 5

int f1(int n) { int res = 2 * n; return res; }

---

Devrait être écrite comme ceci :

Code:

---

1 2 3 4

unsigned int __fastcall f1(unsigned n) { return n << 1; }

---

Voilà...

Citation:

---

Envoyé par NairodDorian

Une petite remarque aussi sur la fonction codé par Thierry :
sa fonction :

Code:

---

1 2 3 4 5

int f1(int n) { int res = 2 * n; return res; }

---

Devrait être écrite comme ceci :

Code:

---

1 2 3 4

unsigned int __fastcall f1(unsigned n) { return n << 1; }

---

Voilà...

---

Pourquoi?

Je fais confiance aux qualités d'optimiseur de mon compilo.

Thierry

A ma connaissance le shift est toujours plus rapide pour les multiplications et divisions par 2

Pour les multiplications par 2, je me permets d'en douter.
Selon le proc, l'addition peut être plus rapide que le décalage (il me semble que c'était le cas pour les 68000 par exemple)

Citation:

---

Envoyé par samitriani

A ma connaissance le shift est toujours plus rapide pour les multiplications et divisions par 2

---

Si gcc utilise l'addition, j'ai confiance dans le fait qu'il sait ce qu'il fait et qu'il pense que l'addition est plus rapide que le décalage. D'ailleurs, gcc optimise également ma fonction f2() (qui utilise un décalage) en générant une addition.

Thierry

Citation:

---

Pourquoi?

---

Il suffit de comparer le code ASM.
Ta fonction compiler avec MSC++ on a :

Code C :

Code:

---

1 2 3 4 5 6

int f1(int n) { int res = 2 * n; return res; }

---

ASM généré :

Code:

---

1 2 3

mov eax, DWORD PTR _n$[esp-4] add eax, eax

---

Mon code C :

Code:

---

1 2 3 4 5

unsigned int __fastcall f1(unsigned n) { return n << 1; }

---

ASM généré :

Code:

---

1 2	lea eax, DWORD PTR [ecx+ecx]

---

Si on décode le code ASM de ta fonction on voit que le paramètre est "stocké" sur la pile et mit dans le registre EAX. Ensuite on a une addition de EAX lui même dont le résultat est retourné dans le registre EAX.

Si on décode le code ASM de ma fonction on voit que le paramètre est "stocké" dans le registre ecx et que l'addition de ce même registre est immédiatement mit dans le registre EAX.

Ma fonction est donc plus rapide de qq cycles.

Après écrire :

Code:

---

1 2	return n << 1;

---

Ou :

Code:

---

1 2	return n * 2

---

dans mon code C ne change rien le même code ASM sera généré.
Une remarque quand même il faut mettre le type unsigned car on fait des opérations de décalages sur les types unsigned par convention.

Voilà...

__fastcall est non standard, donc il n'y a pas de raison pour l'utiliser avant de savoir que ça va apporter quelque chose. Et si on est dans ce cas-là le plus important c'est que la fonction soit inlinée.

Citation:

---

Envoyé par NairodDorian

ça dépend sur quel processeur tu veux faire tourner ce code.
Si tu as un processeur Intel Pentium III l'instruction shl sera plus rapide que mul et add par contre si tu tournes sur un processeur Intel récent Pentium 4 et après l'instruction add est plus rapide que mul et shl.

---

ADD a l'avantage de toujours être rapide et de ne pas créer de ne pas créer de partial flag stall, à part pour les shifts reg, 1 sur les Core 2 qui n'en font pas non plus. L'inconvénient c'est qu'il faut utiliser plusieurs additions pour émuler un décalage de plus d'un bit.

Citation:

---

Envoyé par NairodDorian

Il suffit de comparer le code ASM.
Ta fonction compiler avec MSC++ on a :

Code C :

Code:

---

1 2 3 4 5 6

int f1(int n) { int res = 2 * n; return res; }

---

ASM généré :

Code:

---

1 2 3

mov eax, DWORD PTR _n$[esp-4] add eax, eax

---

Mon code C :

Code:

---

1 2 3 4 5

unsigned int __fastcall f1(unsigned n) { return n << 1; }

---

ASM généré :

Code:

---

1 2	lea eax, DWORD PTR [ecx+ecx]

---

Si on décode le code ASM de ta fonction on voit que le paramètre est "stocké" sur la pile et mit dans le registre EAX. Ensuite on a une addition de EAX lui même dont le résultat est retourné dans le registre EAX.

Si on décode le code ASM de ma fonction on voit que le paramètre est "stocké" dans le registre ecx et que l'addition de ce même registre est immédiatement mit dans le registre EAX.

Ma fonction est donc plus rapide de qq cycles.

Après écrire :

Code:

---

1 2	return n << 1;

---

Ou :

Code:

---

1 2	return n * 2

---

dans mon code C ne change rien le même code ASM sera généré.
Une remarque quand même il faut mettre le type unsigned car on fait des opérations de décalages sur les types unsigned par convention.

Voilà...

---

1) c'est l'utilisation abusive de __fastcall et absolument pas de shift left, utilise inline plutot.
2) plus d'instructions ASM n'a jamais voulu dire moins rapide
3) le shift a été optimisé en une addition...

j'ajouterai que le plus intelligent est d'ecrire le code de facon a ce que le compilateur le comprenne pour utiliser les meilleures instructions.
il est beaucoup plus facile d'ecrire "n*2" et de le relire que d'obfusquer un relecteur et le compilateur avec une fausse optimisation.

Citation:

---

Envoyé par corentin59

Ce bout de code

Code:

---

1 2	int a; a = a * 2;

---

et celui-ci

Code:

---

1 2	int a; a = a << 1;

---

font la même chose : multiplier a par 2. Par contre, quel est le code le plus rapide à l'exécution et comment le vérifier ?

---

N'oublie pas que le code source n'est une déclaration d'intention à l'encontre du compilateur, qui lui, écrit le code machine qui va bien. Il est fort probable que les 2 codes sources donnent le même code machine avec un compilateur moderne... Tu ne verras donc pas la différence.

Si tu veux la voir, il faut coder en assembleur.

Moi y a un truc qui me fait rire.
En quoi utilisé __fastcall vous dérange?

Citation:

---

Envoyé par NairodDorian

Moi y a un truc qui me fait rire.
En quoi utilisé __fastcall vous dérange?

---

C'est pas standard. Ce n'est donc pas une solution universelle. Mais si ça fonctionne dans ton monde, ne t'en prive pas...

Citation:

---

Envoyé par NairodDorian

Moi y a un truc qui me fait rire.
En quoi utilisé __fastcall vous dérange?

---

l'utilité face a l'inlining est assez limité. c'est aussi une optimisation prématurée. et moins d'instruction ASM ca ne veut pas dire code plus rapide.