Qual è il / i modo / i più veloce / i per eseguire il loop di un grosso blocco di dati su una base per bit

Question

Sto attraversando un blocco di memoria di dati binari per byte.

Attualmente sto facendo qualcosa del genere:

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++;
}

Dove si trova la maschera:

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

(In qualche modo non sono riuscito a farlo più velocemente in un ciclo o in una funzione incorporata, quindi l'ho scritto.)

Qualcuno ha qualche suggerimento su come migliorare questo primo ciclo? Sono piuttosto inesperto nel ridimensionarmi.

Potrebbe sembrare una cosa stupida da fare. Ma sto implementando un algoritmo di compressione. Voglio solo avere un po 'di accesso alla parte in basso a destra.

Grazie!

PS: è presente nel compilatore di Visual Studio 2008. Quindi sarebbe bello se i suggerimenti si applicassero a quel compilatore.

PPS: ho appena capito che non ho bisogno di incrementare due conteggi. Uno sarebbe abbastanza. Quindi calcola la differenza con i bit totali alla fine. Ma questo sarebbe specifico solo per il conteggio. Quello che voglio davvero fare velocemente è l'estrazione dei bit.

EDIT: L'idea della tabella di ricerca che è stata proposta è piacevole. Mi rendo conto però di aver posto la domanda sbagliata nel titolo. Perché alla fine quello che voglio fare non è contare i bit, ma accedervi il più velocemente possibile.

UN ALTRO EDIT: È possibile far avanzare un puntatore di un solo bit nei dati?

UN ALTRO EDIT: Grazie per tutte le risposte finora.

Quello che voglio implementare nei prossimi passi è un codificatore aritmetico binario non sofisticato che non analizza il contesto. Quindi per ora sono interessato solo a bit singoli. Alla fine diventerà un BAC adattivo al contesto, ma lo lascerò per dopo.

L'elaborazione di 4 byte anziché 1 byte potrebbe essere un'opzione. Ma anche un loop di oltre 32 bit è costoso, vero?

Answer 1

Non ho davvero capito cosa stai cercando di fare. Ma se vuoi solo accedere ai bit di una bitmap, puoi usare queste funzioni (non testate !!!):

#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));
}

Modifica: Ok, penso capisco cosa vuoi fare: iterazione rapida su una sequenza di bit. Pertanto, non vogliamo utilizzare le funzioni di accesso casuale dall'alto, ma leggere un'intera parola di dati contemporaneamente.

Puoi usare qualsiasi tipo intero senza segno che ti piace, ma dovresti sceglierne uno che probabilmente corrisponderà alla dimensione delle parole della tua architettura. Vado con uint_fast32_t da 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
        }
    }
}

Dal ciclo interno, è possibile impostare il bit con

*data |= mask;

disattiva il bit con

*data &= ~mask;

e attiva / disattiva il bit con

*data ^= mask;

Avvertenza: il codice potrebbe comportarsi in modo imprevisto su architetture big-endian!

Answer 2

Il modo più veloce è probabilmente quello di creare una tabella di ricerca di valori di byte rispetto al numero di bit impostati in quel byte. Almeno questa è stata la risposta quando ho intervistato su Google.

Answer 3

Vedi il seguente link per una dozzina di cose relative ai bit: Bit Twiddling Hacks

Answer 4

Utilizzare una tabella che associa ciascun valore di byte (256) al numero di 1 in esso. (Il numero di 0 è solo (8 - N. di 1)). Quindi scorrere i byte ed eseguire una singola ricerca per ogni byte, anziché più ricerche e confronti. Ad esempio:

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

È possibile utilizzare una tabella di ricerca pre-calcolata, ovvero:

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

Ecco un metodo per contare i 1 bit di un numero intero a 32 bit (basato sul metodo Integer.bitCount (i) di 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;
}

Quindi puoi trasmettere i tuoi dati a int e andare avanti con passi di 4 byte.

Answer 7

Eccone uno semplice che ho montato su un singolo valore a 32 bit, ma puoi vedere che non sarebbe difficile adattarlo a qualsiasi numero di bit ....

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);

Si noti tuttavia che modifica il valore nel processo. Se lo stai facendo sui dati che devi conservare, devi prima crearne una copia.

Fare questo in __asm ??sarebbe probabilmente un modo migliore, forse più veloce, ma è difficile dire con che ottimizzazione il compilatore ...

Con ogni soluzione considerata, ognuna presenterà degli svantaggi. Una tabella di ricerca o un po 'shifter (come il mio), hanno entrambi degli svantaggi.

Larry

Answer 8

ttobiass - Tieni presente che le tue funzioni incorporate sono importanti nelle applicazioni di cui stai parlando, ma ci sono cose che devi tenere a mente. PUOI ottenere le prestazioni dal codice inline, ricorda solo un paio di cose.

• inline in modalità debug non esiste. (A meno che non lo forziate)
• il compilatore incorporerà le funzioni come ritiene opportuno. Spesso, se gli dici di incorporare una funzione, potrebbe non farlo affatto. Anche se usi __forceinline. Controlla MSDN per maggiori informazioni sull'inline.
• Solo alcune funzioni possono anche essere incorporate. Ad esempio, non è possibile incorporare una funzione ricorsiva.

Otterrai le migliori prestazioni dalle impostazioni del tuo progetto per il linguaggio C / C ++ e da come costruisci il tuo codice. A questo punto, è importante comprendere le operazioni Heap vs. Stack, convenzioni di chiamata, allineamento della memoria, ecc.

So che questo non risponde esattamente alla tua domanda, ma menzioni le prestazioni e come ottenere le prestazioni migliori, e queste cose sono fondamentali.

Answer 9

Per unirti al vagone link: conteggio dei bit

Answer 10

Se questo non è un caso di ottimizzazione prematura e hai davvero bisogno di spremere ogni ultimo femtosecondo, probabilmente stai meglio con un array statico a 256 elementi che popoli una volta con il conteggio dei bit di ciascun valore di byte , quindi

  

Stats.FreqOf1 + = bitCountTable [byte]

e al termine del ciclo:

  

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

Answer 11

C'è un intero capitolo sulle diverse tecniche per questo nel libro Beautiful Code . Puoi leggerlo (la maggior parte) su Google books a partire da .

Answer 12

Un modo più veloce per estrarre i bit è usare:

bitmask= data->Data[i];

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

Se vuoi solo contare i bit impostati, un LUT nella cache per sarebbe veloce, ma puoi anche farlo in tempo costante con il metodo di conteggio dei bit interlacciato in il link in questa risposta .