Discussion :

[BNS]

Bonjour à tous,

Je travaille sur un tableau de 307200 valeurs (640*480) égales à 1 ou 0. Un pointeur me permet de jongler avec les différents éléments du tableau. Dans un premier temps, j'avais déclaré ce beau monde en int mais j'ai rapidement remarqué que je pouvais gagner un gros temps d'éxécution si je travaillais avec des unsigned char. Et maintenant je me dis qu'avec des booleens ca pourrait aller encore plus vite, je me trompe?
Ma questionm, en gros, c'est: lors d'une gestion d'un tableau de cette taille, qu'est-ce qui est le plus intéressant d'utilisation? unsigned char? int? bool? autre?
Merci d'avance pour votre aide et vos conseils

[r0d]

Bonjour,

si mes souvenirs sont bons, cela dépend du compilateur. Quel est celui que tu utilises?

Il y a également autre chose à prendre en considération, c'est l'utilisation de ton ton tableau. Si par exemple tu fais un tableau de bool mais que, lorsque tu utilise ces valeurs, tu doit les caster en int, autant utiliser directement des int.

[BNS]

je travaille avec Visual Studio .NET 2003
J'utlise mon tableau de la facon suivante: selon qu'une case est à 0 ou 1, je noircis ou non une case (simple binarisation en fait), plus quelques autres trucs à coté. En gros, j'utilise principalement:

Code :

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

1
2
3
4
5
 
if (Mask[i]==1) 
{
   fais moi ca;
}

[Pragmateek]

"char" est le plus petit type du C++.
Après pour travailler au niveau des bits on peut utiliser les opérateurs bitwise.
On économise de la place mais on perd en performance lors de l'accés aux bits des données.

[r0d]

Là, il nous faudrait l'avis d'experts en optimisation, mais je crois que le type int est le plus (le mieux) optimisé en c++.

préférer le type int, c'est quasiment par définition le plus rapidement manipulé par le processeur.

Ca veut dire que bool ne peut pas etre manipulé rapidement par le proc?
L'important c'est tout de meme la proprete des types manipulés par le programme, le compilateur fait sa sauce derriere pour arranger ca au mieux.

Je veux dire:
Si le type n'est pas soumis à une contrainte particulière, comme initialisé par tel autre type, passé a une fonction, surpasser ou pas, avoir des décimales, être signé ou pas...
...alors, il faut prendre int.
Prendre un type plus petit en se disant "il prends moins de place en mémoire, j'y gagne" risque surtout de forcer le compilateur à générer du code supplémentaire, ou à utiliser des instructions processeur anciennes pour y accéder conformément au code écrit.

Hope it helps.

[BNS]

C'est en effet ce que j'ai lu un peu partout... Mais dans les faits, quand je travaille en int c'est plus lent qu'en unsigned char. Est-ce que la remarque que tu cites est principalement valable pour un petit nombre de valeurs?
Car la, avec 307200 valeurs, dans la memoire ca donne ca:
int ---> 1.228.000 bytes, soit 1.23 Mb
unsigned char ---> 307.000 bytes soit 0,31 Mb

[Foobar1329]

Hello,

Bonjour à tous,

Je travaille sur un tableau de 307200 valeurs (640*480) égales à 1 ou 0. Un pointeur me permet de jongler avec les différents éléments du tableau. Dans un premier temps, j'avais déclaré ce beau monde en int mais j'ai rapidement remarqué que je pouvais gagner un gros temps d'éxécution si je travaillais avec des unsigned char. Et maintenant je me dis qu'avec des booleens ca pourrait aller encore plus vite, je me trompe?
Ma questionm, en gros, c'est: lors d'une gestion d'un tableau de cette taille, qu'est-ce qui est le plus intéressant d'utilisation? unsigned char? int? bool? autre?
Merci d'avance pour votre aide et vos conseils

Pourquoi ne pas utiliser un tableau d'unsigned char de taille TailleMaxi / CHAR_BIT ? Si CHAR_BIT vaut 8 sur ton implémentation (cf <climits> ou <limits.h> ) comme c'est le cas pour beaucoup, tu peux avoir le bit comme donnée élémentaire et surtout diviser la taille de tableau par 8. Si en plus ta taille maxi est un multiple de 8 comme ici, c'est facile.

Voici un exemple de code ci-dessous. C'est un exemple crado pour aller vite. Tu peux bien sûr virer la variable globale, définir par exemple un type (classe, structure) sur lequel tu pourrais effectuer des manipulations de bits en y mettant des fonctions membres qui font la même chose que les 2 présentées en dessous, lever des exceptions si l'utilisateur rentre une position erronée, etc...

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <climits>
#include <iostream>
 
#if (CHAR_BIT != 8)
#error "CHAR_BIT doit valoir 8 pour compiler et exectuer ensuite le code ci-dessous"
#endif // (CHAR_BIT != 8)
 
const int cMaxSize = 640*480;
 
unsigned char foobar[cMaxSize/CHAR_BIT];
 
int setBitAtPos(const int & pos, bool bVal)
{
   int rc = -1;
   if (pos>=0 && pos<cMaxSize)
   {
      int numBlock = pos / CHAR_BIT;
      int posInBlock = pos % CHAR_BIT;
      unsigned char * pBlock = foobar;
      pBlock += numBlock;
      unsigned char mask = 1u << posInBlock;
      if (bVal) {
         *pBlock |= mask;
      }
      else {   
         *pBlock &= ~mask;
      }
      rc = 0; 
   }
   return rc;
}
 
int getBitAtPos(const int & pos) 
{
   int rc = -1;
   if (pos>=0 && pos<cMaxSize)
   {
      int numBlock = pos / CHAR_BIT;
      int posInBlock = pos % CHAR_BIT;
      unsigned char * pBlock = foobar;
      pBlock += numBlock;
      unsigned char mask = 1u << posInBlock;
      rc = (*pBlock & mask);
   }
   return rc;
}
 
int main()
{
   int rc = 0;
 
   std::cout << "Number of elements in foobar: " << cMaxSize<< "\n" ;
   std::cout << "Size of foobar: " << sizeof(foobar) << " bytes.\n" ;
 
   rc = setBitAtPos(300000, true);
   rc = getBitAtPos(300000);
 
   rc = setBitAtPos(0, true);
   rc = getBitAtPos(0);
 
   return 0;
}

A+

[Jean-Marc.Bourguet]

Ma questionm, en gros, c'est: lors d'une gestion d'un tableau de cette taille, qu'est-ce qui est le plus intéressant d'utilisation? unsigned char? int? bool? autre?

Ca va dépendre principalement du processeur utilisé et accessoirement du compilateur et de la manière dont tu vas écrire le code.

Le premier effet dont il faut tenir compte est le cache. Moins les données occupent d'espace, plus il y a de chance qu'elles soient dans un cache proche (les processeurs peuvent avoir plusieurs niveaux de cache) quand on en a besoin. Donc plus on a des données denses, plus on va vite.

Mais cet effet est contrebalancé par un autre facteur: les calculs nécessaires pour accéder aux données. Les processeurs qui peuvent accéder à un bit individuellement sont rares (et il est de plus difficile de faire comprendre à un compilateur qu'il faut utiliser ces instructions), donc on va y accéder par masquage de données plus grosse. C'est parfois vrai aussi pour les char (mais c'est moins courant). Ces instructions ont un coût, il est donc possible qu'il soit plus important ou plus faible que le gain dû à la moindre occupation mémoire.

Le facteur suivant est le compilateur. S'il est capable de remarquer que tu utilises systématiquement les 8 bits d'un octet après l'avoir lu, il va peut-être pouvoir utiliser une séquence plus performante que de relire chaque fois l'octet, construire un masque dépendant d'une variable et utiliser ce masque.

Le dernier facteur, c'est la manière dont le code est écrit. Je citais le cas d'un accès séquentiel à tous les bits d'un octet, si tu écris le code de manière à ce que ce soit bien remarquable, il y a plus de chances pour que le compilateur utilise une séquence efficace. Tu peux aussi réorganiser le code de manière à faire plusieurs passes sur un bloc qui tient en cache avant de passer à un autre bloc de données plutôt que de faire la première passe sur toute les données, puis la deuxième, ...

Il est fort vraissemblable qu'il y ait aussi des effets de seuils... jusqu'à une certaine taille utiliser un int est mieux, ensuite jusqu'à une autre utiliser un char est mieux, enfin utiliser un bit. Par exemple, le niveau de mémoire le plus lent est le disque (quand le SE commence a swapper). Même s'il faut beaucoup d'instructions pour gérer un stockage par bit, si ça permet d'éviter de swapper c'est à coup sûr un gain.

[Pragmateek]

Et les "bitset"?

[Jean-Marc.Bourguet]

Et les "bitset"?

C'est, en C++ (je ne sais pas pourquoi, je pensais répondre sur le forum C) une alternative à gérer le masquage pour une taille fixe. Pour une taille variable, on peut utiliser un std::vector<bool> qui est spécialisé pour permettre une optimisation en espace.

D'un point de vue performance, comme dans les autres options il faut mesurer pour savoir ce qui est le mieux (donc commencer par déterminer si c'est réellement critique) car ces solutions peuvent être meilleures ou pire qu'une gestion manuelle avec masquage.

En fait, en C++ l'utilisation d'un bitset ou d'un vector<bool> est vraissemblablement la solution à utiliser si on n'a pas mesuré qu'elle est trop coûteuse.