performance : structure de tableaux ou tableau de structures

**Heimdall** · 02/04/2011, 12h49

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** · 02/04/2011, 15h44

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** · 02/04/2011, 16h10

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** · 02/04/2011, 16h24

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** · 02/04/2011, 16h37

Envoyé par souviron34

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** · 02/04/2011, 17h33

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...

**Heimdall** · 02/04/2011, 17h48

Salut et merci de ta réponse

J'ai bien conscience de la signification "sémantique" différente d'une méthode ou de l'autre... je suis moi même très sensible à l'équilibre, dans mon code, entre la maintenabilité, la lisibilité et l'efficacité.

Mais en fait j'ai quand même à me soucier de la performance... je m'explique : Je fais du calcul scientifique assez intensif (des programmes qui peuvent durer plusieurs semaines sur calculateur parallèle avec quelques dizaines de processeurs) et donc un gain de temps d'un facteur 6 sur des boucles ça m'intéresse

L'exemple simple que j'ai codé cet après midi montre des facteurs importants et j'ai pas l'impression (mais je demande qu'à me tromper) que le compilateur (gcc en l'occurence) puisse m'inverser la tendance.

J'ajoute que je pense que je préfère mieux réfléchir en amont en optimisant le code, plutot que d'écrire un code qui sera d'avantage compilateur-dépendant.

Concernant les écarts de performance entre les deux méthodes, j'attribue ça aux allers retour cache/mémoire ram, mais je suis nul en hardware, si quelqu'un se sent de m'expliquer exactement ce qui se passe :-) Je comprends pas non plus vraiment les propositions de changement de Souviron34

**souviron34** · 02/04/2011, 18h43

Envoyé par Heimdall

Je comprends pas non plus vraiment les propositions de changement de Souviron34

C'était pour mieux visualiser ce qui se passe..

Envoyé par Heimdall

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

il n'y en a pas, voir plus haut...

C'est juste que dans un cas tu as :

3 fois (1 mutiplication + 1 addition) pour le calcul d'adresse

alors que dans l'autre tu as 3 additions..

Sur des millions, tu commences à voir le coût des multiplications..

**Heimdall** · 04/04/2011, 12h20

re-salut,

Dans le principe, comment marche le chargement en cache de manière générale :

si j'ai un code qui doit accéder à une grille de 5 variables : a,b,c,d, on pourait dire que faire un tableau de structures :

Code :

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

1
2
3
4
5
 
struct mastruct
{
double a,b,c,d;
};

et que je veux faire souvent :

tmp = a*b + d*c; //par exemple

On pourrait se dire qu'avec un tableau de 'mastruct', on va charger une série de 'mastruct' en cache et les élements 'a', 'b', etc... seront accessibles rapidement.

Avec une structure de tableaux,

Code :

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

1
2
3
4
5
 
struct mastruct
{
double *a,*b,*c,*d;
};

est-ce que les tableaux 'a', 'b', 'c' et 'd' vont etre "équitablement" (ou presque) chargés en cache de sorte que a*b + c*d se fasse également rapidement ?

Bref, dans un cas et dans l'autre, qu'est-ce qui se passe vraiment au niveau du chargement en cache ? ça doit dépendre des machines... mais en regle générale ?

Merci :-)

**souviron34** · 04/04/2011, 13h05

Je pensais que ma démonstration t'avait ouvert les yeux..

Le problème principal n'est pas un problème de cache mais de calcul...

Tes mesures montrent (et c'est courant et normal) qu'une multiplication coûte 3 fois plus cher qu'une addition... c'est tout

Maintenant, le cache on s'en fiche un peu, car à moins que tu ne t'occupes de Téra-octets, même une matrice 5000*5000 de nombres double-précision tient dans une mémoire "classique".. Sous une forme ou sous une autre..

Et le "swap" peut avoir des inconvénients, soit, mais les "strcutures" sont peu importantes..

C'est effectivement l'intensité d'usage de telle ou telle partie qui va le garder en mémoire vive..

Mais donc il faudrait connaître réellement le problème considéré pour pouvoir aider plus..

Il n'y a pas de réponse absolue...

**diogene** · 04/04/2011, 13h26

@souviron34 :
je crois que la question évoquée ne concerne pas l'utilisation de la mémoire virtuelle, donc des échanges mémoire vive<->disque, mais de la mémoire cache (externe ou interne au processeur) donc des échanges mémoire vive<-> mémoires cache<->unité de calcul

**Heimdall** · 04/04/2011, 13h40

oui en effet diogene a raison, c'est ça qui me préoccupe, j'avais pas compris que souviron34 parlait d'autre chose (?)

**souviron34** · 04/04/2011, 14h36

ok, mais alors comme dit Sv@r, s ceci est sensible alors c'est que l'algo est mal conçu...

Disons que ce ne devrait pas être un problème..

**Heimdall** · 04/04/2011, 15h27

Bof...

Prendre l'exemple d'un ensemble de particules qui bougent. Naturellement je dirais, on a envie de faire ça :

Code :

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

1
2
3
4
5
6
7
8
9
 
typedef struct _particle
{
double r[3];
double v[3];
} Particle;
 
 
Particle particles[100];

Physiquement, on a un ensemble de particules...
Informatiquement, on a un tableau de particules...

je trouve ça facile à lire...

Par contre il est plus efficace de faire :

Code :

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

1
2
3
4
5
6
 
typedef struct _particles
{
double *r[3];
double *v[3];
} Particles;

c'est peut-etre moins facile à lire et moins identique au sens physique ("groupe de particules") mais après test... ça marche mieux.

**souviron34** · 04/04/2011, 16h14

oui, et même il (peut) y a beaucoup plus efficace...

(suivant certaines hypothèses)

mais beaucoup moins facile à lire

(mais on en revient à la vitesse).

Mais pour en revenir au sujet :

les "goulots" dont tu parlais au début sont dûs aux vitesses des bus et au capacités des différentes parties indiquées par diogene..

Je ne pense pas que l'une ou l'autre structure, à part la vitesse d'accès (dont je parlais plus haut), puissent être suffisamment "découpée" pour influer sur ce qui passera ou non dans le cache...

Après ça dépend du problème bien entendu..

Mais à ce compte-là, si on n'utilise réellement qu'une partie de la structure, pourquoi s'emmerder à stocker le reste ?

(et je rajouterais que si on a à se soucier de la manière dont se passent les choses entre le cache et le reste, c'est quand même un problème de fond de l'algorithme : du point de vue optimisation, les options spécialisées des complateurs sont faites pour ça, et sont adaptées, alors que si ce progamme particulier doit gérer son approche d'un cache, il est pas mal.... travesti)

**Heimdall** · 04/04/2011, 16h26

re,

je suis curieux de connaitre la façon qui est beaucoup plus rapide (et les hypothèses qui vont avec) si ça te vas de me l'expliquer

Je ne pense pas que l'une ou l'autre structure, à part la vitesse d'accès (dont je parlais plus haut), puissent être suffisamment "découpée" pour influer sur ce qui passera ou non dans le cache...

je comprends pas trop ?

J'ai mis en pièce jointe le code et makefile (faire juste make, sous linux) qui teste tout ça. Si vous avez le courage de me dire pourquoi l'un est plus rapide que l'autre....

Pour ce qui est du compilateur, je compile en -O2 et j'ai quand même un écart de perf assez grand entre les deux modèles...

**souviron34** · 04/04/2011, 18h12

Envoyé par Heimdall

je suis curieux de connaitre la façon qui est beaucoup plus rapide (et les hypothèses qui vont avec) si ça te vas de me l'expliquer

Une autre fois, mais cela dépend aussi si on veut optimiser la mémoire, et si il y a des coordonnées qui reviennent (modèles numériques réguliers) ou si tout est toujours aléatoire...

Envoyé par Heimdall

je comprends pas trop ?

J'ai mis en pièce jointe le code et makefile (faire juste make, sous linux) qui teste tout ça. Si vous avez le courage de me dire pourquoi l'un est plus rapide que l'autre....

Pour ce qui est du compilateur, je compile en -O2 et j'ai quand même un écart de perf assez grand entre les deux modèles...

Je regarderais peut-être ce soir ou demain...

**Heimdall** · 04/04/2011, 20h59

ok merci.

j'ai trouvé ceci :

At first glance, it might seem more sensible to have applications define a struct that stores all the attribute data for one particle in a single data structure, and then use this as a template argument to the Particles class, which would store a DynamicArray of values of this type. POOMA's designers considered this option, but discarded it. The reason is that most compute-intensive operations in scientific applications are implemented as loops in which one or more separate attributes are read or written. In order to make the evaluation of expressions involving attributes as efficient as possible, it is therefore important to ensure that data are arranged as separate one-dimensional arrays for each attribute, rather than as a single array of structures with one structure per particle. This makes typical computational loops such as

Code :

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

1
2
3
4
5
6
 
for (int i=0; i<n; ++i)
{
  x[i] += dt * vx[i];
  y[i] += dt * vy[i];
}

run more quickly, as it makes much better use of the data cache.

sur ce site : http://www.nongnu.org/freepooma/tuto...ticlesDoc.html

C'est une bibliothèque de calcul parallèle (en C++ mais je pense que ça n'a pas d'importance de ce point de vue) typiquement prévue pour la manipulation de simulations particules.

Je traduis pour les non anglophones :

Au premier abord, il pourrait sembler meilleur de définir une structure qui encapsule les attributs concernant une particule dans une seule structure de donnée, et ensuite l'utiliser comme un argument template pour la classe Particules, qui elle stockerait ce type dans un tableau dynamique. Les développeurs de POOMA on envisagé cette option mais l'ont finalement écartée. la raison est que la plupart des opérations intensive dans les applications scientifiques sont implémentées par des boucles dans lesquelle un ou plusieurs attributs de particules sont lus ou écrits. De manière à rendre l'évaluation des expression impliquant les attributs aussi efficaces que possible, il est donc important que les données soient implémentées comme des tableaux 1D séparés pour chacun des attributs, plutot qu'un seul tableau de structures de particules. Ceci fait qu'une boucle typique de calcul ressemble a :

[code]

Code :

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

1
2
3
4
5
6
 
for (int i=0; i<n; ++i)
{
  x[i] += dt * vx[i];
  y[i] += dt * vy[i];
}

et est executée plus rapidement étant donnée qu'elle fait une meilleur utilisation du cache.

Bon visiblement, c'est également la conclusion de mon code de test... mais je ne vois pas encore pourquoi, ce qui se passe vraiment dans la machine

**Heimdall** · 04/04/2011, 22h02

Pour ceux que ça intéresse, j'ai trouvé ceci, qui est très intéressant :

http://hectorgon.blogspot.com/2006/0...ucture-of.html

La conclusion est que "tableau de structure" est plus rapide que "structure de tableaux" TANT QUE le tableau de structure tient tout entier dans le cache L2 (j'ai pas compris pourquoi par contre).

Dès que le tableau de structure dépasse du cache L2, alors c'est la solution "structure de tableaux" qui est la plus rapide.

Perso j'ai testé avec le code que j'ai mis en pièce jointe plus haut, sur un intel xeon 3GHz avec un cache L2 de 2Mo. Ma structure fait 15doubles donc 120 octets, soit 17476 éléments dans mon cache.

C'est petit, déjà avec 128*128 éléments, je suis presque à la limite...

par contre en testant avec mon code, je trouve que peut importe la taille de la grille, la méthode "structure de tableaux" est plus rapide.

tout ceci est intéressant :-)

**Sve@r** · 04/04/2011, 23h58

Envoyé par Heimdall

tout ceci est intéressant :-)

Ouais. Mais en ce qui concerne "expliquer pourquoi" je reste sec.
Je sais à une époque que quand on utilisais des tableaux de structures, il était plus efficace de padder la structure sur une puissance de 2 octets. Bref les mystères de l'informatique...

performance : structure de tableaux ou tableau de structures

C

Discussions similaires

Partager

Partager