Discussion :

[etienne007]

Bonjour,
J'ai besoin dans mon programme d'une matrice de booleens de taille 256*256*256.

La taille en mémoire serait donc de 2Mo.

Or quand je compare la phase d'initialisation de mon programme, j'ai un écart de 33Mo environ lorsque j'ajoute la matrice. (donnée calculée avec le gestionnaire des tâches en tenant compte de la mémoire virtuelle)

Sans matrice: 5,8Mo + 3,4 dans la MV
Avec matrice 22,3Mo + 19,6 dans la MV

Voici comment je crée la matrice:

Code :

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

bool table[256][256][256];

J'ai essayé une autre méthode avec les malloc mais ca prend meme quelques Mo de plus.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
bool*** table;
//Allocation et initialisation du tableau de booleens
	table = (bool***) malloc(256*sizeof(bool**));
	for (int i=0; i<256; i++) {
		table[i] = (bool**) malloc(256*sizeof(bool*));
		for (int j=0; j<256; j++) {
			table[i][j] = (bool*) malloc(256*sizeof(bool));
			for (int k=0; k<256; k++) {
				table[i][j][k] = 0;
 
			}
		}
	}

D'autre la création naïve bool table[256][256][256]; prendrait un espace de mémoire contiguë. N'y a t'il pas un risque de bug si la mémoire est trop fragmentée au moment de l'utilisation? (à moins que le système est assez inteligent pour ranger la mémoire si besoin)

Que faire car c'est quand meme pas top cette utilisation excessive mémoire!

Merci d'avance pour votre aide

[Invité]

Il faudrait regarder la doc de ton compilateur, mais un booléen c'est en général stocké sur un octet (même si ca n'utilise qu'un bit). Donc un tableau de 256*256*256 booléens, ca fait 2^24 octets, ou 16 Mo (à mon avis, il y a un double compte quand tu ajoutes la MV).

Si tu alloues cela comme un tableau de tableau de tableau, il faut rajouter la mémoire pour les pointeurs (4 octets par pointeur de 32 bits).

L'intérêt de travailler à l'octet, c'est que les accès aux booléens seront nettement facilités. Et 16 Mo, sur une machine récente, ce n'est pas énorme.

Sinon, tu peux soit utiliser un vector<bool>, qui utilise un bit par booléen, soit un tableau de bitset, par exemple des bitset<256>. (mais lit la doc de la STL si tu utilises l'un ou l'autre, c'est plein de pièges...)

Francois

[etienne007]

Merci pour l'explication!

Pour le compilateur j'utilise visual Studio 2005.

Je vais donc rester sur la méthode simple bool table[256][256][256]; et tanpis pour la perte de mémoire...

par contre pour le destructeur de l'objet je détruit manuellement la matrice oou c'est automatique?

Je sais que si elle est créer avec des malloc il faut le faire sur chaque sous tableau, mais dans le cas de cette matrice crée avec bool table[256][256][256]; je détruis explicitement le tableau?

[Mac LAK]

Si la matrice est déclarée de façon statique, tu n'as pas besoin de la détruire.

Par contre, c'est hautement inefficace comme méthode pour stocker autant de booléens, ne serait-ce qu'à cause des alignements qui peuvent quadrupler la taille de ton tableau...

Pour ma part, je serais plutôt parti sur l'utilisation d'un seul bit par booléen, avec une matrice de type unsigned long int table[256][256][8] et quelques bon templates/macros pour gérer ça : tu t'affranchis des optimisations (forcément optionnelles...) de la STL, et tu es certain de l'utilisation de ta mémoire.

[etienne007]

ne serait-ce qu'à cause des alignements qui peuvent quadrupler la taille de ton tableau...

Je ne vois pas de quoi il s'agit?

Pour ma part, je serais plutôt parti sur l'utilisation d'un seul bit par booléen, avec une matrice de type unsigned long int table[256][256][8] et quelques bon templates/macros pour gérer ça

dans ce cas pour obtenir le bool correspondant à i on fait (on prend le pb en une dimension pour simplifier)

+ les 3 bits de plus haut poids donnent le numéro de la case du tableau
ça se code avec:

Code :

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

table[ i >>5 ]

+ les 5 bits de plus bas poids donnent un nombre entre 0 et 31 qui correspond à la place du bit cherché dans le long int de la case

Par contre ça m'a l'air plus couteux en opération (à moins que le modulo % soit optimisé en cas de puissance de 2...)

i%32 donne donc la place du bit entre 0 et 31, on fait un décalage puis on prend le bit de plus faible poids

Ca donnerait:

Code :

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

1
2
3
bool valeureTable(int i) { // i entre 0 et 255
return ( ( table[ i >>5 ] ) >> (i%32) ) % 2;
}

Je trouve ca pas très beau (impossible de trouver une fonction donnant directement le nième bit d'un long int.)

mais n'est ce pas trop couteux en opérations?

C'est pour un traitement d'image et chaque pixel demande un accès à la matrice256*256*256 (qui correspond à l'espace des couleurs)

Donc pour traiter un flux vidéo, j'ai pas interet que ca soit trop long.

Par contre ça pourrait peut être aller un peut plus vite avec la meme méthode sur un char table[256][256][32]
avec return ( ( table[ i >>3 ] ) >> (i%8) ) % 2;

(ca dépend si le décalage de bit est moins couteux que le modulo, mais ca revient peut être au même)

Ou alors coder carrément un type de 256bits avec une fonction pour atteindre le ieme bit, mais il y a peut être un risque que ca soit moins performant?

J'attends vos commentaires avant de me mettre à recoder mon objet.

Merci encore!

[Joel F]

Pour ma part, je serais plutôt parti sur l'utilisation d'un seul bit par booléen, avec une matrice de type unsigned long int table[256][256][8] et quelques bon templates/macros pour gérer ça : tu t'affranchis des optimisations (forcément optionnelles...) de la STL, et tu es certain de l'utilisation de ta mémoire.

c'est deja ce que fait std::bitset<N> si je ne m'abuse:

http://codepad.org/I4BplhrE

sachant que bitset::operator[] fait aussi la tambouille pour extraire le booleen compressé.

[etienne007]

Ca a l'air super pour ce que je veux faire bitset!

En plus l'accès semble se faire comme pour un simple tableau
(table[i][j][k] )

Je n'aurais donc que la déclaration de table à modifier!

par contre pour le destructeur, je suppose qu'il faudra faire:

Code :

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

1
2
3
4
5
for (int i=0; i<256; i++) {
        for (int j=0; j<256; j++) {
			~table[i][j](); 
		}
	}

[Mac LAK]

Je ne vois pas de quoi il s'agit?

Tu peux, suivant les optimisations, n'avoir qu'un seul octet tous les 32 bits, pour des raisons de performances. C'est pour ça que j'ai mis comme élément "terminal" de ma matrice un entier 32 bits et non pas un octet. Ainsi, peu importe l'alignement, tes données (sur une machine 32 bits) seront contigües et sans "pertes" au niveau des accès à la mémoire (un CPU 32 bits lit toujours des mots de 32 bits, même si tu n'as demandé qu'un octet).

Je trouve ca pas très beau (impossible de trouver une fonction donnant directement le nième bit d'un long int.)

Ce n'est pas fait pour être "beau", c'est fait pour être efficace...
C'est plutôt que tu fonctionnes avec des décalages "purs", opérations qui sont extrêmement rapides. Le but derrière n'est pas d'avoir un joli bit valant 0 ou 1, mais un booléen, quelque chose que l'on peut filer directement à "if" pour faire une opération. Donc, tu vas extraire brutalement le bit, et éventuellement caster directement dans un bool au travers d'une macro.
Exemple :

Code :

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

#define GETBIT(Matrix,i,j,k) (bool)(Matrix[(i)][(j)][(k)>>5] & (1<<((k) & 31)))

Cela renvoie directement un bool, mais on pourrait aussi le laisser renvoyer un entier 32 bits qui vaudra soit zéro, soit "pas zéro".
Tu vas avoir de même une macro de positionnement de bit fonctionnant de façon similaire :

Code :

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

#define SETBIT(Matrix,i,j,k,value) if (value) { Matrix[(i)][(j)][(k)>>5] |= (1<<((k) & 31))) } else { Matrix[(i)][(j)][(k)>>5] &= ~(1<<((k) & 31))) }

Bon, là, c'est fait avec des macros, mais tu peux le faire avec des templates si ça te "parle" plus. Cela ne changera pas grand-chose au final, tant que le code est inliné au maximum et qu'il n'utilise que des opérations "simples" (indirections, décalages, AND/OR/NOT binaires).

C'est pour un traitement d'image et chaque pixel demande un accès à la matrice256*256*256 (qui correspond à l'espace des couleurs)

Hmmm ? Est-ce pour compter le nombre de couleurs ? Si oui, il y a beaucoup plus efficace que cette méthode...

(ca dépend si le décalage de bit est moins couteux que le modulo, mais ca revient peut être au même)

Avec les optimisations activées, cela revient NORMALEMENT au même si la valeur de modulo est constante. Ce n'est pas forcément vrai si c'est en debug ou si c'est variable. Par exemple, "i % 32" est optimisé avec un décalage, mais "i % value" (value étant une variable contenant 32) ne le sera pas.

[3DArchi : sur la digression relative aux perfs de la STL, cf cette discussion]