Compter les bits non nuls: banal !!!

Télécharger le projet
Commenter

Description

Pourquoi trouve-t-on des codes 100 fois plus rapides que d'autres ?
Est-ce un problème "trop simple" pour y découvrir quelques astuces ?

Voici 35 méthodes qui comptent les bits (BitCount, Population) et qui vous donneront des éléments de réponse.

Dans cet exposé, il faut remplacer le caractère # par 8, 16, 32 ou 64 selon la taille des mots à traiter.
L'ensemble de tous les sources se trouve dans le fichier Pop.cpp .
 
 

PopA#: comptage


L'idée est de parcourir tous les bits avec un 1 "shifté" à gauche et de compter tous les produits binaires non nuls: 
int PopA#(uint#_t k) {
  int n=0;
  for (int i=0; i<#; i++) if (k&(1<<i)) ++n;
  return n;
}

 
 

PopB#: autre comptage


On peut aussi compter l'imparité du nombre à tester k en le décalant successivement une position à droite:
Dans ce cas, on peut s'arrêter dès que k=0. 
int PopB#(uint#_t k) {
  int n=0;
  do n+=k&1; while (k>>=1);
  return n;
}

 
 

PopC#: comptage pour population éparse


L'instruction k = k&(k-1) est intéressante car elle permet d'éliminer le dernier bit non nul.
Utilisons-la pour ce comptage, efficace lorsque les "1" sont éparses (rares): 
int PopC#(uint#_t k) {
  int n=0;
  while (k) {++n; k&=k-1;}
  return n;
}

 
 

PopD#: additions par groupes


On subdivise d'abord le mot en groupes de 2 bits.
On sélectionne tous les premiers bits de chaque groupe, puis les seconds en les décalant à droite.
Une seule addition suffit alors pour faire les sommes de tous les groupes, qui ne peuvent pas se chevaucher, puisque les sommes sont <= 2.
On répète une méthode similaire basée cette fois sur des groupes de 4 bits, et ainsi de suite. 
int PopD8(uint32_t k) {
  k=(k&0X55)+((k>>1)&0X55);
  k=(k&0X33)+((k>>2)&0X33);
  return (k&0X0F)+(k>>4);
}
int PopD16(uint32_t k) {
  k=(k&0X5555)+((k>>1)&0X5555);
  k=(k&0X3333)+((k>>2)&0X3333);
  k=(k&0X0F0F)+((k>>4)&0X0F0F);
  return (k&0X00FF)+(k>>8);
}
int PopD32(uint32_t k) {
  k=(k&0X55555555)+((k>>1)&0X55555555);
  k=(k&0X33333333)+((k>>2)&0X33333333);
  k=(k&0X0F0F0F0F)+((k>>4)&0X0F0F0F0F);
  k=(k&0X00FF00FF)+((k>>8)&0X00FF00FF);
  return (k&0X0000FFFF)+(k>>16);
}
int PopD64(uint64_t k) {
  k=(k&0X5555555555555555)+((k>> 1)&0X5555555555555555);
  k=(k&0X3333333333333333)+((k>> 2)&0X3333333333333333);
  k=(k&0X0F0F0F0F0F0F0F0F)+((k>> 4)&0X0F0F0F0F0F0F0F0F);
  k=(k&0X00FF00FF00FF00FF)+((k>> 8)&0X00FF00FF00FF00FF);
  k=(k&0X0000FFFF0000FFFF)+((k>>16)&0X0000FFFF0000FFFF);
  return (k&0X00000000FFFFFFFF)+(k>>32);
}

 
 

PopE#: Additions par groupes bis


Avant d'optimiser les codes PopD#, constatons que les deux basés sur 8 ou 16 bits sont nettement plus lents que celui de 32.
Remède: transformer le type uint8_t ou uint16_t du paramètre en uint32_t au début du code.
L'amélioration est surprenante. 
int PopE8(uint8_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X55;
  k=(k&0X33)+((k>>2)&0X33);
  return (k+(k>>4))&0x0F0F;
}
int PopE16(uint16_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X5555;
  k=(k&0X3333)+((k>>2)&0X3333);
  k=(k+(k>>4))&0x0F0F;
  return (k+(k>>8))&0x0000001F;
}

 
 

PopF#: Additions par groupes optimisé


Peut-on encore simplifier les codes PopD# (ou PopE#) ? Il semble que oui.

La première ligne de code, par exemple:
k = (k&0X55555555) + ((k>>1)&0X55555555); peut être remplacée par:  k = k - ((k>>1)&0X55555555);
Contrôlons cela pour les 4 combinaisons possibles dans un groupe à 2 bits:
  00: 0-0=0 ; 01: 1-0=1 ; 10: 2-1=1 ; 11: 3-1=2 .
Résultats qui représentent bien le nombre de bits à 1 dans les différents groupes de 2 bits.

La troisième ligne k = (k&0X0F0F0F0F) + ((k>>4)&0X0F0F0F0F);
peut aussi se simplifier en: k = (k + (k>>4))&0x0F0F0F0F;
En effet, à ce stade, k contient les sommes des groupes de 4 bits, comprises entre 0 et 4.
Comme chaque somme tient dans 4 bits, il suffit d'appliquer le masque 0X0F0F0F0F sur le résultat.

Dans les quatrième et cinquième lignes, on peut même éviter l'utilisation du masque en limitant simplement le résultat à ses 7 premiers bits.
Ce qui donne: 
int PopF32(uint32_t k) {
  k-=(k>>1)&0X55555555;
  k=(k&0X33333333)+((k>>2)&0X33333333);
  k=(k+(k>>4))&0X0F0F0F0F;
  k+=(k>>8);
  k+=(k>>16);
  return k&0X0000003F;
}

Finalement, j'ai retenu dans le fichier 'Pop.cpp' les codes suivants: 
int PopF8(uint8_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X55;
  k=(k&0X33)+((k>>2)&0X33);
  return (k+(k>>4))&0X0F;
}
int PopF16(uint16_t kk) {
  uint32_t k=kk;
  k-=(k>>1)&0X5555;
  k=(k&0X3333)+((k>>2)&0X3333);
  k=(k+(k>>4))&0X0F0F;
  return (k+(k>>8))&0X001F;
}
int PopF32(uint32_t k) {
  k-=(k>>1)&0X55555555;
  k=(k&0X33333333)+((k>>2)&0X33333333);
  k=(k+(k>>4))&0X0F0F0F0F;
  k+=(k>>8);
  return (k+(k>>16))&0X0000003F;
}
int PopF64(uint64_t k) {
  k-=(k>>1)&0X5555555555555555;
  k=(k&0X3333333333333333)+((k>>2)&0X3333333333333333);
  k=(k+(k>>4))&0X0F0F0F0F0F0F0F0F;
  k+=(k>>8);
  k+=(k>>16);
  return (k+(k>>32))&0X0000007F;
}

PopF32 correspond au code proposé dans le "Hacker's Delight".
 
 

PopG#: multiplication


Comme le montre ce tableau,
 0 1 2 3 4 5 6 7 8 9 A B C D E F = k
 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 = n = (k>>1)&0X7777777777777777
 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 = k = k-n
 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 = n = (n>>1)&0X7777777777777777
 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 = k = k-n
 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 = n = (n>>1)&0X7777777777777777
 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 = k = k-n,
les 6 premières lignes de chacun des 4 codes suivants permettent de compter la population par groupe de 4.
Puis, k=(k+(k>>4))&0X0F0F0F0F effectue la somme par byte (ou groupe de 8 bits).
Le produit par 0X0101, 0X01010101 ou 0X0101010101010101 permet de faire d'un coup la somme de tous ces bytes. Exemple: 
//      0X0r0s0t0u * 0X01010101         (avec 0 <= r,s,t,u <= 8)
//    = 0X0r0s0t0u
//    + 0X0s0t0u
//    + 0X0t0u
//    + 0X0u
//    = 0Xzz??????                      (avec zz = r+s+t+u <= 32)

int PopG16(uint16_t kk) {
	uint32_t k=kk,n=(k>>1)&0X7777;
	k-=n;
	n=(n>>1)&0X7777;
	k-=n;
	n=(n>>1)&0X7777;
	k-=n;
	k=(k+(k>>4))&0X0F0F;
  return ((k*0X0101)>>8)&0X1F;
}
int PopG32(uint32_t k) {
	uint32_t n=(k>>1)&0X77777777;
	k-=n;
	n=(n>>1)&0X77777777;
	k-=n;
	n=(n>>1)&0X77777777;
	k-=n;
	k=(k+(k>>4))&0X0F0F0F0F;
	return (k*0X01010101)>>24;
}
int PopG64(uint64_t k) {
	uint64_t n=(k>>1)&0X7777777777777777;
	k-=n;
	n=(n>>1)&0X7777777777777777;
	k-=n;
	n=(n>>1)&0X7777777777777777;
	k-=n;
	k=(k+(k>>4))&0X0F0F0F0F0F0F0F0F;
	return (k*0X0101010101010101)>>56;
}

 
 

PopH#: addition et multiplication


Ici, nous prenons le début de PopF# et la fin de PopG#: 
int PopH16(uint16_t kk) {
	uint32_t k=kk;
	k-=(k>>1)&0X5555;
	k=(k&0X3333)+((k>>2)&0X3333);
	k=(k+(k>>4))&0X0F0F;
  return ((k*0X0101)>>8)&0X1F;
}
int PopH32(uint32_t k) {
	k-=(k>>1)&0X55555555;
	k=(k&0X33333333)+((k>>2)&0X33333333);
	k=(k+(k>>4))&0X0F0F0F0F;
	return (k*0X01010101)>>24;
}
int PopH64(uint64_t k) {
	k-=(k>>1)&0X5555555555555555;
	k=(k&0X3333333333333333)+((k>>2)&0X3333333333333333);
	k=(k+(k>>4))&0X0F0F0F0F0F0F0F0F;
	return (k*0X0101010101010101)>>56;
}

 

PopI#: 256 bytes précomptés


La méthode est basée sur un array de 256 éléments contenant la somme des bits de l'index. 
inline int PopI8(uint8_t k) {return T8[k];}
inline int PopI16(uint16_t k) {return (T8[k&255]+T8[k>>8]);}
inline int PopI32(uint32_t k) {
  return (T8[k&0XFF]+T8[(k>>8)&0XFF]+T8[(k>>16)&0XFF]+T8[k>>24]);
}
inline int PopI64(uint64_t k) {
  return T8[k&0XFF]+T8[(k>>8)&0XFF]+T8[(k>>16)&0XFF]+T8[(k>>24)&0XFF]
    +T8[(k>>32)&0XFF]+T8[(k>>40)&0XFF]+T8[(k>>48)&0XFF]+T8[k>>56];
}

 
 

PopJ#: 65536 shorts précomptés


Et la dernière méthode présentée est basée sur un array de 65536 éléments (T16) contenant la somme des bits de l'index. 
inline int PopJ16(uint16_t k) {return T16[k];}
inline int PopJ32(uint32_t k) {return (T16[k&0XFFFF]+T16[k>>16]);}
inline int PopJ64(uint64_t k) {
  return (T16[k&0XFFFF]+T16[(k>>16)&0XFFFF]+T16[(k>>32)&0XFFFF]+T16[k>>48]);
}

 
 

Temps utilisé pour compter 1 miliard de bits


Dans main(), le vecteur V64 est rempli avec des valeurs aléatoires, et de leur compléments (on a donc exactement la moitié des bits à "1").
V64 est alors analysé en tant que array of uint8_t, uint16_t, uint32_t, uint64_t, selon le type de fonction.
Vous pouvez aussi compiler (en release) et exécuter le fichier Pop.cpp.

PopA: comptage
   8 Bits: s=500000000, t=2605 ms
  16 Bits: s=500000000, t=3759 ms
  32 Bits: s=500000000, t=3588 ms
  64 Bits: s=500000000, t=5835 ms
PopB: autre comptage
   8 Bits: s=500000000, t=1138 ms
  16 Bits: s=500000000, t=4243 ms
  32 Bits: s=500000000, t=920 ms
  64 Bits: s=500000000, t=1872 ms
PopC: comptage pour population éparse
   8 Bits: s=500000000, t=1482 ms
  16 Bits: s=500000000, t=858 ms
  32 Bits: s=500000000, t=561 ms
  64 Bits: s=500000000, t=1061 ms
PopD: addition par groupes
   8 Bits: s=500000000, t=405 ms
  16 Bits: s=500000000, t=249 ms
  32 Bits: s=500000000, t=31 ms
  64 Bits: s=500000000, t=171 ms
PopE: addition par groupes bis
   8 Bits: s=500000000, t=78 ms
  16 Bits: s=500000000, t=47 ms
PopF: addition par groupes optimisé
   8 Bits: s=500000000, t=78 ms
  16 Bits: s=500000000, t=60 ms
  32 Bits: s=500000000, t=31 ms
  64 Bits: s=500000000, t=156 ms
PopG: multiplication
  16 Bits: s=500000000, t=62 ms
  32 Bits: s=500000000, t=31 ms
  64 Bits: s=500000000, t=202 ms
PopH: addition et multiplication
  16 Bits: s=500000000, t=46 ms
  32 Bits: s=500000000, t=31 ms
  64 Bits: s=500000000, t=172 ms
PopI: 256 bytes précomptés
   8 Bits: s=500000000, t=78 ms
  16 Bits: s=500000000, t=78 ms
  32 Bits: s=500000000, t=109 ms
  64 Bits: s=500000000, t=94 ms
PopJ: 65536 shorts précomptés
  16 Bits: s=500000000, t=62 ms
  32 Bits: s=500000000, t=62 ms
  64 Bits: s=500000000, t=69 ms

J'espère que ces mesures vous aideront à formuler votre propre conclusion.

Remarque: il me semble que les méthodes basés sur 64 bits sont relativement lentes, alors que mon système fonctionne sur 64 bits.
J'ai remarqué que MS VS Express 2013 charge kernel32.dll.
Existe-t-il un équivalent 64 bits "kernel64.dll" ?
Merci d'avance à ceux qui voudraient bien éclairer ma lanterne.

Le zip comprend les fichiers "Pop.cpp" et "Description.txt"
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (William VOIROL)