Le moyen le plus rapide de compter les bits

Dupliquer possible:
Comment compter le nombre de bits définis dans un entier de 32 bits?

Donnez une valeur de type de caractère non signé, comptez le nombre total de bits qu’il contient. Quel est le moyen le plus rapide? J’ai écrit trois fonctions comme ci-dessous, quel est le meilleur moyen, et quelqu’un peut-il en proposer une plus rapide? (Je veux juste la très rapide)

const int tbl[] = { #define B2(n) n, n+1, n+1, n+2 #define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2) #define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2) B6(0), B6(1), B6(1), B6(2) }; char naivecount (unsigned char val) { char cnt = 0; while (val) { cnt += (val & 1); val = val >> 1; } return cnt; } inline tableLookUp(int val) { assert(val >= 0 && val <= 255); return tbl[val]; } int asmCount(int val) { int res = 0; asm volatile("xor %0, %0\n\t" "begin:\n\t" "cmp $0x0, %1\n\t" "jle end\n\t" "movl %1, %%ecx\n\t" "and $0x1, %%ecx\n\t" "addl %%ecx, %0\n\t" "shrl %1\n\t" "jmp begin\n\t" "end:" : "=r"(res) : "r" (val)); return res; } 

MODIFIER:

J’ai testé toute la méthode, la plus rapide consiste à utiliser l’instruction popcntl plate-forme sans instruction, j’utiliserai une table de recherche.

Si vous voulez le coder à la main, essayez ceci:

 #include  int popcnt8(uint8_t x) { x = (x & 0x55) + (x >> 1 & 0x55); x = (x & 0x33) + (x >> 2 & 0x33); x = (x & 0x0f) + (x >> 4 & 0x0f); return x; } 

sur x86, cela comstack en (syntaxe AT & T):

 popcnt8: movl %edi, %eax shrb %dil andl $85, %eax andl $85, %edi addl %eax, %edi movl %edi, %eax shrb $2, %dil andl $51, %eax andl $51, %edi addl %eax, %edi movl %edi, %eax shrb $4, %dil andl $15, %eax addl %edi, %eax movzbl %al, %eax ret 

Comparez ceci à ce que gcc génère avec l’insortingnsèque:

 #include  int popcnt8_insortingn(uint8_t x) { return __builtin_popcount(x); } 

Sur x86 avec SSE 4.2:

 popcnt8_insortingn: movzbl %dil, %eax popcntl %eax, %eax ret 

ce qui n’est pas optimal; Clang génère:

 popcnt8_insortingn: popcntl %edi,%eax ret 

réduire le calcul à une (!) instruction.

Sur x86 sans SSE 4.2:

 popcnt8_insortingn: subq $8, %rsp movzbl %dil, %edi call __popcountdi2 addq $8, %rsp ret 

gcc appelle essentiellement sa bibliothèque ici. Pas tout à fait optimal. Clang fait un peu mieux:

 popcnt8_insortingn: # @popcnt8_insortingn movl %edi, %eax shrl %eax andl $85, %eax subl %eax, %edi movl %edi, %eax andl $858993459, %eax # imm = 0x33333333 shrl $2, %edi andl $858993459, %edi # imm = 0x33333333 addl %eax, %edi movl %edi, %eax shrl $4, %eax addl %edi, %eax andl $252645135, %eax # imm = 0xF0F0F0F imull $16843009, %eax, %eax # imm = 0x1010101 shrl $24, %eax ret 

Clang calcule le popcnt pour un nombre entier de 32 bits. Ce n’est pas optimal à mon humble avis.

Votre code assembleur serait plus rapide si vous ne réalisiez pas autant de comparaisons et de twigs qui varient entre sockets et non sockets.

Mais il est clair que la méthode la plus rapide consiste à effectuer une recherche sur des octets, d’autant plus que vous n’utilisez que 256 valeurs (vous pouvez utiliser la méthode naïve pour écrire une liste des valeurs, puis static const table[256] = { ... }; return table[value]; dans votre fonction.

Benchmark les différentes solutions.

Je ne serais pas surpris si votre code assembleur est plus lent que le code généré par le compilateur!

Edit: Votre code assembleur serait légèrement plus rapide en faisant:

 int asmCount(int val) { int res = 0; asm volatile("begin:\n\t" "movl %1, %%ecx\n\t" "and $0x1, %%ecx\n\t" "addl %%ecx, %0\n\t" "shrl %1\n\t" "jnz begin\n\t" "end:" : "=r"(res) : "r" (val) : "ecx"); // Important: clobbers ecx! return res; } 

J’ai enlevé le xor (res = 0 devrait le faire quand même), et comparé (bien sûr, si val est zéro, nous exécutons quelques instructions supplémentaires, mais pour tout ce qui a des bits élevés, c’est bien pire, car ce sont deux instructions supplémentaires pour chaque itération, ce qui signifie potentiellement 16 instructions supplémentaires – dont l’une est une twig!), et a changé le saut en jnz à la fin de la boucle. C’est probablement à peu près ce que le compilateur génère dans votre premier cas. Essayer de battre le compilateur avec du code simple n’est pas si simple!