Discussion :

[genteur slayer]

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 :

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

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 :

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

[Matt_Houston]

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.

[dalfab]

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 :

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

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;
}

[Matt_Houston]

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 !