Tableau de bits

Bonjour, Voilà mon problème:
je dois faire un tableau de bits avec lecture/écriture la taille du tableau est variable, et la limite haute de taille nes pas spécialement définie, mais disons 1000000 pour l'exemple....
du coup le fais une allocation du style:

Code:

---

1 2 3 4 5 6

static const unsigned char bits_in_char =8;   unsigned char* allocate(unsigned int taille) { return (unsigned char*)malloc(taille/bits_in_char + 1); }

---

pour les fonctions de lecture/écriture

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

bool get_bit(unsigned char* tab,unsigned int index){ unsigned int kn,in; kn=(index+bits_in_char-1)/bits_in_char; in=(index-1)%bits_in_char; return (1 & (tab[kn] >> in)); }   void set_bit(unsigned char* tab,unsigned int index,bool val){ unsigned int kn,in; kn=(index+bits_in_char-1)/bits_in_char; in=(index-1)%bits_in_char; if (val) tab[kn]= tab[kn] | (1 << in); else tab[kn]= tab[kn] & ~(1 << in); }

---

Mon soucis c'est que ces fonctions (surtout la lecture) sont appelée un très grand nombre de fois. Et je constate que c'est lent!

Est-ce qu'il y a un meilleur moyen de définir/lire/écrire un tableau de bits?

En premier lieu, utilise CHAR_BIT plutôt qu'une constante à toi.

Hé oui, l'accès à un tableau de bits sera toujours plus lent qu'un tableau du type natif int où chaque entier fait office de bascule binaire ! ;) Bon en pratique c'est loin d'être aussi simple, ça dépend de beaucoup de choses notamment la quantité de données que tu as besoin de rapatrier dans le cache à chaque session de bit fiddling...

Difficile donc d'accuser le code proposé sans voir le reste de ton programme. Quelques pistes cependant pour accélérer l'exécution de tes routines :

• compile avec -O2 ;
• utilise un tableau d'int ou d'unsigned int pour stocker les bits (à la rigueur (u)int_fast64_t lorsque tu compiles sous Windows 64 bit) ;
• d'une manière générale, utilise également et exclusivement des int au sein des opérations arithmétiques (pas de char, pas de bool...) ;
• évite les branchements conditionnels if...else dans les routines d'accès, utilise uniquement de l'arithmétique et des opérateurs bit à bit ;
• inline tes fonctions ou fais-en des macros.

Tu peux vérifier la sortie assembleur du compilateur pour t'assurer de l'impact de tes modifications.

Bonjour,

+1
Une fois compilé en optimisé get_bit() fait 3 instructions assembleur en ARM ou 5 en Intel. A condition que les fonctions soient inline.
Utiliser des int plutôt que des char permet une meilleure optimisation (l'accès mémoire char fait perdre un cycle).
En ayant des index qui commencent à 1 plutôt qu'à 0, on perd aussi un cycle précieux

Code:

---

1 2 3 4 5

inline bool get_bit( const unsigned* tab , unsigned int index ) { unsigned kn = index / INT_BIT; unsigned in = index % INT_BIT; return 1 & tab[kn] >> in; }

---

Citation:

---

Envoyé par dalfab

En ayant des index qui commencent à 1 plutôt qu'à 0, on perd aussi un cycle précieux

---

Bien vu, ça..


J'allais aussi oublier le classique : ne caste pas le résultat de malloc ! :mrgreen: