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

Citation:

---

Envoyé par 3DArchi

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

---

Oui, mais pas tous... Et cela ne change en rien le fait que le mot-clé inline (pas celui spécifique, donc) ne garantit pas l'inlining.

Citation:

---

Envoyé par TropMDR

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.

---

Non. Cela dépend de son contexte d'appel.

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.

---

Non, cela dépend surtout du nombre de registres utilisés/utilisables, et ce nombre est particulièrement faible sur des processeurs CISC. Cela dépend aussi d'autres réglages du compilateurs qui peuvent entrer en conflit avec un inlining.

Citation:

---

Envoyé par TropMDR

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.

---

Les macros, c'est comme le feu : si tu fais n'importe quoi avec, notamment en croyant que c'est une fonction, tu te brûles. Cela ne remet pas en cause l'outil lui-même, mais celui qui l'utilise.

Citation:

---

Envoyé par Joel F

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

---

Faut arrêter d'entrer en développement comme on entre en religion. Un compilateur n'est qu'un programme, qui fait ce qu'on lui dit de faire, comme on lui dit de le faire. Il n'a pas d'intelligence, et ne peut en aucun cas connaître à l'avance tous les tenants et aboutissants d'un programme en cours de compilation.

Tu devrais arrêter un peu tes professions de foi, je pense, et te pencher un peu sur des cas concrets d'optimisation réellement poussée... Et non pas laisser faire la machine avec une foi tellement absolue qu'elle en devient risible. Comme le dit François, battre la machine n'est pas très difficile, ne serait-ce que parce qu'elle n'a pas de notion du chemin dynamique du programme.

Mais encore faut-il s'être un jour penché sur le sujet pour le comprendre...

Citation:

---

Envoyé par fcharton

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

---

Parce que toi oui ? Tu te bases sur quoi pour savoir qu'une fonction doit être inliné, quelque soit l'endroit où elle est appelé, mais surtout quelque soit l'architecture ? Tu connais le rapport entre le coût d'un appel de fonction et le coût d'une augmentation de la taille du code, quelque soit l'archi ? Genre entre un x86 ou quasiment tous les arguments passent forcément par la pile, ou un amd64 ou on peut rester intégralement en registres ?

Citation:

---

Envoyé par Mac LAK

Non. Cela dépend de son contexte d'appel.

---

Je veux bien un "contexte d'appel" où la fonction dont on parle n'est pas inliné. Pour qu'on arrête de parler dans le vent sur le mode du "non mais sérieux, c'est trop possible qu'elle soit pas inliné"

Citation:

---

Envoyé par Mac LAK

Les macros, c'est comme le feu : si tu fais n'importe quoi avec, notamment en croyant que c'est une fonction, tu te brûles. Cela ne remet pas en cause l'outil lui-même, mais celui qui l'utilise.

---

Je ne remets pas en cause le fait que les macros soient utiles, quand on doit effectivement faire du remplacement textuel. En revanche, programmer avec des macros, c'est mal utiliser ses outils puisqu'on a les fonctions inline qui font pareil, mais en mieux.

Citation:

---

Envoyé par Mac LAK

Un compilateur n'est qu'un programme, qui fait ce qu'on lui dit de faire, comme on lui dit de le faire.

---

Oui enfin... Il faut surtout ce que lui disent de faire ses concepteurs, qui ne sont généralement pas de complets gignols et ont quelques notions de... compilation justement ! Et d'optimisation.

Citation:

---

Envoyé par Mac LAK

Il n'a pas d'intelligence, et ne peut en aucun cas connaître à l'avance tous les tenants et aboutissants d'un programme en cours de compilation.

---

Ca veut dire quoi "pas d'intelligence" ? Pour quelqu'un qui se dit programmeur chevronné, nous dire qu'on programme ne fait rien de bien parce qu'il n'a "pas d'intelligence", c'est quand même assez incroyable ! Tu vas nous dire qu'un programme ne peux pas reconnaitre un visage parce qu'il n'a "pas d'intelligence", qu'un programme ne peux pas résoudre une système linéaire parce qu'il n'a "pas d'intelligence", qu'un programme ne peut pas prédire le temps qu'il fera demain, parce qu'il n'a "pas d'intelligence" ? C'est n'importe quoi...

Citation:

---

Envoyé par Mac LAK

Tu devrais arrêter un peu tes professions de foi, je pense, et te pencher un peu sur des cas concrets d'optimisation réellement poussée...

---

Genre quoi ? la fusion de nid de boucles ? La propagation des constantes ? Le découpage en tuiles ? La réductions de force ? Celle des variables d'inductions ? Le pipeline logiciel ? Le lazy code motion ? L'élimination des sous expression communes ?

Citation:

---

Envoyé par Mac LAK

Et non pas laisser faire la machine avec une foi tellement absolue qu'elle en devient risible. Comme le dit François, battre la machine n'est pas très difficile, ne serait-ce que parce qu'elle n'a pas de notion du chemin dynamique du programme.

---

Les compilos itératif, ça existe, surtout pour l'embarqué aux perfs critiques que tu sembles tant chérir

Citation:

---

Envoyé par Mac LAK

Mais encore faut-il s'être un jour penché sur le sujet pour le comprendre...

---

Hihi :)

Citation:

---

Envoyé par TropMDR

Je ne remets pas en cause le fait que les macros soient utiles, quand on doit effectivement faire du remplacement textuel. En revanche, programmer avec des macros, c'est mal utiliser ses outils puisqu'on a les fonctions inline qui font pareil, mais en mieux.

---

Non, pas "en mieux". Les fonctions inline résolvent un des problèmes des macros (les paramètres modifiés par répétition), et introduisent un problème à la place (le fait que l'inlining ne soit pas toujours possible).

Citation:

---

Envoyé par TropMDR

Oui enfin... Il faut surtout ce que lui disent de faire ses concepteurs, qui ne sont généralement pas de complets gignols et ont quelques notions de... compilation justement ! Et d'optimisation.

---

Ils ne peuvent pas prévoir tous les cas de figure, ne serait-ce que par ce qu'ils ne peuvent pas estimer la criticité d'un code ou son profil d'exécution.

S'ils le pouvaient, des systèmes comme PolySpace ou autres Coverity ne serviraient à rien. Or, ils sont très utiles (et très utilisés).

Citation:

---

Envoyé par TropMDR

Ca veut dire quoi "pas d'intelligence" ?

---

Qu'un ordinateur n'est pas intelligent, même avec un programme d'IA. Il calcule vite, c'est tout. Prends un dictionnaire pour regarder la définition du mot "intelligence".

Citation:

---

Envoyé par TropMDR

Genre quoi ?

---

Genre prendre un programme et lui faire gagner 10% de perfs sans changer ni le matériel, ni les algos sous-jacents, ni le compilateur, ni les réglages dudit compilateur.

Citation:

---

Envoyé par TropMDR

Les compilos itératif, ça existe, surtout pour l'embarqué aux perfs critiques que tu sembles tant chérir

---

En dix ans d'embarqué, c'est amusant, mais je n'en ai pas vu un seul... On en parle, bien sûr, mais comme toute technologie, elle devra auparavant être validée et éprouvée avant d'être utilisée dans l'industrie. En attendant, on profile le code et on sait aussi ce que l'on écrit.

Et je pense que ça rassure pas mal de gens de savoir que les avions, les trains ou les voitures ne sont pas validés avec des softs en version alpha et/ou en cours de stabilisation. Si l'on n'utilise pas les dernières technos à la mode, il y a une bonne raison : nos clients nous l'interdisent formellement. Seules les technologies pouvant justifier de plusieurs millions (voire milliards...) d'heures de bon fonctionnement peuvent être utilisées.

Citation:

---

Envoyé par TropMDR

Parce que toi oui ? Tu te bases sur quoi pour savoir qu'une fonction doit être inliné, quelque soit l'endroit où elle est appelé, mais surtout quelque soit l'architecture ? Tu connais le rapport entre le coût d'un appel de fonction et le coût d'une augmentation de la taille du code, quelque soit l'archi ? Genre entre un x86 ou quasiment tous les arguments passent forcément par la pile, ou un amd64 ou on peut rester intégralement en registres ?

---

Moi? Je teste, j'utilise un profileur, je fais mon boulot d'ingénieur...
Il n'y a rien de magique, tout se mesure, tout se teste.

"Quelle que soit l'architecture", c'est atrocement prétentieux. Je teste sur les architectures qu'utilisent mes clients, point barre... La portabilité sur une machine qui n'existe pas dans mon monde, je m'en bats un peu l'oeil...

Mais l'approche fonctionne, et ce qui la cautionne, c'est qu'on vend nos programmes

Francois

Citation:

---

Envoyé par fcharton

Moi? Je teste, j'utilise un profileur, je fais mon boulot d'ingénieur...
Il n'y a rien de magique, tout se mesure, tout se teste.

---

Donc l'approche que tu suggères, c'est d'écrire une fonction non inline, et d'écrire une macro (donc certaine d'être "inlinée"), et de tester les deux à chaque fois ?

Citation:

---

Envoyé par TropMDR

Donc l'approche que tu suggères, c'est d'écrire une fonction non inline, et d'écrire une macro (donc certaine d'être "inlinée"), et de tester les deux à chaque fois ?

---

Non. Ce que je dis c'est que *quand* il faut optimiser le code, on regarde souvent la possibilité d'inliner, ou de refondre certaines boucles appelées très souvent. On le fait parce que, bien souvent, ca marche.

Du coup, dans des modules relativement simples et isolés, et qui n'ont pas vocation à évoluer, écrire des macros dès le départ (en sachant que cela comporte des risques) est souvent un gain de temps, car cela évite de se poser la question un peu plus tard.

Maintenant, mettre des macros n'importe où, c'est idiot, parce que ca rend le code difficile à lire et à maintenir. Mais ce n'est pas une raison pour les interdire entièrement (au passage, je pense la même chose des goto, des constantes magiques, des casts, de plein de choses)

Comme souvent, c'est une affaire de jugement, qu'on laisse au programmeur, réputé intelligent.

Francois

Citation:

---

Envoyé par fcharton

Non. Ce que je dis c'est que *quand* il faut optimiser le code, on regarde souvent la possibilité d'inliner, ou de refondre certaines boucles appelées très souvent. On le fait parce que, bien souvent, ca marche.

---

Justement ! L'intérêt du mot clé inline, c'est bien ça : pour passer d'une fonction "normale" à une fonction "inlinée", il suffit d'un mot clé. Pour les macros, c'est bien plus lourd (il faut entre autre changer la casse ;))

Mais pour arrêter de parler dans le vent, j'aimerais *un* exemple d'une fonction et d'un contexte d'appel avec les propriété suivante :

1. La fonction est marquée inline
2. elle est suffisamment "petite" pour qu'on puisse l'écrire comme une macro
3. mais même avec une option d'optimisation raisonnable du compilo (c'est à dire qui active l'inlining), elle n'est pas inliné alors qu'elle devrait l'être

Parce que l'argument pour les macros/contre les fonctions inline, c'est qu'il se pourrait que ce ne soit pas inliné. Mais n'est ce pas un risque purement théorique ?

Citation:

---

Envoyé par fcharton

au passage, je pense la même chose des goto, des constantes magiques, des casts, de plein de choses

---

des goto, ça doit quand même faire plus de 20 ans que je ne vois personne les prôner ou même les avouer. Tu vas un peu fort, non ?
Sinon, je ne suis jamais intervenu dans une petite structure avec peu de développeurs internes et pérennes. La problématique de la maintenance et l'évolution par d'autres intervenants a toujours été une composante forte : le genre de projet où il n'y a pas de transmission de l'"intelligence" du tabou qu'on peut violer. Par conséquent, introduire des goto (je prends exprès car c'est celui qui m'a le + interpellé), même intelligemment, même bien documenté, itou, itou, c'est prendre le risque d'une diffusion de mauvaises pratiques par effet de mimétisme (puisque ça existe déjà, pourquoi s'en priver ?). Peut-être ces différentes pratiques sont elles liées aussi à des contextes projets trop différents ?

Je me souviens qu'il y a eu un fil sur les goto il y a quelques mois, où finalement, pas mal de monde en avouait un ou deux...

Juste pour préciser... Dans ma carrière, des goto (en C ou C++), j'ai dû en écrire trois ou quatre, donc oui, c'est complètement exceptionnel. Mais j'ai utilisé pas mal de code où il y en avait. Globalement, je peux imaginer des cas où ils sont pratiques, parce qu'ils améliorent la lisibilité du code, mais ils sont très rares. Je ne crois pas non plus à l'idée que cela pourrait "contaminer" notre belle jeunesse : les goto, c'est un peu le croquemitaine des programmeurs, tout le monde en a peur, le risque est donc très faible.

Ce que j'essaie de dire, c'est que j'ai tendance à privilégier la lisibilité du code sur son côté "défensif" (vis à vis d'autres programmeurs). Quand on écrit des choses complexes (dans du code "bateau", cela n'a aucune importance) un code simple, même "casse gueule" me parait toujours préférable à quelque chose de plus correct, mais bavard et moins lisible.

Inversement, je suis extrèmement méfiant vis à vis des constructions "correctes" qui se traduisent par des choses lourdes à lire ou à débuguer. La lourdeur se caractérisant pour moi par la longueur des phrases ou des idiomes (je n'ai aucun mal avec les notations abstraites et compactes, façon APL). C'est probablement mon principal problème avec des bouts du C++ moderne et des design pattern. Et je trouve ces approches (qui souvent complexifient gratuitement des concepts simples, en essayant de les rattacher à des 'abstractions connues') bien plus contaminantes que les goto.

Je conviens volontiers que c'est une approche de PME, et typique de milieux où l'on travaille avec de petites équipes, et souvent des programmeurs ayant un bagage scientifique. Je crois qu'on essaye, en fait, de retrouver la concision du langage mathématique, parce que c'est le mode d'abstraction qui nous convient.

Francois

@fcharton: si je profile mais je profile dans les cas ou le code généré ne respecte pas ma spec (ou celle du client). Je bosse aussi sur des outils d'aide à la parallélisation automatique et souvent, je m'aperçois que une idée d'optimisation poussé qui me semblait bonne est faite toute seul par de gros compilo genre icc récent etc. Je ne dis pas qu'il faut jamais le faire, tout comme je n'entre pas en profession de foi. Mais encore une fois, ce que certains ne comrpennent pas, c'est que ce cas de figure est celui de la majorité des gens, et non d'une minorité. Pour faire comme certain, je vais aussi m'étaler. J'ai fait une thése sur de la vision par ordinateur parallèle temps réelle sur cluster et multi-coeur, j'ai 2 outils de parallèlisation automatique qui cible ces archis et plus (genre processeur cell et gpu) et qui sont utilisés par de vrais gens (genre on a eu des contrats de recherche avec Thales et le CEA la dessu), j'ai fait du MMX/SSE2+ et de l'AltiVec depuis mon DEA. Alors oui je sais de quoi je parle ...

Maintenant, pour faire avancer le débat, il serait de bon aloi de prendre ce fait pour acquis (comme la montré je ne sais qui dans le topic fils sur la STL). Aprés, oui je suis d'accord avec vous: sur des archis exotiques avec des compilateurs middle (et dieu sait que j'en ai chié à faire du C++ avancée avec g++ 2.95.2) voir atroces (icc 6 ou -), oui il faut se palucher ce genre de truc, et je le fait. Sauf que c'est 1% de mon temps voire moins.
C'est tout ce que j'aimerais que vous compreniez ;)

Citation:

---

Envoyé par Joel F

Alors oui je sais de quoi je parle ...

---

Je n'en ai jamais douté, j'espère que je ne vous ai pas donné cette impression (je vous rassure, je ne déballererai pas mon CV...).

Citation:

---

Envoyé par Joel F

C'est tout ce que j'aimerais que vous compreniez ;)

---

Je pense que tout le monde s'est compris, et au fond je crois qu'on est tous d'accord. En fait, je crois que la plupart des défenseurs des macros, sur ce fil, n'en écrivent pas tant que cela, et que la plupart de leurs opposants s'en sont déjà rendu coupables.

On est plus dans le domaine des réactions épidermiques aux "fais pas ca" qu'on nous assène parfois un peu beaucoup en informatique...

Francois, sans rancune.

Citation:

---

Envoyé par fcharton

Francois, sans rancune.

---

Y a pas de soucis :o

Bon, vous arrêtez de vous faire des papouilles les deux là ? :-p

Plus sérieusement, la question plus haut n'était pas là juste pour mettre les gens en difficulté, c'est que j'aimerais *vraiment* savoir à quel point c'est un mythe le coup du "le compilo peut ne pas inliner" (je sais pertinemment que tous les compilos s'autorisent à le faire, je voudrais juste être sûr que ça arrive vraiment, dans la vraie vie.)

Citation:

---

Envoyé par TropMDR

Plus sérieusement, la question plus haut n'était pas là juste pour mettre les gens en difficulté, c'est que j'aimerais *vraiment* savoir à quel point c'est un mythe le coup du "le compilo peut ne pas inliner" (je sais pertinemment que tous les compilos s'autorisent à le faire, je voudrais juste être sûr que ça arrive vraiment, dans la vraie vie.)

---

Je l'ai vu faire sur des compilateurs Borland (en mode release et tout ça), pour des fonctions assez longues, ou ayant un appel de fonction à l'intérieur, ou parfois des paramètres d'appels un peu nombreux. Dans l'exemple ci dessus, on le verrait peut être si les opérateurs [] de la matrice sont surchargés, ou si le type matrice passé en paramètre est un peu plus complexe qu'un tableau.

Ma conclusion, à l'époque, avait été que la décision d'inliner dépendait à la fois de la taille, mais aussi de la "linéarité" du code concerné. Un truc avec une boucle, un appel de fonction, ou des sauts pouvait n'être pas inliné.

En général, ca partait d'un bon sentiment de la part du compilateur, mais qui pouvait s'avérer faux dans des cas critiques (qui sont un peu les seuls qu'on regarde quand on profile : on ne parle pas des trains qui arrivent à l'heure...).

Francois

la seule experience concluante (ie répétable et mesurable) c'est que souvent les fonctions avec du controle complexe (while, if imbriqués) ne passent pas l'inlining au dela d'un certain seuil de nombre de saut (certainement à cause de forward jump que le compilo à du mal à intégrer au site d'appel).

Par contre, le coup de l'operator[] j'ai du mal à y croire (ou alors à coir la tete du []). Y avait un PDF qui trainait sur le net ou un gars de chez Metrowerks comparait justement les sorties assembleurs de qqs compilateurs récents à ce qu'on pouvait écrire à la main et démontait justement pas mal de préjugés. Je poste le lien des que je le retrouve.

Citation:

---

Envoyé par Joel F

Par contre, le coup de l'operator[] j'ai du mal à y croire (ou alors à coir la tete du []).

---

Si la surcharge de [] est une indirection (on a une structure contenant un conteneur, et [] est surchargé pour renvoyer le "bon élément" du conteneur), ce qui doit être le cas le plus courant, il est certain que ce sera inliné. Le problème peut se poser quand on assigne à [] des missions plus complexes. Deux cas relativement fréquents :

- le conteneur a une implémentation complexe, que l'interface cache, et [] effectue en fait une recherche
- les éléments du conteneur sont initialisés lors de leur première utilisation, par []. Ce dernier cas est le cas typique du "piège à compilateur" : la fonction se compose d'une boucle d'initialisation, un peu complexe, mais très rarement appelée, et d'un code "de base" (un test une indirection) très simple et presque toujours appelé.

Il n'y a rien de mystérieux avec []. La seule chose "piégeuse", c'est qu'on a souvent tendance à considérer qu'un opérateur simple fait forcément un calcul simple...

Francois

Citation:

---

Envoyé par fcharton

Je l'ai vu faire sur des compilateurs Borland (en mode release et tout ça), pour des fonctions assez longues, ou ayant un appel de fonction à l'intérieur, ou parfois des paramètres d'appels un peu nombreux.

---

Et tu as testé ? Tu l'as mis en macro, et c'était vraiment plus rapide ? Parce qu'on peut clairement *perdre* des perfs à inliner des fonctions trop longues (les explications qui suivent ne sont pas pour les intervenants de cette discussions mais pour les lecteurs potentiels ;) ).

Si on inline plusieurs fois une fonction, on duplique le code. On augmente donc la taille du code total, et on risque par exemple de sortir du cache instruction. Si j'ai une boucle serrée qui appelle une fois et à chaque tours une toute petite fonction, il sera sans doute rentable de l'inliner. Si la même boucle appelle 3 ou 4 fois une petite fonction, il est parfois rentable de faire les appels (qui sont cher, mais pas forcément tant que ça, surtout si on a peu d'arguments, qu'ils passent en registres parce qu'on en a plus que 8 (des registres) :)), en restant dans le cache (on peut même imaginer que le prédicteur de branchement du proc profite de la réutilisation du même code). Donc la "bonne" décision n'est pas forcément purement locale, et les euristiques de l'inliner peuvent en tenir compte, alors qu'une fois que c'est une macro, c'est inliné, point barre. Plus de décision possible suivant le site d'appel.

Mais même si on n'appelle la fonction qu'une seule fois, ce n'est pas forcément une bonne idée de l'inliner ! J'ai eu le problème il y a peu avec GCC en écrivant une machine virtuelle (en C). J'avais plein de fonctions marquées inline qu'il inlinait bien, mais aussi une fonction assez grosse, mais appelé en un seul point du code, qu'il avait donc inliné de force (la fonction n'étant pas exporté, ça n'augmentait pas la taille totale du code). Sauf que cette fonction n'était appelé que rarement, et le fait de l'avoir inliné faisait sortir le corps de ma boucle du cache instruction. Après avoir réussi à convaincre GCC de ne PAS l'inliner, j'ai eu un gain de perf de presque 10%. Donc l'inlining peut vraiment avoir des effets très négatifs !

Bref, la version "fonction marquée inline" garde nettement plus de souplesse que la macro puisque la décision d'inliner ou non peut être prise (ok, par le compilo) suivant le site d'appel.

Citation:

---

Envoyé par TropMDR

Et tu as testé ? Tu l'as mis en macro, et c'était vraiment plus rapide ? Parce qu'on peut clairement *perdre* des perfs à inliner des fonctions trop longues

---

Ben oui... En l'occurrence j'avais copié le code dans la boucle, mais tu conviendras que c'est rigoureusement égal à la macro. Et oui, le gain était réel.

Sur le fait que l'inlining n'est pas toujours bon, c'est une certitude. Une boucle centrale courte avec appels externes gagne très souvent contre une boucle longue avec appels inlinés, pour les raisons que tu cites. J'ai remarqué néanmoins que quand on allait dans le détail, ca devenait vite très compliqué, surtout quand on est en mode release, où la structure du code final peut dépendre assez fortement de l'ordre des instructions en entrée...

En fin de course, une fois qu'on a déterminé les points où le temps est passé, et qu'on n'a plus d'idées pour des améliorations algorithmiques (c'est généralement là que sont les vrais gains de performance), ca finit souvent par une séance d'essais et erreurs avec un profileur...

Ce que fait le compilateur, et qu'il fait bien, c'est de réduire le nombre d'endroits où il est nécessaire de profiler.

Francois