[Optimisation]Est-ce possible ?

Bonjour à tous !
J'ai une fonction "inlinée" qui est énormément appelée, et je pense qu'elle est optimisable, mais je ne vois pas bien comment...

Code:

---

1 2 3 4 5 6 7 8

__inline const Int gClip( const Int iX ) { const Int i2 = (iX & 0xFF); if( i2 == iX ) { return iX; } if( iX < 0 ) { return 0x00; } else { return 0xFF; } }

---

Je pense en particulier à virer les if() mais je n'y parviens pas.
Si jamais ça peut vous aider, le code est destiné à un ARMv5.
Merci d'avance !

deja tu peux enlever le dernier "else" qui ne sert a rien, apres je vois pas ;)

Visiblement tu veux faire une saturation.

2 pistes:

-utiliser des instructions MMX/SSE2 qui savent faire ça automatiquement dans les calculs. Cette méthode n'est cependant pas évidente à mettre en oeuvre quand on n'a pas l'habitude du calcul vectoriel.

-tu peux remplacer tes "if" par un min suivi d'un max. Mais plutôt que d'utiliser les min et max classiques (avec "if" ou "?:" qui doivent faire une fois sur deux un saut et donc cassent le pipeline du processeur), préfère les fonctions "__min" et "__max" sous Visual (ou leur équivalent pour d'autres compilos...)

Quand ta fonction est inlinée le if devrait déjà être enlevé...
Regarde le code généré par ton compilateur.

Justement, le code est assez fouillis, mais il contient plusieurs cmp, je pense donc que les if ne sont pas trop enlevés...

Bonjour,
perso je ne vois pas de moyen d'optimiser encore la fonction, sauf en la codant en asm...

Merci pour les différents conseils :).

Tu peux éviter les sauts conditionnels au prix de quelques contorsions arithmétiques. Je ne suis ps sûr que le résultat soit plus rapide/efficace/court. De plus cela demande de bien savoir comment sont implémentés les Int (taille ? Où est le bit de signe ?).

Le test (iX < 0) peut s'écrire (ix & 0x80000000), il suffit ensuite de convertir ce résultat en 0 ou 1. Exemple :

Code:

---

1 2	if( iX < 0 ) { return 0x00; } else { return 0xFF; }

---

devient

Code:

---

1 2	static Int tab[2] = { 0x00, 0xFF }; return tab[(iX >> 31) & 1];

---

Pour le test (iX & 0xFF) c'est plus délicat. Si tu es sûr qu'un réultat de test vaut 0 ou 1 (c'est le cas quand l'assembleur utilise des SETE/SETNE), tu peux utiliser (iX >> 8) && 1, ou bien (int)((bool)iX >> 8)) pour détecter des bits non nuls en dehors de ceux de poid faible. Ta fonction devient alors :

Code:

---

1 2 3 4 5 6 7

__inline const Int gClip( const Int iX ) { static Int tab[2] = { 0x00, 0xFF }; Int local = (i >> 8) && 1; return (local * tab[(iX >> 31) & 1]) | (iX * (1-local)); }

---

Attention aux & et && !

C'est ce que je souhaitais faire...
Maintenant, il va falloir que je regarde le code généré pour savoir si ça fonctionne, c'est bien cela ?

ou juste vérifier que (27 && 1) vaut bien 1.

Citation:

---

Justement, le code est assez fouillis, mais il contient plusieurs cmp, je pense donc que les if ne sont pas trop enlevés...

---

Avec O2 ?

Citation:

---

Envoyé par loufoque

Avec O2 ?

---

Un compilateur ne peut pas supprimer les sauts conditionnels comme ça...

Ici le plus simple sous Visual, et sans saut, c'est

Code:

---

return __max(0,__min(255,x))

---

Si t'as pas d'équivalent pour __min et __max avec ton compilo, il suffit de les programmer

Citation:

---

Envoyé par loufoque

Justement, le code est assez fouillis, mais il contient plusieurs cmp, je pense donc que les if ne sont pas trop enlevés...

---

Ce ne sont pas les CMP qui gênent, mais les JGE/JLE et autres qui font les sauts. Un CMP couplé avec un SETE ne posera pas le problème de pipeline rompue, par exemple.

Citation:

---

Envoyé par Charlemagne

-tu peux remplacer tes "if" par un min suivi d'un max. Mais plutôt que d'utiliser les min et max classiques (avec "if" ou "?:" qui doivent faire une fois sur deux un saut et donc cassent le pipeline du processeur), préfère les fonctions "__min" et "__max" sous Visual (ou leur équivalent pour d'autres compilos...)

---

En Visual C 2005, j'ai :

Code:

---

1 2 3

#define __max(a,b) (((a) > (b)) ? (a) : (b)) #define __min(a,b) (((a) < (b)) ? (a) : (b))

---

:/

Tiens oui, t'as raison. Je me suis trompé.
J'étais convaincu du contraire, que min/max étaient implémentés différemment. J'avais pourtant eu (il me semble) des gains significatifs de vitesses grâce à __min/__max. Peut-être que dans certaines circonstances le compilo sait compiler l'opérateur "?:" sans saut.

J'en reviens à MMX ou SSE2 qui proposent des calculs saturés, ainsi que des instructions min/max sans saut. C'est imbattable...

Le processeur est un ARM, que je connais assez mal.
Comment écrire le min/max sans saut ?

Par exemple

Code:

---

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

inline int max(int a, int b) { b = a-b; a -= b & (b>>31); return a; } inline int min(int a, int b) { b = b-a; a += b & (b>>31); return a; } inline int abs(int a) { return a - ((a+a) & (a>>31)); }

---

PS: C'est peut-être pas si grâve que ça dans ton cas s'il y a des sauts, par exemple si tu sais que dans la grande majorité des cas tes valeurs sont comprises entre 0 et 255, tu peux t'arranger pour que les conditions des "if" soient remplies. Comme le processeur (en tout cas le x86) suppose que les conditions sont toujours remplies, le pipeline ne sera quasiment jamais brisé.

Ca suppose quand même que les int sont codés sur 32 bits, et utilisent le premier bit pour coder le signe.

Citation:

---

Envoyé par Laurent Gomila

Ca suppose quand même que les int sont codés sur 32 bits, et utilisent le premier bit pour coder le signe.

---

Ce n'était qu'un exemple fait à la va-vite pour montrer comment éviter les branchements.
Plus on optimise plus on fait des suppositions sur le matériel.
Les instructions MMX/SSE2 font aussi des suppositions, mais elles sont beaucoup plus rapides...

Pour le problème du 32, on peut toujours utiliser 8*sizeof(int) à la place, mais là n'est pas le propos.

Citation:

---

Envoyé par Charlemagne

Un compilateur ne peut pas supprimer les sauts conditionnels comme ça...

---

Bien sûr que si.
Lorsqu'il fait de l'inlining il peut adapter la fonction en fonction de ses paramètres.

Code:

---

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

#include <cstdio>   typedef int Int;   inline const Int gClip( const Int iX ) { const Int i2 = (iX & 0xFF); if( i2 == iX ) { return iX; } if( iX < 0 ) { return 0x00; } else { return 0xFF; } }   int main() { const int a = gClip(-1); std::printf("%d\n", a); }

---

ne génère en fait chez moi que printf("%d\n", 0); (c'est particulièrement clair avec GCC/LLVM)

C'est en fait bien souvent le plus simple qui est le plus performant. En ayant un code clair le compilateur est à même d'optimiser proprement.
Le compilateur est d'ailleurs probablement plus malin que toi pour optimiser.

Comme je l'ai déjà dit regarde ce que génère ton compilateur avant de dire que ce n'est pas optimisé...

Citation:

---

Envoyé par loufoque

Bien sûr que si.
Lorsqu'il fait de l'inlining il peut adapter la fonction en fonction de ses paramètres.

---

Uniquement avec des constantes... ce qui rend l'intérêt quasi nul... puisque le programmeur aurait également pu le faire!

Citation:

---

Envoyé par loufoque

Le compilateur est d'ailleurs probablement plus malin que toi pour optimiser.

---

J'en doute fort.
Plus malin que toi... sûrement...

Sans être méchant, il est évident que le compilateur, voyant une valeur constante, optimise de lui-même.
Il est également évident que ce n'est pas mon cas, car j'utilise des variables...

Citation:

---

Envoyé par Charlemagne

Uniquement avec des constantes... ce qui rend l'intérêt quasi nul... puisque le programmeur aurait également pu le faire!

---

Pas uniquement sur des constantes... Si je construis une class Segment { x0, x1 }, avec une fonction "length" en inline qui va a priori faire un { return abs(x1-x0); }. Comment puis-je optimiser ca ? Pas possible !

Par contre, le compilateur, lui, a connaissance du context appelant, et va donc optimiser

Code:

---

1 2 3 4 5 6

int l; { Segment test(0,5); int l = test.length(); }

---

en....

Code:

---

1 2	int l = 5;

---

Mieux encore, les compilateurs connaissent les valeurs possibles d'une variable... Et optimisent en fonction de cette information.
D'ou l'importance de l'utilisation des assert() dans le code. Non seulement ils permettent de s'assurer d'une précondition, mais donnent d'excellentes indications au compilateur (__assume sous Visual).

T'as rien compris.
Tu ne fais que transposer la constante....intérêt quasi nul...

Dans ton exemple, j'aurais pu également te donner la valeur de la longueur de ton segment.
Demande donc plutôt à l'utilisateur d'entrer les coordonnées du segment...

Je rejoins Charlemagne (ça c'est rigolo à dire/écrire...) !
Evidement qu'il va optimiser, tu lui donnes des valeurs constantes dans le code.
Si tu fais intervenir des variables tenant sur 4 octets (ou plus) il ne va pas s'amuser à calculer tous les possibles (2^32 dans ce cas) et évaluer chaque cas...

Si tu fais ça comme code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

int l,i,j; { for (i=0 ; i< 3000000 ; i++) { for(j=0;j<251000;j++) { Segment test(i,j); l = test.length(); printf("l = %d", l); } } }

---

Je doutes qu'il arrive à optimiser...

Merci du soutien.

Petite remarque:
En l'occurrence je sais que mon compilo (Intel Compiler) sait optimiser ta boucle car il remarquera que la variable locale 'l' n'est pas utilisée et ne va pas faire de boucle du tout! Les autres compilos savent probablement l'optimiser également.
C'est différent par exemple si tu affiches les résultats à l'écran...

J'ai édité ;).

Citation:

---

Envoyé par Charlemagne

T'as rien compris.
Dans ton exemple, j'aurais pu également te donner la valeur de la longueur de ton segment.

---

Oui, parceque tu sais sémantiquement ce que length() "devrait" faire... si par contre, à un moment, un programmeur change le length() en abs(x1-x0)/2 par exemple, ton optimisation manuelle ne tient plus, et pire, casse le code sans que personne ne puisse s'en apercevoir sauf toi.

C'est la base du refactoring. Plus le code est optimisé en évitant les appels de fonction "évidents", moins il est refactorisable (et donc maintenable).

Les 'segment', 'length' sont donnés à titre d'exemple, il est bien évidemment idiot de faire ce que je dis sur un 'length()' :)

Mais bon... on va arrêter là cette disgression :)

Tu comprends rien à rien...

Et alors, ton programme affichait invariablement la valeur 5, dorénavant il affichera 2.5...
Le compilateur optimise le calcul sur des données constantes! très bien, c'est sympa de sa part...

Tu veux essayer de nous faire croire que tous les sauts sont finalement inutiles dans un programme ou quoi?

Citation:

---

Envoyé par Charlemagne

Tu comprends rien à rien...

---

Je confirme... j'ai rien compris à ton dernier message, mais bon... c'est pas très grave non plus :)