Discussion :

[Flo.]

Bonjour,

j'ai un tableau d'unsigned short à 3 entrées, par exemple :

Code :

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

unsigned short myTab[4][4][256 * 256];

Il très important, pour mon utilisation, de garder cette notion de tri-dimensionalité. Et lorsque je traite un tableau[i][j][256 * 256], je n'utilise pas les autres tableaux[x][y][256 * 256].

Je sais que l'utilisation de tableaux uni-dimensionnels est préférée à des tableaux mutli-dimensionnels ; les temps d'accès aux éléments d'un tableau multi-dimensionnels sont plus longs.

Par contre, quelle est la meilleure solution ?

Cas n°1 : myTab devient un tableau uni-dimensionnel, et j'utilise des offsets pour accéder aux parties qui m'intéressent :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
unsigned short myTab[4 * 4 * 256 * 256];
 
int offset00 = 0;
int offset01 = offset00 +  256 * 256;
int offset02 = offset01 +  256 * 256;
int offset03 = offset02 +  256 * 256;
int offset10 = offset03 +  256 * 256;
//... etc ...
int offset33 = offset32 +  256 * 256;
 
// et pour accéder à mon "original" myTab[2][1][65]
myTab[offset21 + 65] = 8;

Par contre je risque d'encombrer le cache inutilement puisque, comme le l'ai dit plus haut, lorsque je traite un tableau[i][j][256 * 256], je n'utilise pas les autres tableaux[x][y][256 * 256].

Cas n°2 : je déclare 16 tableaux de 256 * 256 que je réunis dans un tableau de pointeurs :

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
unsigned short myTab00[256 * 256];
unsigned short myTab01[256 * 256];
unsigned short myTab02[256 * 256];
unsigned short myTab03[256 * 256];
unsigned short myTab10[256 * 256];
unsigned short myTab11[256 * 256];
unsigned short myTab12[256 * 256];
unsigned short myTab13[256 * 256];
//... etc ...
 
// je réunis le tout dans une table de pointeurs
unsigned short * ptrOnMyTab[4][4];
 
ptrOnMyTab[0][0] = &myTab00[0];
ptrOnMyTab[0][1] = &myTab01[0];
ptrOnMyTab[0][2] = &myTab02[0];
ptrOnMyTab[0][3] = &myTab03[0];
ptrOnMyTab[1][0] = &myTab10[0];
//... etc ...
 
// et pour accéder à mon "original" myTab[2][1][65]
ptrOnMyTab[2][1][65] = 8;

Dans ce cas, je me demande si ça ne revient pas finalement au cas original myTab[4][4][256*256]

Alors qu'elle est la meilleure solution au final ?

Merci

Flo.

[ash.ice.loky]

Salut Flo,

A savoir qu’un l’opérateur de pointage équivaut à l’opérateur d’indexation.
Mes 2 façons de faire sont les suivantes :
- tableau unidimensionnel, avec décalage.
- vetor<vector<vector> > > : notation assez lourde, mais avec un petit typedef le problème est réglé.

[Flo.]

Merci pour ta réponse ash.ice.loky.

Je voudrais juste rajouter que j'utilise mon tableau dans un contexte de temps réel.

J'ai déjà fait des tests sur les vectors (notamment dans des algorithmes de segmentation d'images pour remplacer des tableaux), et ça n'a pas était concluant. Donc je ne retiendrai pas cette solution.

Par contre pourrais-tu être plus précis sur :

A savoir qu’un l’opérateur de pointage équivaut à l’opérateur d’indexation

Quant aux 2 cas que j'évoque, ils ne sont quand même pas identiques :

Dans le 1er cas j'ai un tableau énorme à faire passer dans le cache (de taille 4*4*256*256).
Dans le 2eme cas, juste un tableau de 256*256 (si ça fonctionne bien ainsi !!!).

La mise en cache devrait être plus rapide donc. Mais je ne m'y connais pas trop dans ce genre de chose. Je ne sais pas si il y a vraiment un gain ou pas

Flo.

[Sivrît]

A savoir qu’un l’opérateur de pointage équivaut à l’opérateur d’indexation

Je pense que ce qu'il veut dire est que

Code :

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

1
2
3
 
unsigned short myTab[4][4][256 * 256];
cout << myTab[2][1][65];

est identique à

Code :

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

1
2
3
 
unsigned short myTab[4][4][256 * 256];
cout << *(myTab + (2*4 + 1)*256*256 + 65);

J'ajouterais que en mémoire on obtient le même résultat avec les deux déclarations:

Code :

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

1
2
3
 
unsigned short myTab[4][4][256 * 256];
unsigned short myTab[4*4*256 * 256];

Dans les deux cas c'est une seule zone avec la même taille. La seule différence est qu'avec la deuxième il faut gérer soit même les différentes dimentions (sinon c'est le compilo qui le fait car on lui a donné les infos).

Pour tenter d'optimiser il est toujours possible de poser

Code :

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

1
2
 
unsigned short * current = myTab[2][1];

et de travailler sur current pour éviter de multiplier les calculs d'indices. Mais le compilateur doit être capable de gérer ce genre d'optimisations de lui même donc à réserver en dernier recourt.

Le vrai problème des tableaux à plusieurs dimentions est quand leurs taille s ne sont pas fixes. On passe par des tableaux de pointeurs, on fait des "new" et le tableau est éclaté en mémoire mais ce n'est pas le cas ici. De ce point de vue le cas 2 me semble une mauvaise idée car il introduit un déréférencement de plus (à la différence du cas original) et il fragmente les données.


Je connais assez mal le fonctionnement des caches mais dans l'ensemble on tente plutôt de grouper les données que de les fragmenter (même si ici l'indépendance des différents morceaux limite cet aspect). Et il me semble que rien ne s'oppose à ce que seule une partie du tableau soit mise en cache. Si je ne me méprend pas là dessus les différentes notations n'apporterons pas de gain (ou de perte) monumental de performances, alors "unsigned short myTab[4][4][256 * 256]" me semble avoir l'avantage d'être pratique et clair.

[Flo.]

Bon ben je vous remercie.

En fait, je vais passer à mon 1er cas :

Code :

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

1
2
 
unsigned short myTab[4 * 4 * 256 * 256];

Parce que lorsque je dois "vider" (mettre à 0) tous les tableaux, je pourrais tout passer en une seule boucle XMMX. Ca sera déjà un gain appréciable .

Merci.

Flo.

[Laurent Gomila]

Quoiqu'il en soit, essaye d'encapsuler tout ça dans une interface qui elle ne variera pas, de façon à ce que ton code soit toujours valide le jour où tu souhaites changer la représentation interne de tes tableaux.

[Sivrît]

Parce que lorsque je dois "vider" (mettre à 0) tous les tableaux, je pourrais tout passer en une seule boucle XMMX. Ca sera déjà un gain appréciable.

Ca marche aussi avec

Code :

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

unsigned short myTab[4][4][256 * 256];

qui est en fait la même chose. Dans les deux cas myTab va pointer sur le premier des unsigned short qui seront contigus donc MMX powa quand même. Je trouve dommage de renoncer à la facilité de notation pour eviter un cast (d'ailleurs non nécessaire je crois)

[Flo.]

Effectivement vous avez raison, j'ai réfléchi un peu rapidement.

Je vais préserver ma notation originale, ce qui, vous avez tous entièrement raison, est plus lisible ...

Merci encore.

Flo.

[loufoque]

Pour les tableaux à n dimensions il est plus pratique d'utiliser boost::multi_array