Discussion :

[Heimdall]

Salut,


Je crois que tout est dans le titre, je me demande si je dois, pour des raisons de performances (utilisation du cache), plutôt utiliser une structure contenant des tableaux, ou des tableaux de structures.

Déjà, est-ce qu'il y a des arguments généraux (indépendants du problème considéré) qui iraient vers l'une ou l'autre des deux solutions, et pourquoi ?

Mon problème consiste a calculer des formules mathématiques sur des fonctions à 2 dimensions, genre f(x,y), g(x,y), h(x,y). Par exemple f(x,y) = h(x,y)*g(x,y).


Est-il plus malin de faire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
struct ma_grille
{
 double f;
 double g;
 double h;
};
 
 
int i, j, ij;
int nx, ny;
 
nx = 100;
ny = 100;
 
 
struct ma_grille *mg = malloc((nx+1)*(ny+1)*sizeof(*mg));
 
// initialisation de f, g et h
//...
//
 
// calcul
for (i=0; i < nx+1; i++)
    {
    ij = i + j*(nx+1);
    mg[ij].f = mg[ij].g * mg[ij].h;
    }
 
free(mg);

ou bien :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
struct ma_grille
{
 double *f;
 double *g;
 double *h;
};
 
 
 
int i, j, ij;
int nx, ny;
 
nx = 100;
ny = 100;
 
 
 
struct ma_grille mg;
 
mg.f = malloc((nx+1)*(ny+1)*sizeof(*mg.f));
mg.g = malloc((nx+1)*(ny+1)*sizeof(*mg.g));
mg.h = malloc((nx+1)*(ny+1)*sizeof(*mg.h));
 
// initialisation de f, g et h
//...
//
 
// calcul
for (i=0; i < nx+1; i++)
    {
    ij = i + j*(nx+1);
    mg.f[ij] = mg.g[ij] * mg.h[ij];
    }
 
 
free(mg.f);
free(mg.g);
free(mg.h);

[souviron34]

indépendants du problème considéré je ne crois pas...

Par contre, suivant le problème :

si il peut arriver que l'on modifie g ou h tout en gardant f constant (ou h modifé et f et g constants, ou toute autre combinaison), alors la 2ième solution est mieux..


Note : ton exemple (dans un cas comme dans l'autre) d'accès à la cellule est faux (j n'est assigné/calculé nulle part).

[Heimdall]

Salut et merci de ta réponse.

En effet, j'ai fait des examples faux sans faire exprès, désolé...

J'ai fait quelques tests pour voir ce que ça donne... j'ai défini deux structures :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
struct mesh1
{
	double f;
	double g;
	double h;
};

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
struct mesh2
{
	unsigned int nx;
	unsigned int ny;
 
	double *f;
	double *g;
	double *h;
};

Et pour chacune des structures, j'ai codé une petite fonction qui calcule le produit f=g*h pour tous les points de la grille.

pour mesh1 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
void mesh1_compute(struct mesh1 *m, unsigned int nx, unsigned int ny)
{
unsigned int i;
	for (i=0; i < (nx+1)*(ny+1); i ++)
        {
		m[i].f = m[i].g * m[i].h;
        }
}

pour mesh2 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
 
void mesh2_compute(struct mesh2 *m)
{
int i;
for (i=0; i<(m->nx+1)*(m->ny+1); i++)
     {
     m->f[i] = m->g[i]*m->g[i];
     }
}

J'ai fait ça pour des grilles de tailles différentes :

nx=ny = (512^2, 1024^2, 2048^2, 4096^2, 8192^2)

et a chaque fois j'ai mesuré le temps d'execution de chaque fonction compute(), que j'ai executé 10 fois, pour faire une moyenne du temps d'execution de ces fonctions.


Le résultat ne présente pas d'ambiguité. Le temps moyen de la méthode 1 (tableau de structures) est toujours plus long que celui de la méthode 2 (structures de tableaux). Le rapport des temps entre les deux méthodes ne dépend que faiblement de la taille de la grille.

En revanche, il dépend assez fortement de la taille de la structure mesh1.
Ainsi pour une structure mesh1 présentée au dessus, la méthode 1 est environ 2 fois plus lente que la méthode 2. Tandis que pour une structure mesh1 plus grosse :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
struct mesh1
{
        double f;
        double g;
        double tmp[3];
        double h;
};

la méthode 1 est 2-3 fois plus lente ! En mettant un tmp[10] j'ai un facteur 6-7 entre les deux méthode...


J'en conclue donc que la méthode des structures contenant des tableaux est beaucoup plus avantageuse. J'imagine que c'est parce que plus de points de la grille sont chargés dans le cache dans ce cas, alors que dans la première méthode, il faut charger des structures entières dans le cache et forcément c'est plus gros donc on fait des aller-retours cache/ram qui ralentissent l'execution...

A+

[souviron34]

remplace par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
void mesh1_compute(struct mesh1 *m, unsigned int nx, unsigned int ny)
{
unsigned int i;
 
	for (i=0; i < (nx+1)*(ny+1); i ++, m++)
        {
		m->f = m->g * m->h;                         
        }
}

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
void mesh2_compute(struct mesh2 *m)
{
int i;
double *f=m->f, *g=m->g, *h=m->h ;
 
for (i=0; i<(m->nx+1)*(m->ny+1); i++,f++,g++,h++)
     {
        f = h*g;
     }
}

et compare..

[Heimdall]

remplace par :

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
void mesh2_compute(struct mesh2 *m)
{
int i;
double *f=m->f, *g=m->g, *h=m->h ;
 
for (i=0; i<(m->nx+1)*(m->ny+1); i++,f++,g++,h++)
     {
        f = h*g;
     }
}

et compare..

J'imagine que tu voulais plutôt dire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
*f = *h * (*g);

Résultat des 10 execution de *_compute() pour tes nouvelles méthodes et pour les structures suivantes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
struct mesh1
{
        double f;
        double g;
        double tmp[10];
        double h;
};

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
struct mesh2
{
        unsigned int nx;
        unsigned int ny;
 
        double *f;
        double *g;
        double *h;
};

temps en secondes, grille 8192^2. Méthode 1 à gauche, et méthode 2 a droite.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
    4.247373      2.14971167
  4.76580338     0.853740388
  4.11490201     0.855233308
  4.08537824     0.847526236
  4.03221669     0.849687077
  4.11114667     0.855027072
  4.16237639     0.853272092
  4.06561274     0.839831005
  4.09081166     0.848389385
  4.06501795     0.855185667

je veux bien que tu m'explique la différence physique entre mes routines et les tiennes ?

Avant, avec mes méthodes, j'avais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
   4.9412316     0.635360499
  3.96521252     0.639802781
  3.99971396     0.639220618
  3.96497992     0.639379942
     3.96973     0.638121426
  3.94750979     0.632379168
  3.98541909     0.650921249
  4.05364455     0.633509299
  3.95744846     0.634653635
  3.93342002     0.635777603

[Sve@r]

Salut Heimdall

En dehors du problème de performance, qui ne dépend pas que du choix entre "tableau de structures" ou "structure de tableaux", il y a un problème plus général : celui de la façon dont les autres comprendront quand ils reliront ton code. Un tableau de structures sous-entend que tu dois traiter plein de petits éléments tous identiques. Par exemple ce serait utile si tu devais gérer plein de dates.
Alors qu'une structure de tableaux sous entend que tu dois gérer un seul élément contenant des datas identiques. C'est par exemple le cas d'une matrice.
Bref quand on réfléchit à la meilleure façon de coder une notion, il ne faut pas penser "que" performances mais aussi relecture, évolutivité, coopération. Comment feras-tu si tu dois un jour transmettre ta matrice via support externe (fichier ou autre) ? Si tu as un gros objet ce sera peut-être plus facile que si tu en as plein de petits.

Et en plus, question performance, les compilateurs sont assez forts pour trouver eux-même comment optimiser donc finalement t'as pas vraiment à te préoccuper de ça...