Quel est le moyen le plus rapide de retourner les positions de tous les bits définis dans un entier 64 bits?

Je pense que la clé de la performance ici est de se concentrer sur le problème plus large plutôt que sur la micro-optimisation de l’extraction des positions de bits à partir d’un entier aléatoire.

A en juger par votre exemple de code et votre précédente question SO, vous enregistrez tous les mots avec K bits définis dans l’ordre, et vous en extrayez les indices de bits. Cela simplifie grandement les choses.

Si c’est le cas, au lieu de reconstruire la position du bit, chaque itération essaye d’incrémenter directement les positions dans le tableau de bits. La moitié du temps, cela impliquera une itération et un incrément de boucle unique.

Quelque chose dans ce sens:

 // Walk through all len-bit words with num-bits set in order void enumerate(size_t num, size_t len) { size_t i; unsigned int bitpos[64 + 1]; // Seed with the lowest word plus a sentinel for(i = 0; i < num; ++i) bitpos[i] = i; bitpos[i] = 0; // Here goes the main loop do { // Do something with the resulting data process(bitpos, num); // Increment the least-significant series of consecutive bits for(i = 0; bitpos[i + 1] == bitpos[i] + 1; ++i) bitpos[i] = i; // Stop on reaching the top } while(++bitpos[i] != len); } // Test function void process(const unsigned int *bits, size_t num) { do printf("%d ", bits[--num]); while(num); putchar('\n'); } 

Pas particulièrement optimisé mais vous obtenez l'idée générale.

Voici quelque chose de très simple qui pourrait être plus rapide – pas de moyen de savoir sans tester. Beaucoup dépendra du nombre de bits défini par rapport au nombre non défini. Vous pouvez dérouler cela pour supprimer les twigments, mais avec les processeurs actuels, je ne sais pas si cela accélèrerait.

 unsigned char idx[K+1]; // need one extra for overwrite protection unsigned char *dst=idx; for (unsigned char i = 0; i < 50; i++) { *dst = i; dst += x & 1; x >>= 1; } 

PS votre sortie échantillon dans la question est incorrecte, voir http://ideone.com/2o032E

En tant que modification minimale:

 int64_t x; char idx[K+1]; char *dst=idx; const int BITS = 8; for (int i = 0 ; i < 64+BITS; i += BITS) { int y = (x & ((1<>= BITS; } 

Le choix de BITS détermine la taille de la table. 8, 13 et 16 sont des choix logiques. Chaque entrée est une chaîne, terminée par zéro et contenant des positions de bit avec 1 décalage. Ie onglet [5] est "\x03\x01" . La boucle interne corrige ce décalage.

Légèrement plus efficace: remplacez le strcat et la boucle interne par

 char const* ptr = tab[y]; while (*ptr) { *dst++ = *ptr++ + (i-1); } 

Le déroulement de la boucle peut être un peu pénible si la boucle contient des twigs, car la copie de ces instructions de twig n’aide pas le prédicteur de twig. Je vais volontiers laisser cette décision au compilateur.

Une chose que je considère, c’est que l’ tab[y] est un tableau de pointeurs vers des chaînes. Celles-ci sont très similaires: "\x1" est un suffixe de "\x3\x1" . En fait, chaque chaîne qui ne commence pas par "\x8" est un suffixe d’une chaîne qui le fait. Je me demande combien de chaînes uniques vous avez besoin et dans quelle mesure l’ tab[y] est en fait nécessaire. Par exemple, par la logique ci-dessus, tab[128+x] == tab[x]-1 .

[modifier]

Bien sûr, vous avez besoin de 128 entrées de tabulation commençant par "\x8" car elles ne sont jamais le suffixe d’une autre chaîne. Cependant, la règle de l’ tab[128+x] == tab[x]-1 signifie que vous pouvez enregistrer la moitié des entrées, mais au prix de deux instructions supplémentaires: char const* ptr = tab[x & 0x7F] - ((x>>7) & 1) . (Configurez l’ tab[] pour qu’il pointe après le \x8 )

Utiliser char ne vous aidera pas à augmenter la vitesse, mais nécessite en fait plus de ANDing et de sign / zero pendant le calcul. Seulement dans le cas de très grands tableaux qui doivent tenir dans le cache, des types int plus petits doivent être utilisés

Vous pouvez également améliorer la macro COPY. Au lieu de copier octet par octet, copiez le mot entier si possible

 inline COPY(unsigned char *dst, unsigned char *src, int n) { switch(n) { // remember to align dst and src when declaring case 8: *((int64_t*)dst) = *((int64_t*)src); break; case 7: *((int32_t*)dst) = *((int32_t*)src); *((int16_t*)(dst + 4)) = *((int32_t*)(src + 4)); dst[6] = src[6]; break; case 6: *((int32_t*)dst) = *((int32_t*)src); *((int16_t*)(dst + 4)) = *((int32_t*)(src + 4)); break; case 5: *((int32_t*)dst) = *((int32_t*)src); dst[4] = src[4]; break; case 4: *((int32_t*)dst) = *((int32_t*)src); break; case 3: *((int16_t*)dst) = *((int16_t*)src); dst[2] = src[2]; break; case 2: *((int16_t*)dst) = *((int16_t*)src); break; case 1: dst[0] = src[0]; break; case 0: break; } 

De plus, comme les tabofs [x] et n [x] sont souvent proches les uns des autres, essayez de les rapprocher en mémoire pour vous assurer qu’ils sont toujours en cache en même temps

 typedef struct TAB_N { int16_t n, tabofs; } tab_n[256]; src=tab0+tab_n[b0].tabofs; COPY(dst, src, tab_n[b0].n); src=tab0+tab_n[b1].tabofs; COPY(dst, src, tab_n[b1].n); src=tab0+tab_n[b2].tabofs; COPY(dst, src, tab_n[b2].n); src=tab0+tab_n[b3].tabofs; COPY(dst, src, tab_n[b3].n); src=tab0+tab_n[b4].tabofs; COPY(dst, src, tab_n[b4].n); src=tab0+tab_n[b5].tabofs; COPY(dst, src, tab_n[b5].n); 

Last but not least, gettimeofday n’est pas destiné au comptage des performances. Utilisez plutôt QueryPerformanceCounter , c’est beaucoup plus précis

Votre code utilise la table d’index 1 octet (256 entrées). Vous pouvez l’accélérer par facteur 2 si vous utilisez une table d’index de 2 octets (65536 entrées).

Malheureusement, vous ne pouvez probablement pas étendre cela plus loin – pour une taille de table de 3 octets serait de 16 Mo, pas susceptible de tenir dans le cache local du processeur, et cela ne ferait que ralentir les choses.

La question est ce que vous allez faire avec la collecte des positions?
Si vous devez l’itérer plusieurs fois, alors oui, il pourrait être intéressant de les rassembler une fois, comme vous le faites maintenant, et de les réitérer.
Mais si c’est pour une itération juste une ou plusieurs fois, alors vous pourriez penser à ne pas créer un tableau intermédiaire de positions, et simplement invoquer une fermeture / fonction de bloc de traitement à chaque 1 rencontré en itérant sur des bits.

Voici un exemple naïf d’iterator de bit que j’ai écrit dans Smalltalk:

 LargePositiveInteger>>bitsDo: aBlock | mask offset | 1 to: self digitLength do: [:iByte | offset := (iByte - 1) << 3. mask := (self digitAt: iByte). [mask = 0] whileFalse: [aBlock value: mask lowBit + offset. mask := mask bitAnd: mask - 1]] 

Un LargePositiveInteger est un entier de longueur arbitraire composé de chiffres d'octet. Le lowBit répond au rang du bit le plus bas et est implémenté en tant que table de consultation avec 256 entrées.

En C ++ 2011, vous pouvez facilement passer une fermeture, il devrait donc être facile à traduire.

 uint64_t x; unsigned int mask; void (*process_bit_position)(unsigned int); unsigned char offset = 0; unsigned char lowBitTable[16] = {0,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0}; // 0-based, first entry is unused while( x ) { mask = x & 0xFUL; while (mask) { process_bit_position( lowBitTable[mask]+offset ); mask &= mask - 1; } offset += 4; x >>= 4; } 

L'exemple est démontré avec un tableau de 4 bits, mais vous pouvez facilement l'étendre à 13 bits ou plus s'il tient dans le cache.

Pour la prédiction de twig, la boucle interne pourrait être réécrite comme un for(i=0;i avec une table supplémentaire nbit=numBitTable[mask] puis déroulée avec un switch (le compilateur pourrait le faire?), Mais je laissez-vous mesurer comment il fonctionne d'abord ...