Discussion :

[ThE_LaSt]

Salut tout le monde, je travaille sur l'optimisation d'un programme en language C. Pour une fonction donnée, je veux travailler sur un tableau de booléens (0 ou 1), c'est à dire qu'au lieu de creer un tableau d'entiers (qui me couterait cher en espace memoire puisque 1 entier = 2 octets), je veux créer un tableaux de booléens. Ainsi chaque case sera codée sur un bit, si ce bit est 0, alors l'etat sera faux, sinon l'etat sera vrai.
Un grand Merci d'avance de bien vouloir m'aider !

[Pouic]

Et ?

Pourquoi n'utilises-tu pas un simple 'int' ?

[ThE_LaSt]

Je l'ai dejé expliqué dans mon premier post. Vu que je travaille sur l'optimisation de cet algorithme donc il faut reduire sa complexité spatiale (memoire) et temporelle (temps d'execution) et avec un simple int qui coute 2 octets par case, l'addition serait cher. La solution que j'ai trouvé est de travailler sur un bit vu que je n'utilise que les 0 et les 1 pour ce tableau. 1 case qui coute 1 bit <<< 1 case qui coute 2 octets.

[progfou]

Un char occupe un octet, tu ne peux pas travailler au niveau bit en C, sauf si tu passes par une structure avec champs de bits, mais la manipulation n'est plus la même...
Edit: Quelle est la contrainte mémoire ? Que dit le profiler ?

[gege2061]

avec un simple int qui coute 2 octets par case

En C la taille des types de base n'est pas défini, cela est vrai uniquement sur ta machine.

Le plus petit type est le char qui est codé sur CHAR_BIT bits. Après tu peut utiliser les opérateurs de décalage de bits (<< et >>) pour sélectionner/modifier un bit mais ça risque de ralentir l'algorithme.

Sinon en C99 le fichier d'en tête stdint.h définie deux nouveaux types qui pourraient t'interesser :

int_fastN_t Entier rapide(*) signé d'au moins N (8, 16, 32 ou 64) bits
uint_fastN_t Entier rapide(*) non signé d'au moins N (8, 16, 32 ou 64) bits

* la taille est choisie afin d'augmenter la rapidité des opérations

[ThE_LaSt]

Un char occupe un octet, tu ne peux pas travailler au niveau bit en C, sauf si tu passes par une structure avec champs de bits, mais la manipulation n'est plus la même...

Vous pouvez m'en dire un peu plus sur cette structure avec champs de bits S'il vous plaît ?

[Pouic]

Donc je repose ma question.
Qu'est ce qui t'empeche de travailler sur un int ? (unsigned)

En supposant que la taille d'un entier sur ta machine soit de 16 bits (c'est ce que tu sembles dire), tu as 16 bits de disponibles pour faire tes opérations. Après, ça dépend de la taille de ton tableau, et de la taille en mémoire de la représentation d'un entier (16, 32, ... bits).

Bien entendu, ce genre de manipulation doit être mûrement réfléchie : on perd en portabilité....

[Jack_serious]

Un char occupe un octet, tu ne peux pas travailler au niveau bit en C, sauf si tu passes par une structure avec champs de bits, mais la manipulation n'est plus la même...

Vous pouvez m'en dire un peu plus sur cette structure avec champs de bits S'il vous plaît ?

Structure avec champs de bit: quand tu crees une structure, tu peux definir sur combien de bits sont codes chacun des champs.

Ex:

Code :

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

1
2
3
4
5
 
struct     bitfield_s
{
  unsigned int  b : 16;
}

Ici b est code sur 16 bits.

Si tu a besoin d'un champs de bits de taille fixe, cette solution peut convenir.

[progfou]

Personnellement, j'opte pour les char, tu gagnes 1 octet par variable, c'est pas si mal.
Maintenant, les champs de bits, le site de developpez propose des cours et tutoriels, logiquement en cherchant un peu (et google est aussi ton ami), on trouve :
ftp://ftp2.developpez.be/developps/c/PolyC.pdf
Page 56, mais tout est intéressant.
C'est une introduction aux champs de bits, et il le rappelle, ce n'est pas portable, et pour moi, ce n'est pas LA solution.

[PRomu@ld]

Pour une fonction donnée, je veux travailler sur un tableau de booléens (0 ou 1),

Bon stdbool ne peut être pas t'aider (je ne sais pas comment ce tyoe est géré). Sinon, un champ de bit peut suffire, non ?

Code :

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

1
2
3
4
5
 
struct champ
{
     int val : 1;
};

Le seule problème que je vois c'est que ton compilateur va peut être te transformer ton champ de bit qui est théoriquement stoqué sur 1 bit en un octet voir même pus (je ne sais pas pourquoi mais il y de fortes chances pour que ça en occupe 4).

Pour ton problème de base, utilises déjà un char, ça sera mieux qu'un int, mais je ne pense pas que tu gagne énormément comme celà. En fait, utilise un profiler pour voir là ou se situe le goulot d'étranglement de ton programme, ensuite, tu pourras voir les champs de bits.

[Pragmateek]

ce n'est pas portable

Ca a un rapport avec le big et little endian ou est-ce un tout autre probleme?

[PRomu@ld]

trouvé sur le net :

Les champs de bits sont évalués de gauche à droite sur certaines machines et de droite à gauche sur d'autres. Ce type de données n'est donc pas portable.

C'est donc bien un problème de little/big endian

[progfou]

Entre autres choses, oui.
De plus, chaque compilateur organise la mémoire un peu différement, et si tu as un champ de 3 bits, ça peut occuper un octet (contenant les 3 bits), ou 2 ou 4, tu n'en sais a priori rien.

[Pragmateek]

Merci de ces précisions.

[ThE_LaSt]

Un grand merci pour votre aide et toutes ces precisions. La solution avec les structures de bits m'ont seduit avant que vous ne me citiez leur inconveniants. Pour l'instant je vais prendre un char pour chaque cases du tableau. A votre avis, quel serait la solution finale à adopter car le temps joue contre moi ?
Encore merci pour votre disponibilité...

[gl]

Et pourquoi ne pas, comme le suggere Pouic, travailler avec des unsigned int ?

Dans un unsigned int, tu peux stocker (sur ta plateforme) 16 bits grace aux operateurs binaires & et |

http://c.developpez.com/faq/c/?page=...TYPE_acces_bit

[ThE_LaSt]

Et pourquoi ne pas, comme le suggere Pouic, travailler avec des unsigned int ?

Dans un unsigned int, tu peux stocker (sur ta plateforme) 16 bits grace aux operateurs binaires & et |

http://c.developpez.com/faq/c/?page=...TYPE_acces_bit

Merci beaucoup gl, je crois que je tiens ma solution. Mais si t'as le temps, accorde en moi un peu et explique moi mieux comment bien manipuler ces bits. Encore merci !

[PRomu@ld]

La solution dépend de tes propres choix : soit tu cherches la portabilité et donc tu utilises un char, sinon prend les champs de bits sachant qu'ils ne t'apporterons pas forcément un gain de performance (les champs seront surement alignés sur un octet et donc dans la plupart du temps sur un char)

[Emmanuel Delahaye]

Un char occupe un octet, tu ne peux pas travailler au niveau bit en C, sauf si tu passes par une structure avec champs de bits, mais la manipulation n'est plus la même...

Vous pouvez m'en dire un peu plus sur cette structure avec champs de bits S'il vous plaît ?

Euh, as tu ouvert ton livre de C ?

http://emmanuel-delahaye.developpez....s.htm#bitfield

[Emmanuel Delahaye]

Personnellement, j'opte pour les char, tu gagnes 1 octet par variable, c'est pas si mal.

Sur un DSP Texas TMS320C54, les char faisant 16-bit, on ne va pas gagner grand chose. Se méfier des généralisations hatives.

C'est une introduction aux champs de bits, et il le rappelle, ce n'est pas portable, et pour moi, ce n'est pas LA solution.

Les champs de bits utilisés de manière appropriées (interne) sont tout à fait portables, au même titre que les structures. Ce qui n'est pas portable, c'est de s'en servir pour définir des interfaces matérielles ou réseau.