Adressage de matrice, performances

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Adressage de matrice, performances

Sebxoii

I've made a huge tiny mistake.

Salut à tous,

J'ai implémenté il y a peu un décodeur audio et je me suis trouvé face à un problème de performance. Mon patron m'a conseillé de remplacer mes adressages de matrices/tableaux (tab[x][y]) par un pointeur que j'incrémente (ptr+xx).

J'ai trouvé cela étonnant, mais comme on en apprend tous les jours...Bref, j'ai quand même décidé de tester cela avant de modifier 20.000 lignes de code.
Code de test :

Code :

#include <stdio.h>
#include <time.h>
#define SIZE 10000
float tab[SIZE][SIZE];
float tab2[SIZE][SIZE];
int main(void)
{
int i, j;
clock_t start, stop;
/* Test 1 */
start = clock();
for(i = 0; i < SIZE; i++)
{
for(j = 0; j < SIZE; j++)
{
tab[i][j] = 0;
}
}
stop = clock();
printf("Temps t1 : %d\n",(stop-start));
/* Test 2 */
float *ptr = (float*)tab2;
start = clock();
for(i = 0; i < SIZE; i++)
{
for(j = 0; j < SIZE; j++)
{
*ptr++ = 0;
}
}
stop = clock();
printf("Temps t2 : %d\n",(stop-start));
return 0;
}

Résultat des courses en optimisation -O3 :
T1 = 531
T2 = 532

Ai-je loupé quelque chose ou est-ce que les deux modes d'adressage se valent ?

Merci d'avance.

Cordialement,
Sébastien.

Publicité

jagstang

Pa Capona ಠ_ಠ

tu as raté quelque chose en effet, car c'est strictement la même chose. Ton patron voulais sans doute parler de l'allocation mémoire :

# #define SIZE 10000
#
# float tab[SIZE][SIZE];
# float tab2[SIZE][SIZE];

regarde du côté de malloc() et de free()

---------------
What if I were smiling and running into your arms? Would you see then what I see now?

Sebxoii

I've made a huge tiny mistake.

Au niveau de l'allocation des deux tableaux, il s'agit juste d'un exemple ici.

Mon patron me parlait bien de la vitesse d'adressage.

Pour en revenir à la question de base, il me semble que la seule chose que fasse le compilateur lorsqu'il tombe sur des [][] est de les remplacer par l'addition correspondante par rapport à l'adresse de base du tableau/matrice, c'est ça ?

Edit : En fait son argumentation tenait au fait que tab[x][y] implique une multiplication et deux additions à chaque passage de boucle (tab + (x * size + y)), alors que ptr++ n'implique d'une incrémentation.

Mon autre patron argumenta qu'avec les optimisations du compilateur, cela ne devrait pas entrer en ligne de compte.

Edit2 : Effectivement, en réalisant le test sans optimisation :
T1= 1031
T2= 797

Donc j'imagine qu'au final il est vrai que ptr++ est plus rapide que tab[][], mais qu'une fois les optimisations du compilateur activée, la différence est alors infime/nulle.

Message édité par Sebxoii le 13-07-2009 à 11:48:46

Joel F

Real men use unique_ptr

Encore des FUDs ... L'acces par pointeur lineaire est la pire des façons vu qu'elle va pas plus vite que celle en [][] et est plus chiante à utiliser.

cf ces sujets :
http://forum.hardware.fr/hfr/Progr [...] 9389_1.htm
http://forum.hardware.fr/hfr/Progr [...] 0227_1.htm

En gros, un tableau 2D ca s'alloue via un bloc contigue + 1 tableau de pointeur sur ligne. En terme de code résultant, y a pas plus de *+ qu'avec l'autre vu qu'elles sont précalculées.

cf aussi : http://codepad.org/nDy8z2iG

Autre chose, le "temps d'adressage" on s'en fout. C'est le respect des caches qui est important.Apres, regarde du coté du déroulage de boucle, fusion de boucle, jam & roll loop. Si ca suffit pas SSE2+ ou Altivec en fonction du Proc et oepnMP si tu as plus de 1 coeur

Message cité 1 fois
Message édité par Joel F le 13-07-2009 à 12:40:47

Elmoricq

Modérateur

Pour les problèmes de performances, plutôt que de faire des tentatives hasardeuses pour tenter de débusquer le problème, je préconiserais plutôt l'utilisation d'un profiler (prof ou gprof pour les plus basiques, mais il y en a d'autres, par exemple analyzer/collect sous Sun).

Ça permet de faire des statistiques sur les appels, de voir très simplement où se situent les goulots d'étranglement, et de cibler les optimisations là où elles comptent vraiment.

Message cité 1 fois
Message édité par Elmoricq le 13-07-2009 à 15:27:33

Joel F

Real men use unique_ptr

PAPI aussi

Sebxoii

I've made a huge tiny mistake.

Merci pour les infos.

Joel F a écrit :

Apres, regarde du coté du déroulage de boucle, fusion de boucle, jam & roll loop. Si ca suffit pas SSE2+ ou Altivec en fonction du Proc et oepnMP si tu as plus de 1 coeur

J'ai jamais entendu parler d'aucun de ces termes/techniques, donc je vais essayer de jeter un oeil et voir ce que je peux en faire. Je suis ingénieur électronique débutant donc les optimisations ~~avancées~~, ça me passe un peu haut dessus de la tête. xD

Elmoricq a écrit :

Ça permet de faire des statistiques sur les appels, de voir très simplement où se situent les goulots d'étranglement, et de cibler les optimisations là où elles comptent vraiment.

Oui j'ai déjà fait ça avec valgrind (callgrind), mais j'arrive à un point où je n'ai pas une fonction qui prend plus de 3-4% de la puissance de calcul...

Merci pour vos conseils en tout cas.

edit :

Citation :

En gros, un tableau 2D ca s'alloue via un bloc contigue + 1 tableau de pointeur sur ligne. En terme de code résultant, y a pas plus de *+ qu'avec l'autre vu qu'elles sont précalculées.

Cela est-il vraiment gênant de déclarer le tableau de pointeur sur une ligne, et d'allouer à chaque pointeur une zone mémoire indépendante ?

edit2 : Bon, évidemment, c'pas bon pour le cache.

Message cité 1 fois
Message édité par Sebxoii le 13-07-2009 à 16:12:58

Joel F

Real men use unique_ptr

Sebxoii a écrit :

edit2 : Bon, évidemment, c'pas bon pour le cache.

Voila

Le cache c'ets le truc qui fait la difference entre un code et un code efficace, parfois avec un facteur 10.

Sebxoii

I've made a huge tiny mistake.

J'aurais ptet du regarder plus attentivement le relevé des "cache miss" de Valgrind. Je jetterai un oeil demain matin.

N'ayant aucune idée des ordres de grandeur, à partir de combien de % de cache miss peut-on considérer qu'il y a un problème à ce niveau ?

Message édité par Sebxoii le 13-07-2009 à 18:24:56

Joel F

Real men use unique_ptr

ca depend. En gros, vire les cache misses des grosses boucles le reste tu t'en tapes mais cachegrind te file tout. Ensuite rebench et affine.

Publicité

Sebxoii

I've made a huge tiny mistake.

J'ai été occupé hier, donc j'ai reporté Valgrind à ce matin, résultats :

Code :

==6052==
==6052== I refs: 1,345,276,877
==6052== I1 misses: 874,503
==6052== L2i misses: 2,341
==6052== I1 miss rate: 0.06%
==6052== L2i miss rate: 0.00%
==6052==
==6052== D refs: 582,629,777 (455,880,919 rd + 126,748,858 wr)
==6052== D1 misses: 2,719,251 ( 1,911,036 rd + 808,215 wr)
==6052== L2d misses: 19,630 ( 3,039 rd + 16,591 wr)
==6052== D1 miss rate: 0.4% ( 0.4% + 0.6% )
==6052== L2d miss rate: 0.0% ( 0.0% + 0.0% )
==6052==
==6052== L2 refs: 3,593,754 ( 2,785,539 rd + 808,215 wr)
==6052== L2 misses: 21,971 ( 5,380 rd + 16,591 wr)
==6052== L2 miss rate: 0.0% ( 0.0% + 0.0% )

Je ne suis pas spécialiste mais j'imagine qu'avec moins de 1% de misses, ça ne doit pas influer beaucoup sur les perfs.

Merci pour les conseils en tout cas, au moins je n'aurais pas de regrets en me disant que j'aurais pu remplacer mes [][] par des pointeurs ou supprimer les cache misses.

Message édité par Sebxoii le 15-07-2009 à 10:10:34

Joel F

Real men use unique_ptr

Ca me parait pas mal.
Est-ce pour juste les boucles cirtiques ou toutes l'appli ?

Apres si t'as trjrs des pb de perfs y a plein d'astuce que je peut te donner mais faudrait que je voit la forme général de tes calculs.

Sebxoii

I've made a huge tiny mistake.

Toute l'appli.
Et j'ai fait le tri par fonction, il n'y en a aucune avec un % de cache miss incroyablement haut par rapport aux autres.

Malheureusement pour les soucis de perfs, je suis en stage et il ne me reste que 3 semaines pour m'en occuper (d'autant plus qu'il me reste la moitié de l'appli à porter en fixed-point...). Mes patrons ont donc jugé que ce serait difficile d'obtenir une appli assez optimisée pour tourner sur un ARM et je vais donc passer le temps qu'il me reste à rédiger mon rapport.

Pour des raisons de copyrights, je ne peux pas te montrer mon code source, et vu que le standard AAC est payant, je vois mal comment t'indiquer la forme des calculs.

Merci pour ton aide.

Taz

bisounours-codeur

Sinon vu que ta matrice elle est static, tu supprimes ta boucle de mise à 0 et c'est encore plus rapide :tirelangue

Sebxoii

I've made a huge tiny mistake.

J'ai quand même du bol que sur 40.000 lignes de code, je n'ai que des boucles de mise à zéro.

FORUM HardWare.fr

Programmation

Adressage de matrice, performances

Sujets relatifs
produit des matrice en vba	php/mysql : performances sur une même machine
[PHP] Matrice php	[C] Matrice de structures : probleme de remplissage
Afficher les lignes d'une matrice	SQL Server Reporting Services - Utilisation d'une table matrice
Réalisation de la somme parallèle des éléments d’une matrice: openmp	[Web] Outil d'analyse de performances d'un site
Affichage d'une matrice	matrice carré dynamique? (résolu)
Plus de sujets relatifs à : Adressage de matrice, performances

Page générée en 0.053 secondes