Quel est le moyen le plus rapide de parcourir en boucle un bloc de données volumineux?

Question

Je traverse un bloc de mémoire de données binaires octet par pouce.

Actuellement, je fais quelque chose comme ça:

for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    ((*byte & Masks[0]) == Masks[0]) ? Stats.FreqOf1++; // syntax incorrect but you get the point.
    ((*byte & Masks[1]) == Masks[1]) ? Stats.FreqOf1++;
    ((*byte & Masks[2]) == Masks[2]) ? Stats.FreqOf1++;
    ((*byte & Masks[3]) == Masks[3]) ? Stats.FreqOf1++;
    ((*byte & Masks[4]) == Masks[4]) ? Stats.FreqOf1++;
    ((*byte & Masks[5]) == Masks[5]) ? Stats.FreqOf1++;
    ((*byte & Masks[6]) == Masks[6]) ? Stats.FreqOf1++;
    ((*byte & Masks[7]) == Masks[7]) ? Stats.FreqOf1++;
}

Où masques est:

for (i = 0; i < 8; i++)
{
    Masks[i] = 1 << i;
}

(Je n'ai pas réussi à le faire aussi rapidement dans une boucle ou une fonction en ligne, je l'ai donc écrit.)

Quelqu'un a-t-il des suggestions pour améliorer cette première boucle? Je suis plutôt inexpérimenté avec le fait de tomber en morceaux.

Cela peut sembler une chose stupide à faire. Mais je suis en train de mettre en place un algorithme de compression. Je veux juste que le bit accède à la partie en bas à droite.

Merci!

PS: Cela se trouve dans le compilateur Visual Studio 2008. Donc, ce serait bien si les suggestions appliquées à ce compilateur.

PPS: Je viens de me rendre compte que je n'ai pas besoin d'incrémenter deux comptes. Un suffirait. Calculez ensuite la différence par rapport au nombre total de bits à la fin. Mais ce serait spécifique à juste compter. Ce que je veux vraiment faire rapidement, c'est l'extraction de bits.

EDIT: L'idée de table de consultation qui a été avancée est agréable. Je me rends compte cependant que j'ai posé la question mal dans le titre. En fin de compte, ce que je veux faire n’est pas de compter les bits, mais d’accéder à chaque bit le plus rapidement possible.

UN AUTRE ÉDIT: Est-il possible de faire avancer un pointeur d'un bit dans les données?

UN AUTRE ÉDIT: Merci pour toutes vos réponses jusqu'à présent.

Ce que je veux implémenter dans les prochaines étapes est un codeur arithmétique binaire non sophistiqué qui n’analyse pas le contexte. Donc, je ne suis intéressé que par les bits simples pour le moment. Cela finira par devenir un BAC adaptable au contexte mais je le laisserai pour plus tard.

Le traitement de 4 octets au lieu de 1 octet pourrait être une option. Mais une boucle sur 32 bits est également coûteuse, n'est-ce pas?

Answer 1

Je n'ai pas vraiment compris ce que vous essayez de faire. Mais si vous voulez juste avoir accès aux bits d’un bitmap, vous pouvez utiliser ces fonctions (non testées !!!):

#include <stddef.h>

_Bool isbitset(unsigned char * bitmap, size_t idx)
{
    return bitmap[idx / 8] & (1 << (idx % 8)) ? 1 : 0;
}

void setbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] |= (1 << (idx % 8));
}

void unsetbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] &= ~(1 << (idx % 8));
}

void togglebit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] ^= (1 << (idx % 8));
}

Modifier: OK, je pense que je comprends ce que vous voulez faire: Itération rapide sur une séquence de bits. Par conséquent, nous ne voulons pas utiliser les fonctions d'accès aléatoire d'en haut, mais lire tout un mot de données à la fois.

Vous pouvez utiliser n'importe quel type entier non signé que vous aimez, mais vous devez en choisir un qui corresponde probablement à la taille de mot de votre architecture. Je vais aller avec uint_fast32_t à partir de stdint.h :

uint_fast32_t * data = __data_source__;
for(; __condition__; ++data)
{
    uint_fast32_t mask = 1;
    uint_fast32_t current = *data;
    for(; mask; mask <<= 1)
    {
        if(current & mask)
        {
            // bit is set
        }
        else
        {
            // bit is not set
        }
    }
}

À partir de la boucle interne, vous pouvez définir le bit avec

*data |= mask;

désactive le bit avec

*data &= ~mask;

et basculez le bit avec

*data ^= mask;

Avertissement: le code pourrait se comporter de manière inattendue sur les architectures big-endian!

Answer 2

Le moyen le plus rapide est probablement de créer une table de correspondance des valeurs d'octet par rapport au nombre de bits défini dans cet octet. Du moins, c’était la réponse quand j’ai interviewé chez Google.

Answer 3

Voir le lien suivant pour une douzaine de choses liées au bit: Bit Twiddling Hacks

Answer 4

Utilisez un tableau qui associe chaque valeur d'octet (256) au nombre de 1 qu'elle contient. (Le nombre de 0 est juste (8 - # de 1)). Ensuite, parcourez les octets et effectuez une recherche unique pour chaque octet, au lieu de plusieurs recherches et comparaisons. Par exemple:

int onesCount = 0;
for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    onesCount += NumOnes[byte];
}
Stats.FreqOf1 += onesCount;
Stats.FreqOf0 += (data->Count * 8) - onesCount;

Answer 5

Vous pouvez utiliser une table de recherche précalculée, à savoir:

static int bitcount_lookup[256] = { ..... } ; /* or make it a global and compute the values in code */

...

for( ... ) 
   byte = ... 
   Stats.FreqOf1 += bitcount_lookup[byte];

Answer 6

Voici une méthode pour compter les 1 bits d'un entier 32 bits (basé sur la méthode Integer.bitCount (i) de Java):

unsigned bitCount(unsigned i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    return i & 0x3f;
}

Vous pouvez ainsi convertir vos données en int et avancer par étapes de 4 octets.

Answer 7

Voici un exemple simple que j'ai préparé avec une seule valeur 32 bits, mais vous pouvez voir qu'il ne serait pas difficile de l'adapter à un nombre quelconque de bits ....

int ones = 0;
int x = 0xdeadbeef;
for(int y = 0;y < 32;y++)
{
    if((x & 0x1) == 0x1) ones++;
    x = (x >> 1);
}

printf("%x contains %d ones and %d zeros.\n", x, ones, 32-ones);

Notez cependant qu'il modifie la valeur dans le processus. Si vous le faites sur des données que vous devez conserver, vous devez d’abord en faire une copie.

Faire ceci dans __asm ??serait probablement un meilleur moyen, peut-être plus rapide, mais il est difficile de dire avec quelle efficacité le compilateur peut optimiser ...

Chaque solution que vous envisagez présentera des inconvénients. Une table de correspondance ou un peu décalé (comme le mien) présentent des inconvénients.

Larry

Answer 8

ttobiass - N'oubliez pas que vos fonctions en ligne sont importantes dans les applications dont vous parlez, mais vous devez garder à l'esprit certains éléments. Vous POUVEZ obtenir les performances du code en ligne, souvenez-vous de quelques éléments.

• inline en mode débogage n'existe pas. (Sauf si vous le forcez)
• le compilateur incorporera les fonctions à sa guise. Souvent, si vous lui indiquez d’intégrer une fonction, il se peut qu’il ne le fasse pas du tout. Même si vous utilisez __forceinline. Consultez MSDN pour plus d'informations sur l'inlining.
• Seules certaines fonctions peuvent même être en ligne. Par exemple, vous ne pouvez pas intégrer une fonction récursive.

Vous obtiendrez votre meilleure performance en utilisant les paramètres de votre projet pour le langage C / C ++ et la façon dont vous construisez votre code. À ce stade, il est important de comprendre les opérations Heap vs. Stack, les conventions d’appel, l’alignement de la mémoire, etc.

Je sais que cela ne répond pas exactement à votre question, mais vous parlez de performances et de la manière d'obtenir les meilleures performances. Ces éléments sont essentiels.

Answer 9

Pour rejoindre le lien wagon: compter les bits

Answer 10

S'il ne s'agit pas d'une optimisation prématurée et que vous avez vraiment besoin d'extraire chaque femtoseconde, vous êtes probablement mieux avec un tableau statique de 256 éléments que vous remplissez une fois avec le nombre de bits de chaque valeur d'octet. , puis

  

Stats.FreqOf1 + = bitCountTable [octet]

et lorsque la boucle est terminée:

  

Stats.FreqOf0 = ((data- > Count * 8) - Stats.FreqOf1)

Answer 11

Le livre Beautiful Code contient un chapitre complet sur les différentes techniques utilisées. Vous pouvez le lire (en grande partie) sur les livres Google à partir d'ici. .

Answer 12

Un moyen plus rapide d’extraire des bits consiste à utiliser:

bitmask= data->Data[i];

while (bitmask)
{
    bit_set_as_power_of_two= bitmask & -bitmask;
    bitmask&= bitmask - 1;
}

Si vous souhaitez simplement compter les bits définis, une table d’essai dans le cache serait rapide, mais vous pouvez également le faire en temps constant avec la méthode de comptage de bits entrelacés dans le lien dans cette réponse .