Matrice de booleen

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:

---

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

---

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

Code:

---

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

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

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?

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.

Citation:

---

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

---

Je ne vois pas de quoi il s'agit?

Citation:

---

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:

---

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:

---

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!

Citation:

---

Envoyé par Mac LAK

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

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:

---

1 2 3 4 5

for (int i=0; i<256; i++) { for (int j=0; j<256; j++) { ~table[i][j](); } }

---

Non. Le destructeur est appelé automatiquement comme pour toutes variables allouées statiquement. On est pas en JAVA ;)

Citation:

---

Envoyé par etienne007

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

---

En fait, si tu utilises la STL tu as deux options distinctes : bitset<> et vector<bool>, les deux fonctionnent comme des tableaux, et stockent de manière compacte.

La différence, c'est que

bitset<> offre une interface plus large (fonctions de manipulations de bits, ET, OU, tout ca), mais sa taille doit être fixée à la compilation, et ce n'est pas une séquence, c'est à dire que tu ne peux utiliser un itérateur pour parcourir le tableau.

vector<bool> peut changer de taille à l'éxécution, tu peux le parcourir avec des itérateurs, mais l'interface est plus frustre.

Donc le choix va dépendre de ce que tu veux faire de ces données... En gros, si tu veux juste un tableau compact (que tu utilises comme un tableau) vector<bool> est le choix naturel. Si tu veux faire des calculs sur les booléens (par exemple compter le nombre de 1, ou les décaler, ou...), il te faut un bitset<>

Dis toi aussi que le gain en place se paye en vitesse d'accès à la donnée... Un tableau de bool se lira toujours plus vite qu'un bitset ou un vector<bool> (mais la différence n'est pas forcément énorme, il faut tester...)

Francois

Vu que dans un cas tu accede à un octet et dans l'autre tu fais accés à un octet + un masquage de bit, les bandes passante mémoire étant ce qu'elles sont, la différence est quasi nulle.

Citation:

---

Envoyé par etienne007

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

Citation:

---

Envoyé par etienne007

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:

---

#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:

---

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

Citation:

---

Envoyé par etienne007

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

Citation:

---

Envoyé par etienne007

(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]

Merci beaucoup pour vos conseils.

J'ai finalement choisi la methode de Mac LAK et ca marche bien:

A part ceci

Citation:

---

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

---

qui me renvoit un avertissement, mais je pense que c'est normal.

Citation:

---

warning C4800: 'unsigned long'*: valeur forcée à la valeur booléenne 'true' ou 'false' (avertissement sur les performances)

---

Je gagne 14,4Mo en occupation mémoire, et j'ai même une légère accélération du programme. (de l'ordre de 10%)

Citation:

---

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

---

En fait la matrice de booleen me sépare l'espace des couleurs (256*256*256) en 2 catégories et ma fonction va regarder pour chaque pixel de l'image dans quelle catégorie il est.

C'est pour faire de la reconnaissance des zones de pixels de peau d'une vidéo prise par la webcam...

Citation:

---

Envoyé par etienne007

A part ceci qui me renvoit un avertissement, mais je pense que c'est normal.

---

Arf, oui, c'est normal... Supprime le cast (bool) en début de macro, et laisse-le bosser avec la valeur brute 32 bits. Tant que tu l'utilises comme un booléen C (=> ne pas tester l'égalité avec true), tu n'auras pas de problèmes.

Exemples :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

// Correct if (GETBIT(Matrix,i,j,k)) { /* Action TRUE */ } else { /* Action FALSE */ } if (!GETBIT(Matrix,i,j,k)) { /* Action FALSE */ } else { /* Action TRUE */ } if (GETBIT(Matrix,i,j,k)!=0) { /* Action TRUE */ } else { /* Action FALSE */ } if (GETBIT(Matrix,i,j,k)==0) { /* Action FALSE */ } else { /* Action TRUE */ }   // Correct, mais devrait lever un warning à la compilation. if (GETBIT(Matrix,i,j,k)!=false) { /* Action TRUE */ } else { /* Action FALSE */ } if (GETBIT(Matrix,i,j,k)==false) { /* Action FALSE */ } else { /* Action TRUE */ }   // INCORRECT, risque de ne jamais passer dans le cas "true", et devrait faire un ou deux warnings à la compilation. if (GETBIT(Matrix,i,j,k)==true) { /* Action TRUE */ } else { /* Action FALSE */ } if (GETBIT(Matrix,i,j,k)!=true) { /* Action FALSE */ } else { /* Action TRUE */ }

---

Citation:

---

Envoyé par etienne007

Je gagne 14,4Mo en occupation mémoire, et j'ai même une légère accélération du programme. (de l'ordre de 10%)

---

:ccool:

Citation:

---

Envoyé par etienne007

En fait la matrice de booleen me sépare l'espace des couleurs (256*256*256) en 2 catégories et ma fonction va regarder pour chaque pixel de l'image dans quelle catégorie il est.

---

Mmmm.... Donc, en résumé, sur les 16 millions de couleurs possibles dans ce système, tu as fais une partition entre "couleur de peau" et "autres", c'est bien ça ?

Ta matrice est-elle initialisée statiquement (ex : calcul de la plage couleur de la peau en HSV ou Yuv et conversion RGB, calculé sur des images d'étalonnage), ou dynamiquement (tu dis "cette zone est de la peau" sur une frame de la vidéo, et il stocke les valeurs dans la matrice) ?

Au final, quel est (approximativement, bien sûr !) le pourcentage de "nombre de couleurs FALSE" et de "nombre de couleurs TRUE" ?

En fonction de ces éléments, il sera peut-être possible d'améliorer encore plus cette partie...

Citation:

---

Envoyé par etienne007

A part ceci

Code:

---

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

---

---

Pourquoi utiliser une macro et pas une fonction inline ? Si dans ton code tu mets un GETBIT(m, i, j, k++) tu risques de sévèrement le regretter...

Citation:

---

Envoyé par TropMDR

Pourquoi utiliser une macro et pas une fonction inline ? Si dans ton code tu mets un GETBIT(m, i, j, k++) tu risques de sévèrement le regretter...

---

La macro garantit l'inlining, la directive inline pas.

Je crois que ce genre de macro a pour objet d'être intégrée dans des fonctions "de base" de la classe "matrice de booleen". En ce sens, l'utilisateur ne devrait jamais l'appeler.

Par ailleurs, mettre un k++ (ou n'importe quoi ayant des effets de bord) dans une macro, c'est toujours une mauvaise idée. C'est pour cela qu'on signale généralement les macros dans le code, en les mettant en majuscules, par exemple.

Francois

Citation:

---

Envoyé par TropMDR

Pourquoi utiliser une macro et pas une fonction inline ? Si dans ton code tu mets un GETBIT(m, i, j, k++) tu risques de sévèrement le regretter...

---

Comme le précise François, la directive "inline" n'est qu'une indication, et tu n'as JAMAIS la MOINDRE garantie que le code soit réellement inliné, contrairement à une croyance répandue... En pratique, on peut garantir qu'une fonction ne sera PAS inlinée, mais jamais qu'elle le soit. Les macros sont le seul et unique moyen d'en être certain.

Quand au niveau de "danger" des macros, il est bien sûr réel, mais c'est aussi le prix à payer pour obtenir des performances.

Salut,

Citation:

---

Envoyé par fcharton

La macro garantit l'inlining, la directive inline pas.

---

Certains compilateurs (Visual et il me semble aussi gcc) ont des directives de compilation pour forcer l'inlining.

Euh... Il faut arrêter avec le craquage du "on sait pas quand ce sera inliné". Une fonction d'une ligne, elle sera sans doute inliné sans le mot clé inline, mais avec, c'est *certain* que ce sera inliné, avec n'importe quel compilo.

Et il faut aussi se rappeler que quand le compilo n'inline pas une fonction marquée inline, c'est qu'il en a de très très bonne raisons. Il faut se souvenir que savoir s'il est intéressant d'inliner une fonction ne dépend pas juste de sa taille.

Bref, les risques pris par l'utilisation d'une macro qui utilise deux fois son argument comparé à l'utilisation d'une fonction inline qui a 99% de chance de se retrouver inliné ne valent vraiment pas le coup.

Citation:

---

Envoyé par TropMDR

Et il faut aussi se rappeler que quand le compilo n'inline pas une fonction marquée inline, c'est qu'il en a de très très bonne raisons. Il faut se souvenir que savoir s'il est intéressant d'inliner une fonction ne dépend pas juste de sa taille.

---

Exactement. Ca fait un bon moment qu'il faut arreter de penser que l'on peut battre un compilo à son propre jeu.

Citation:

---

Envoyé par TropMDR

Et il faut aussi se rappeler que quand le compilo n'inline pas une fonction marquée inline, c'est qu'il en a de très très bonne raisons. Il faut se souvenir que savoir s'il est intéressant d'inliner une fonction ne dépend pas juste de sa taille.

---

Oui, et il faut aussi savoir que le compilateur ne dispose pas de toute l'information nécessaire à ce choix...

Précisément, le compilateur dispose de deux informations pour décider d'inliner :
- la taille et la vitesse du code compilé
- les endroits où il est appelé,

Mais il ne sait pas combien de fois ce bout de code sera appelé dans une exécution réelle du programme.

Rien en garantit donc que le compilateur prendra, dans ce cas précis, la bonne décision.

@JoelF : tu n'utilises jamais de profileur ? Parce que, dès qu'on commence à jouer avec ces machins, on observe très très vite que bien sur, on n'a aucun mal à battre un compilateur (simplement parce que nous, on a les durées réelles).

Ca prend évidemment du temps, qui n'est pas consacré au développement, et c'est très agaçant, parce que le profiling c'est lent, voire très lent si on commence à faire des choses compliquées... Mais si on sait se servir du truc, c'est furieusement rentable (perso, je ne crois pas avoir jamais perdu le temps passé à profiler)

Francois