Bonjour à tous   , je vous propose un petit challenge de programmation la plus efficace possible,
le but est de partager ses connaissances et montrer à tous des méthodes de programmation performantes
 
la règle du jeux est la suivante, à partir d'un code simple de filtrage d'image par exemple, tout candidat peut proposer ses propres modifications
et montrer à tous le gain en performance qu'il a pu noter.
 
Sont autorisés tout changement du code d'origine qui ne modifie pas le résultat final, à partir de là, toute optimisation est possible
pointeurs/registres, fonction intrinsics (SSE2 etc), threads etc tout est envisageable, mais doit rester portable (linux et windows, restons en là)
les shaders peuvent aussi être proposés.
 
Le code simple de base est présenté ci dessous, Bon courage à tous.
 
l'exemple proposé ici réalise un filtrage sur une image en NIVEAUX DE GRIS (donc, pas en RGB ou autre, c'est juste sur un calque), ligne par ligne, de la gauche vers la droite, il s'agit en fait d'un filtrage passe bas (lissage des contours) assymétrique couramment utilisé en traitement d'image.
 
dans le code proposé, les calculs sont effectués sur une image de taille _NBrows par _NBcolumns
le résultat final est stocké dans le tableau 'outputFrame', en entrée on a le tableau outputFrame (résultat de la frame précédente par exemple que l'on va écraser après calcul), l'image d'entrée 'inputFrame' (de même taille que la sortie) et une autre image de paramètres 'window' de même taille que l'image de sortie), une variable temporaire 'value' permet d'inclure dans le calcul du pixel courant, le résultat du calcul du pixel précédent.
 
TOUS LES CALCULS SONT EFFECTUES EN TYPE DOUBLE ou en FLOAT, mais pas un autre type introduisant une perte de précision, ici, j'ai tout mis en double,mais tout peut être passé en float !!!
 
voici le code non optimisé :
 
%%%%%%%%%%%%%%%%%%%%%%%%%%
 

 
%%%%%%%%%%%%%
 
merci pour vos contributions, pour toute les personnes intéressés par l'optimisation de code et les novices désireux de progresser (moi compris bien entendu, je ne suis que programmeur amateur, mais j'ai bien envie de progresser)
 
++
ALex : Smile

c'est dingue ce que les gens inventent pour faire faire leur boulot par les autres...

skoi l'interêt du double pour du traitement d'image ?

comme tu utilises des tableaux le codes sera tres probablement vectorisé (suivant le compilateur) et dans cette exemple minimal on pourra difficilement faire mieux
sinon, avant de parler optimisation mieux vaut apprendre à (bien) programmer, c'est ca le plus important

on a le droit de mettre de l'assembleur ?

 
salut, remarque intéressante mais pas très applicable pour ce sujet, je programme en amateur, j'ai fait ce code de base tout simple et c'est lui qui m'a amené à me poser ces questions d'optimisation, après tu penses ce que tu veux, le but de ce thread est plutôt à vertut pédagogique pour tout le monde
 
cordialement
   Alex

 
 
oui oui, tous les droits, même en assembleur, perso, j'ai essayé avec les fonctions sse2 avec le header intrinsics.h mais je ne devais pas bien m'y prendre, ca ramait plus...la quiche lol

 
je travaile en double pour garder la précision des calculs, dans mon prog, ce filtre est appelé de multiples fois à la suite, donc il y a accumulation d'erreur donc attention aux arrondis.
Mais vous pouvez proposer des versions qui travaillent sur les entiers, mais le problème sera la perte de précision...car ce genre de calcul pour un intervalle de valeu de 0 à 255 c'est un peu juste, faudrai bien augmenter l'intervalle en entier (genre multiplier les valeurs d'entrée par un facteur X pour bosser sur de grands intervalles de valeur style de 0 à 1024 ou plus)  et recalibrer juste avant l'affichage...mais là, je suis curieux de connaotre une méthode fiable pour y parvenir, tu as une idée la dessus?
 
++

moi je repete qu'il n'y a rien à optimiser

 
salut, il me semble que si, déjà rien qu'en "forcant " des données à être placée dans les registres, on peut gagner
 
j'ai remplacé la déclaration de  

par  

comme c'est une variable temporaire appellée à chaque tour de boucle, on gagne apparemment un temps fou avec cette méthode
=> là, j'ai eu un facteur 2 en gain de vitesse, c'est con, mais ca marche déjà bien
 
après faudrait voir pour le multithread si on peut y gagner, 2 threads par exemple, et chacun calcule une moitié d'image, mais là, je ne connais pas trop
 
sinon, j'ai essayé les fonctions sse2 avec le header

les fonctions qui codent directement en assembleur pour les pentium4 et équivalent, mais c'est relou comme c'est lent, je doit po bien jouer avec ces méthodes...je fais trop de transfert de mémoire et doit surcharger les registres dispo du processeur,  
voila un appercut:, mais le gain en vitese enst de 1/2...2 fois plus lent, j'ai raté le truc lol
 
 

 
ca c'est le boulot du compilateur, d'ailleur ton mot clef register n'est pratiquement plus utilisé parce que c'est inutile, qui mieux que le compilateur peu l'utiliser à bon escient ?
 
 

 
on appel ca parallelisé, la seul condition c'est que chacun des deux (ou +) flots de calcul ne dépende pas du résultat de l'autre, et chose importante, tu gagne uniquement sur une machine à architecture parallele (multi proc ou autre)
 
 
en gros, laisse faire le compilateur, avec gcc4 (et les options qui vont bien, en ciblant l'arhcitecture si tu veux) par exemple tu auras de bon resultat rien qu'avec la vectorisation des boucles, d'ailleur si j'était toi j'utiliserais des constante pour _Nbrows et l'autres
 
et puis apres ca sert a rien de foutre en l'air la portabilité et la maintenabilité du code pour gagner 3 cycles...

est-ce que ça s'exprime sous forme matricielle ?
 

 
en asm avec du SSE si, beaucoup, mais pas en double

(surtout vu la linéarité du traitement...)

passe en float et utilise altivec ou SSE selon ta plateforme
sinon le reste c'est du branlache de mouche

 
bin le programmeur ? Maintenant c'est sur que c'est un relicat des temps passés, les compilos se demerdent tres bien maintenant
 
 

 
Il ne faut pas non plus cracher systématiquement sur l'optimisation. La dans son cas, il y a bcp a gagner, en utilisant les instructions vectorielles d'un 3dnow / SSE et en ajoutant un petit prefetch kivabien
 
edit : merde, j'avais pas vu la reutilisation de value, ca va etre penible ca par contre

et gcc par exemple, il ne serait pas se demerder avec les options -mcpu=... et -mfpmath=... ? si on lui donne toutes les infos je vois pas pourquoi il ne le ferais pas

gcc il sais pas vectoriser du code de maniere automatique. Je peut même te dire que PERSONNE ne sait faire. Seul VAST fournit un semblant d'autovectorization qui reste imaintenable
 
Apre j'ai juste passer ma these sur ce genre de problemes mais je dis peut etre du käkä

y'avait VectorC aussi

VectorC, C// et j'en passe ... ils restent tous relativement peu efficace   des que ton code diverge de ce qu'ils ont appris à vectoriser.
 
En outre, le compilo ne pourra JAMAIS detecté les changements de structures et d'algorithmes à appliquer à un problemes donné pr le rendre efficace une fois vectoriser

j'ai aucun moyen de tester (pas de gcc4) mais tu ne vas pas me dire qu'il ne saurais pas verctoriser cette simple boucle qui parcour une matrice, j'entends par la dérouler la boucle (sucré tout ce code parasite) pour avoir que les opération fpu consécutives et bénéficier à fond de l'effet pipeline

http://gcc.gnu.org/projects/tree-s [...] vectorizab

Merci pour ce lien
Je sais que gcc sait dérouler les boucles et tout mais d'experiences, ca suffit rarement. Generer les commandes de prefecth adequats, determinés les bonnes tailles de blocs, c'est deja plus compliqué.
 
Et la vectorization c'est aussi PLUS que de simples boucles

en gros, quel serait le gain ?

Sur mon G5, pour des float , j'ai jamais dépasser les x2 en mode auto-vector alors que a la main j'atteins du x3.89. Pour les types entiers 8bits j'atteinds le x7 et le x13 a la main ...
 

oui, dans ce cas ca peu valoir le coup  

Pour comparer les vitesses de calculs, j ai toujours sous la main un petit programme. Sans optimisation, voici le résultat (les chiffres sont en seconde pour 100M opérations, sizeof(double)=sizeof(longlong)):

 
La différence de vitesse est très claire.
A noter que parfois le réencodage de fonctions peut être plus rapide que la version contenue dans math.h, par ex. frexp (standard, lent) et epR (extrait la partie exponentielle du nombre, plus rapide). Mon ordi ne supporte pas l opération fma (réécrire MulAdd est plus rapide). Sur mon ordi (AMD) le type float n est pas plus rapide que double, seulement plus précis. Sur les architectures Intel les types réels sont horriblement plus lents (j ai pas d explications à ça, mais un test m a montré que j obtenais 25 FPS sur une démo graphique avec calcul type double pour AMD 1,666G et 24 FPS pour Intel 2.5G).
 
Autre chose: Les opérateurs << et >> sont plus rapides que la mutiplication/division entière, ou pour certaines architectues que la récupération par example de bits de poid fort d une autre manière (unions par ex.).
 
En ce qui concerne la précision des calculs, on s interesse à la perte de bits. Pour les entiers la perte survient lors de l opération diviser. Pour les réels elle survient notamment lors de l addition/soustraction.
 
Par example pour calculer la moyenne entre deux nombres, la perte est d un demi bit minimum, de 1 bit maximum, dans les deux cas.
L utilisation d un entier de taille apropriée peut par conséquent être même plus précis et plus rapide que l utilisation de double.
 
Dans la rapidité, entre en compte aussi la taille du type entier. Le type int correspond généralement à la taille d un mot machine. Il est plus rapide d utiliser un mot machine que plusieurs, et sur certaines (beaucoup?) de machines utiliser moins d un mot nest pas plus rapide (c est dû aux caches CPU).
 
Reste ensuite à considérer la taille mémoire utilisée. Lorsque sizeof(int)<sizeof(double), c est a dire sur les machines 32 bits (les plus courantes...?), l algo utilise moins de mémoire.
 
Je recommanderais donc l utilisation du type int, plutot que double, sur la plupart des machines. On peut enchaîner 24 fois le filtre sans grande perte de précision. Si l image finale doit être stockée en JPEG on peut même probablement aller jusqua 48 fois. Pour plus de précision, le type long long reste plus rapide que double.
 
L utilisation de register n est pas recommandée, sauf dans le cas ou on a besoin d utiliser à la fois une compilation optimisante (gcc: O3, renameregister) et non optimisante (O0).
 
Un example de programme de filtre graphique lent est ImageMagick. Il utilise des doubles en interne, ça ne rends pas forcément les calculs plus précis mais certainement plus lents. Ça ne l empêche pas d être très pratique à utiliser vu la grande variété de filtres et l utilisation en ligne de commande aussi bien qu en librairie.
 
En conclusion, il n y a rien à optimiser dans ce code. Il est parfaitement rapide quand on a le temps.
 
 

 
oui, passer en float , j'était assez partant, on conserverait suffisamment de précision.
sinon, en SSE2, on put aussi effectuer 2 opérations en parrallèle sur les doubles...et donc 4 sur les float ce qui peut être vraiment sympa
 
pour plus de facilité, on m'a conseillé d'utiliser les fonctions intrinsics, mais bon, j'ai des soucis d'efficacité à e niveau là, ca a tendance à plus ramer que la version de base...
quelle est la bonne méthode à appliquer, de quelle manière bien jouer avec le prefectch? cf par exemple en partant du code que j'ai déjà proposé avec les  intrinsics? car pour cette méthode là, je débute
++

 
 
j'ai déjà posté un exemple en utilsant les sse2, avec les fonctiosn intrinsics, malheureusement, la méthode ne doit pas être la bonne car ca rame plus...le paradoxe...je pense que je fais trop de transferts mémoire, tu parles de  prefetch "kivabien", as tu des infos la dessus, le prefetch, je connais pas

 
 
quelles manips effectue tu donc à la main?
 
perso, pour ce code, je ne manip que des tableaux 2D, y atil un moyen de se déplaver plus vite dans ces tableaux? j'ai essayé en manipulant des pointeurs mais l'effet inverse est arrivé.
 
en fait, il faudrait idéalement que les adresses des pixels soient directement dans les registres, que les valeurs de pixels soient directement transférées au proc pour calcul et directement reposé en mémoire, sans trop prendre de temps de transfert mémoire etc...là, j'avoue que j'ai a apprendre, je ne connais que le C++ de base

prefetch, c'est une instruction qui dit (grosso merdo) au CPU "Hé jean paul, je vais bientot avoir besoin des infos se trouvant a l'adresse [machin], si t'as que ca a faire ca serait sympa de les mettre en cache". Bref, si c'est utilisé correctement ca augmente tes probabilités de lire en cache plutot qu'en memoire, d'ou joli gain de perf

 
effectivement, un 'pointer-style' code est souvent mois optimiser qu'un 'array-style', c'est déconseille
 

 
le plus important c'est avant tout qu'il y ai le moins d'acces à la mémoire (optimiser l'utilisation du cache) pendant le parcour du tableau, faut acceder aux élément de la matrices dans l'ordre dans lequel ils sont ordonnés en mémoire (en C++, les tableaux multidimensionnels sont ordonnés en ligne) et c'est ce que tu fais ici
essayes l'inverse (avec un tableau suffisament grand), tu verras la différence

 
 
okay, c'est bien ce que j'avais compris alors, mais pour faire du prefecth, tu utilise les intrinsics ou il y a d'autres fonction plus portables?

heuh bin t'as l'asm inline mais pour la portabilité, brosse toi fort

 
heu, là, j'ai du mal à te suivre, tu dis donc que mon code traite effectivement ligne par ligne et que c'est bien ou pas, si je tente dans l'autre sens, ca fait quoi? plus ou moins lent?

plus lent si tu fais
 

 
apres suivant la taille tu tableau (et en particulier des lignes, des derniers dimension en générale), la différence est plus ou moin sensible

 
 
okai, alors c'est parfait enfin, dumoins, c'est moins pire
 
sinon, question, les calculs en float seraient ils plus rapide? un collègue m'a dit le contraire mais ca m'a paru bizarre car les float ont 2*moins de données non?

J'ai pas testé mais tu peux essayer ca:
 

c'est pire, on l'a déja dit faut s'attendre à moins d'optimisations si on parcourir un tableau avec un pointeur
 
et accessoirement faudrais controller les allocations dynamiques