c++ operator Quelle est la manière efficace de compter les bits de réglage à une position ou inférieure?




operator bitwise (4)

std::bitset<64> bits avec un nombre quelconque de bits défini et une position de bit X (0-63)

Quelle est la manière la plus efficace de compter les bits à la position X ou inférieure ou de retourner 0 si le bit à X n'est pas défini

Note: Si le bit est défini, le retour sera toujours au moins 1

La voie de la force brute est très lente:

int countupto(std::bitset<64> bits, int X)
{
  if (!bits[X]) return 0;
  int total=1;
  for (int i=0; i < X; ++i)
  {
    total+=bits[i];
  }
  return total;
}

Le methof count() methof de bitset vous donnera le popcount de bits de tous les bits, mais bitset ne supporte pas les plages

Note: Ce n'est pas un dup de Comment compter le nombre de bits définis dans un entier de 32 bits? comme cela pose des questions sur tous les bits non compris entre 0 et X


En supposant qu'un unsigned long ou unsigned long long est assez grand pour contenir 64 bits, vous pouvez appeler bits.to_unlong() (ou bits.to_ullong() ) pour obtenir les données de bitet sous forme d'entier, masquer les bits au-dessus de X (1 << X) - 1 ) comptez ensuite ces bits comme indiqué dans la réponse à la question à laquelle vous accédez.


Ce C ++ obtient g ++ pour émettre un très bon ASM x86 (explorateur de compilateur godbolt) . Je m'attends à ce qu'il compile efficacement sur d'autres architectures 64 bits (s'il existe un popcount HW pour std::bitset::count , sinon ce sera toujours la partie la plus lente):

#include <bitset>

int popcount_subset(std::bitset<64> A, int pos) {
  int high_bits_to_eliminate = 63 - pos;
  A <<= (high_bits_to_eliminate & 63);  // puts A[pos] at A[63].

  return (A[63]? ~0ULL : 0) & A.count();  // most efficient way: great code with gcc and clang
  // see the godbolt link for some #ifdefs with other ways to do the check, like
    // return A[BSET_SIZE-1] ? A.count() : 0;
}

Ce n'est probablement pas optimal sur les architectures 32 bits, donc comparez les autres alternatives si vous avez besoin de créer une version 32 bits.

Cela fonctionnera pour d'autres tailles de bits , à condition que vous fassiez quelque chose à propos des 63 s codés en dur et que vous remplaciez le masque & 63 pour le compte de décalage par un contrôle de portée plus général. Pour des performances optimales avec des bits de taille étrange, créez une fonction de modèle avec une spécialisation pour la size <= register width du size <= register width de la machine cible. Dans ce cas, extrayez le bitset dans un type unsigned de la largeur appropriée et déplacez-le vers le haut du registre au lieu du haut du jeu de bits.

Vous vous attendez à ce que cela génère également un code idéal pour les bitset<32> , mais ce n’est pas tout à fait le cas. gcc / clang utilise toujours les registres 64 bits sur x86-64.

Pour les gros bits, le déplacement de l'ensemble sera plus lent que le simple comptage des mots sous celui contenant pos et l'utilisation de ce mot. (C'est là qu'un popcount vectorisé brille vraiment sur x86 si vous pouvez assumer SSSE3 mais pas le popcnt matériel de popcnt, ou pour les cibles 32 bits. AVh2 pshufb 256 pshufb est le moyen le plus rapide de générer des popcounts, mais sans AVX2 près d'une implémentation pshufb 128 bits. Voir les commentaires pour plus de discussion.)

Si vous avez un tableau d'éléments 64 bits, et que vous voulez compter les bits au-dessous d'une certaine position dans chacun d'eux, vous devez utiliser SIMD . Les parties décalées de cet algorithme vectorisent, pas seulement la partie popcnt. Utilisez psadbw sur un registre à zéro zéro pour les octets à somme horizontale dans les pshufb 64 bits après un pshufb basé sur pshufb qui génère des comptages pour les bits de chaque octet séparément. SSE / AVX ne possède pas de décalage arithmétique 64 bits à droite, mais vous pouvez utiliser une technique différente pour fusionner le bit supérieur de chaque élément.

Comment je suis arrivé avec ceci:

Les instructions asm que vous souhaitez que le compilateur produise seront:

  1. supprimer les bits indésirables de la valeur 64 bits
  2. tester le plus haut des bits souhaités.
  3. le dénombrer
  4. renvoie 0 ou popcount, en fonction du résultat du test. (Les implémentations sans embranchement ou de branchement présentent des avantages. Si la branche est prévisible, une implémentation sans embranchement a tendance à être plus lente.)

La manière évidente de faire 1 est de générer un masque ( (1<<(pos+1)) -1 ) et & it. Une méthode plus efficace consiste à effectuer un décalage de 63-pos , en laissant les bits que vous souhaitez placer en haut du registre.

Cela a aussi l’effet secondaire intéressant de placer le bit que vous voulez tester comme le bit supérieur du registre. Tester le bit de signe, plutôt que tout autre bit arbitraire, nécessite un peu moins d'instructions. Un décalage arithmétique à droite peut diffuser le bit de signe dans le reste du registre, ce qui permet un code sans branchement plus efficace que d'habitude.

Faire le décompte de masse est un problème très discuté, mais est en fait la partie la plus délicate du puzzle. Sur x86, il existe un support matériel extrêmement efficace, mais uniquement sur du matériel récent. Sur les processeurs Intel, l'instruction popcnt n'est disponible que sur Nehalem et les versions plus récentes. J'oublie quand AMD a ajouté le support.

Donc, pour l'utiliser en toute sécurité, vous devez soit faire la répartition de la CPU avec un repli qui n'utilise pas popcnt . Ou bien, créez des fichiers binaires distincts qui dépendent / dépendent de certaines fonctionnalités du processeur.

popcount sans l'instruction popcnt peut être fait de plusieurs manières. On utilise le pshufb SSSE3 pour implémenter une LUT 4 bits. Ceci est plus efficace quand il est utilisé sur un tableau entier plutôt que sur un seul 64b à la fois. Les bithacks scalaires pourraient être les meilleurs ici et ne nécessiteraient pas SSSE3 (et seraient donc compatibles avec les anciens processeurs AMD qui ont 64 bits mais pas pshufb).

Le Bitbroadcast:

(A[63]? ~0ULL : 0) demande au compilateur de diffuser le bit haut à toutes les autres positions de bit, lui permettant d'être utilisé comme masque AND pour mettre à zéro (ou non) le résultat de popcount. Notez que même pour les grandes tailles de bits, il ne fait que masquer la sortie de popcnt , pas le bitet lui-même, donc ~0ULL c'est bien J'ai utilisé ULL pour m'assurer de ne jamais diffuser le bit au bas 32b du un registre (avec UL sur Windows, par exemple).

Cette diffusion peut être effectuée avec un décalage arithmétique à droite de 63, qui se décale en copies du bit haut.

clang a généré ce code à partir de la version originale. Après quelques explications de Glenn sur les différentes implémentations pour 4 , je me suis rendu compte que je pouvais diriger gcc vers la solution optimale de Clang en écrivant la source plus comme le ASM que je veux. Le plus évident ((int64_t)something) >> 63 demande plus directement un décalage arithmétique à droite ne serait pas strictement portable, car les décalages à droite signés sont définis en termes d'arithmétique ou de logique . La norme ne fournit aucun opérateur de calcul arithmétique portable à droite. (Ce n'est pas un comportement non défini , cependant.) Quoi qu'il en soit, heureusement, les compilateurs sont assez intelligents: gcc voit le meilleur moyen une fois que vous lui avez donné un indice suffisant.

Cette source fait du bon code sur x86-64 et ARM64 avec gcc et clang. Les deux utilisent simplement un décalage arithmétique à droite de l'entrée à popcnt (le décalage peut donc s'exécuter en parallèle avec le popcnt). Il compile également très bien sur 32 bits x86 avec gcc, car le masquage ne se produit que sur une variable 32 bits (après l'ajout de plusieurs résultats popcnt). C'est le reste de la fonction qui est désagréable sur 32 bits (quand le bitet est plus grand qu'un registre).

Version opérateur ternaire originale avec gcc

Compilé avec gcc 5.3.0 -O3 -march=nehalem -mtune=haswell (les anciennes -O3 -march=nehalem -mtune=haswell gcc, comme 4.9.2, émettent aussi ceci):

; the original ternary-operator version.  See below for the optimal version we can coax gcc into emitting.
popcount_subset(std::bitset<64ul>, int):
    ; input bitset in rdi, input count in esi (SysV ABI)
    mov     ecx, esi    ; x86 variable-count shift requires the count in cl
    xor     edx, edx    ; edx=0 
    xor     eax, eax    ; gcc's workaround for popcnt's false dependency on the old value of dest, on Intel
    not     ecx         ; two's complement bithack for 63-pos (in the low bits of the register)
    sal     rdi, cl     ; rdi << ((63-pos) & 63);  same insn as shl (arithmetic == logical left shift)
    popcnt  rdx, rdi
    test    rdi, rdi    ; sets SF if the high bit is set.
    cmovs   rax, rdx    ; conditional-move on the sign flag
    ret

Voir Comment prouver que l'instruction C -x, ~ x + 1 et ~ (x-1) produisent les mêmes résultats? pour le fond sur l'utilisation de gcc de l'identité -x == ~x + 1 two complément. (Et les 2 qui complètent les opérations sur les entiers peuvent être utilisés sans mettre à zéro les bits hauts dans les entrées, si seulement la partie basse du résultat est souhaitée, ce qui mentionne tangentiellement que shl masque le compte de décalage. maintenez 63 - pos principalement ce lien parce que je l'ai écrit récemment et que quiconque lit encore ce paragraphe le trouve peut-être intéressant.)

Certaines de ces instructions disparaîtront lors de l'inclusion. (par exemple, gcc génèrerait le compte dans ecx en premier lieu.)

Avec Glenn se multiplie au lieu de l’opération d’opérateur ternaire (activée par USE_mul ), gcc fait

    shr     rdi, 63
    imul    eax, edi

à la fin au lieu de xor / test / cmovs .

Analyse de perf Haswell , utilisant les données de microarch de Agner Fog (version Multiply):

  • mov r,r : 1 uop de domaine fusionné, 0 latence, aucune unité d'exécution
  • xor -zeroing: 1 uop de domaine fusionné, pas d'unité d'exécution
  • not : 1 uop pour p0 / p1 / p5 / p6, 1c de latence, 1 pour 0.25c
  • shl (aka sal ) avec un compte en cl : 3 uops pour p0 / p6: latence 2c, 1 pour un débit 2c. (Les données d'Agner Fog indiquent que IvyBridge n'en prend que 2, étrangement.)
  • popcnt : 1 uop pour p1, 3c latence, 1 par 1c
  • shr r,imm : 1 uop pour p0 / p6, 1c latence. 1 pour 0,5c de débit.
  • imul r,r : 1uop pour la latence p1, 3c.
  • sans compter le ret

Totaux:

  • 9 uops de domaine fusionné, peuvent émettre en cycles de 2,25 (en théorie, les effets de ligne de cache ne gênent généralement pas le frontend).
  • 4 uops (décalages) pour p0 / p6. 2 uops pour p1. 1 port UAL-any. Peut exécuter à un par 2c (saturer les ports de décalage), de sorte que le frontend est le pire goulot d'étranglement.

Latency: chemin critique à partir duquel le bitet est prêt lorsque le résultat est: shl (2) -> popcnt (3) -> imul (3). Total 8 cycles . Ou 9c à partir du moment où pos est prêt, car le not est une latence supplémentaire de 1c pour lui.

La version bitbroadcast optimale remplace shr avec sar (même perf), et imul avec and (latence 1c au lieu de 3c, s'exécute sur n'importe quel port). Ainsi, le seul changement possible est la réduction de la latence du chemin critique à 6 cycles . Le débit est toujours goulot sur le frontend. and être capable de s'exécuter sur n'importe quel port ne fait aucune différence, à moins que vous ne mélangiez cela avec du code qui gêne le port1 (au lieu de regarder le débit pour exécuter uniquement ce code dans une boucle serrée).

version cmov (opérateur ternaire) : 11 uops de domaine fusionné (frontend: un pour 2,75 c ). unités d'exécution: toujours goulot sur les ports de poste (p0 / p6) à un par 2c. Latence : 7c de bitset à résultat, 8c de pos à résultat. ( cmov est la latence 2c, 2 uops pour l'un des p0 / p1 / p5 / p6.)

Clang a quelques astuces: Au lieu de test / cmovs , il génère un masque de tout-ou-tout en utilisant un décalage arithmétique à droite pour diffuser le bit de signe à toutes les positions d'un registre. Je l'adore: utiliser and au lieu de cmov est plus efficace sur Intel. Il a toujours la dépendance aux données et fait le travail des deux côtés de la branche (ce qui est le principal inconvénient de cmov en général), cependant. Mise à jour: avec le bon code source, gcc utilisera également cette méthode.

clang 3.7 -O3 -Wall -march=nehalem -mtune=haswell

popcount_subset(std::bitset<64ul>, int):
    mov     ecx, 63
    sub     ecx, esi      ; larger code size, but faster on CPUs without mov-elimination
    shl     rdi, cl       ; rdi << ((63-pos) & 63)
    popcnt  rax, rdi      ; doesn't start a fresh dep chain before this, like gcc does
    sar     rdi, 63       ; broadcast the sign bit
    and     eax, edi      ; eax = 0 or its previous value
    ret

sar / and remplace xor / test / cmov , et cmov est une instruction 2 uop sur les processeurs Intel, donc c'est vraiment sympa. (Pour la version opérateur ternaire).

Clang fait toujours sar / and trick au lieu d'une imul réelle en utilisant la version source multiply, ou la version source "bitbroadcast". Donc ceux qui aident gcc sans blesser le clang. ( sar/and est certainement mieux que shr/imul : 2c moins de latence sur le chemin critique). .

Le mov ecx, 63 / sub ecx, esi est en fait plus rapide sur les processeurs sans mov-suppression pour reg, reg move (latence nulle et pas de port d'exécution, géré par changement de registre). Cela inclut les processeurs Intel pré-IvyBridge, mais pas les processeurs Intel et AMD plus récents.

La méthode mov imm / sub Clang ne met qu'un seul cycle de latence pour pos sur le chemin critique (au-delà du bitet-> latence du résultat), au lieu de deux pour un mov ecx, esi / not ecx sur les CPU où mov r,r a 1c latence .

Avec BMI2 (Haswell et versions ultérieures), une version ASM optimale peut enregistrer un mov en ecx . Tout le reste fonctionne de la même manière, car shlx masque son registre d’entrée de décompte jusqu’à la taille de l’opérande, tout comme shl .

Les instructions de décalage x86 ont une sémantique délirante de CISC où, si le nombre de décalage est égal à zéro, les indicateurs ne sont pas affectés. Les instructions de décalage à nombre variable ont donc une dépendance (potentielle) par rapport à l'ancienne valeur des indicateurs. "Normal" x86 shl r, cl décode à 3 uops sur Haswell, mais BMI2 shlx r, r, r est seulement 1. Il est donc dommage que gcc émette toujours sal avec -march=haswell , au lieu d'utiliser shlx (ce qu'il fait utiliser dans certains autres cas).

// hand-tuned BMI2 version using the NOT trick and the bitbroadcast
popcount_subset(std::bitset<64ul>, int):
    not     esi           ; The low 6 bits hold 63-pos.  gcc's two-s complement trick
    xor     eax, eax      ; break false dependency on Intel.  maybe not needed when inlined.
    shlx    rdi, rdi, rsi ; rdi << ((63-pos) & 63)
    popcnt  rax, rdi
    sar     rdi, 63       ; broadcast the sign bit: rdi=0 or -1
    and     eax, edi      ; eax = 0 or its previous value
    ret

Analyse des performances pour Intel Haswell: 6 uops de domaine fusionnés ( frontend: un par 1.5c ). Unités d'exécution: 2 changements de rapport p0 / p6. 1 p1 uop. 2 ports de n'importe quel port: (un par 1,25 c des limites du port d'exécution total). Latence du chemin critique: shlx (1) -> popcnt (3) -> and (1) = 5c bitset-> resultat. (ou 6c de pos -> résultat).

Notez que lors de l’inclusion, un humain (ou un compilateur intelligent) pourrait éviter le besoin de xor eax, eax . Il est seulement présent à cause de la fausse dépendance de popcnt sur le registre de sortie (sur Intel) , et nous avons besoin de la sortie dans eax (que l'appelant a peut-être utilisé récemment pour une longue chaîne dep). Avec -mtune=bdver2 ou quelque chose, gcc -mtune=bdver2 pas le registre qu'il utilisera pour la sortie popcnt .

Lors de l 'insertion, nous pourrions utiliser un registre de sortie qui doit déjà être prêt au moins aussi tôt que le popcnt source de popcnt pour éviter le problème. Les compilateurs vont faire un popcnt rdi,rdi quand la source n'est pas nécessaire plus tard, mais ce n'est pas le cas ici. Au lieu de cela, nous pouvons choisir un autre registre qui doit déjà être prêt avant la source. L'entrée de popcnt dépend de 63-pos , et nous pouvons la popcnt rsi,rdi la dépendance de popcnt rsi,rdi sur le rsi ne peut pas le retarder. Ou si nous avions 63 dans un registre, nous pourrions popcnt rsi,rdi / sarx rax, rsi, reg_63 / and eax, esi . Ou les instructions de changement de 3 opérandes BMI2 nous permettraient également de ne pas écraser les entrées au cas où elles seraient nécessaires par la suite.

Ceci est si léger que la boucle en tête et la configuration des opérandes d'entrée / le stockage des résultats seront des facteurs majeurs. (Et le 63-pos permet d’optimiser avec une constante de compilation ou d’où vient le nombre de variables).

Le compilateur Intel se lance avec amusement dans le pied et ne profite pas du fait que A [63] est le bit de signe. shl / bt rdi, 63 / jc . Il installe même les branches d'une manière vraiment stupide. Il pourrait zéro eax, puis sauter par-dessus popcnt ou pas en fonction de l'indicateur de signe défini par shl .

Une implémentation optimale des branchements , à partir de la sortie ICC13 de -O3 -march=corei7 sur godbolt:

   // hand-tuned, not compiler output
        mov       ecx, esi    ; ICC uses neg/add/mov :/
        not       ecx
        xor       eax, eax    ; breaks the false dep, or is the return value in the taken-branch case
        shl       rdi, cl
        jns    .bit_not_set
        popcnt    rax, rdi
.bit_not_set:
        ret

C'est à peu près optimal: Le cas A[pos] == true a une branche non prise. Cela n'économise pas beaucoup sur la méthode sans branchement, cependant.

Si la casse A[pos] == false est plus fréquente: popcnt dessus une instruction ret pour un popcnt / ret . (Ou après l'inlining: sauter à un bloc à la fin qui fait le popcnt et saute en arrière).


Ma réaction immédiate serait de tester le bit spécifié, et de retourner immédiatement 0 de celui-ci.

Si vous réussissez, créez un masque de bits avec ce bit (et les bits les moins significatifs), and cela avec l'entrée d'origine. Ensuite, utilisez la fonction membre count() pour obtenir le nombre de bits défini dans le résultat.

Comme pour la création du masque: vous pouvez décaler 1 N à gauche, puis soustraire 1.


J'ai édité un problème que j'ai déjà vu et qui vérifie si un nombre impair ou pair de bits est défini dans un nombre. C'est pour C mais il ne devrait pas être trop difficile de le masser en C ++. Le nœud de la solution réside dans la boucle while. Essayez-le sur papier pour comprendre comment il choisit le LSB et le supprime ensuite de x. Le reste du code est simple. Le code s'exécute dans O (n), où n est le nombre de bits définis dans x. C'est beaucoup mieux que le temps linéaire que je pensais également être seulement possible en regardant ce problème pour la première fois.

#include <stdio.h>

int
count(long x, int pos)
{
    /* if bit at location pos is not set, return 0 */
    if (!((x >> pos) & 1))
    {
        return 0;
    }

    /* prepare x by removing set bits after position pos */
    long tmp = x;
    tmp = tmp >> (pos + 1);
    tmp = tmp << (pos + 1);
    x ^= tmp;

    /* increment count every time the first set bit of x is removed (from the right) */
    int y;
    int count = 0;
    while (x != 0)
    {
        y = x & ~(x - 1);
        x ^= y;
        count++;
    }
    return count;
}

int
main(void)
{
    /* run tests */
    long num = 0b1010111;
    printf("%d\n", count(num, 0)); /* prints: 1 */
    printf("%d\n", count(num, 1)); /* prints: 2 */
    printf("%d\n", count(num, 2)); /* prints: 3 */
    printf("%d\n", count(num, 3)); /* prints: 0 */
    printf("%d\n", count(num, 4)); /* prints: 4 */
    printf("%d\n", count(num, 5)); /* prints: 0 */
    printf("%d\n", count(num, 6)); /* prints: 5 */
}




bit-manipulation