Sehr schnelle Möglichkeit, gesetztes Bit in C

Question

zu überprüfen Ich verwende eine Art BitStream in meinem Code, der eine read_bit()-Funktion hat. Diese Funktion wird sehr oft (mehr als eine Milliarde Mal in einem einzelnen Stream) aufgerufen. Dies ist, was die Struktur BitStream wie folgt aussieht:

typedef struct BitStream { 
    unsigned char* data; 
    unsigned int size; 
    unsigned int currentByte; 
    unsigned char buffer; 
    unsigned char bitsInBuffer; 
} BitStream; 

Und die read_bit() -function ist wie folgt definiert:

unsigned char bitstream_read_bit(BitStream* stream, unsigned long long bitPos) { 
    unsigned int byte = bitPos/8; 
    unsigned char byteVal = stream->data[byte]; 
    unsigned char mask = 128 >> (bitPos & 7); 
    if (mask & byteVal) { 
     return 1; 
    } else { 
     return 0; 
    } 
} 

Nun fand ich durch Versuch und Irrtum, dass die Linie unsigned char mask = 128 >> (bitPos & 7); ist sehr langsam. Gibt es eine Möglichkeit, die Prüfung etwas zu beschleunigen? Ich habe bereits versucht, ein Array zu verwenden, das die 8 verschiedenen möglichen Masken indiziert, aber das ist nicht schneller (ich denke aufgrund des Speicherzugriffs).

EDIT: Ich habe viele der Antworten in der vergangenen Woche ausprobiert und viele Benchmarks durchgeführt, aber es gab nicht viel Leistungsverbesserung. Ich habe es schließlich geschafft, eine Verbesserung von 10 Sekunden zu erreichen, indem ich die Reihenfolge der Bits im Bitstrom umkehrte. Anstatt also die Maske mit 128 >> (bitPos & 7), benutzte ich die Funktion:

unsigned char bitstream_read_bit_2(BitStream* stream, const unsigned long long bitPos) { 
    unsigned int byte = (unsigned int) (bitPos/8); 
    unsigned char byteVal = stream->data[byte]; 
    unsigned char mod = bitPos & 7; 
    return (byteVal & (1 << mod)) >> mod; 
} 

Ich habe natürlich auch die entsprechende Schreibfunktion verändert.

Answer 1

Hier ist, wie ich zunächst den Code optimiert:

unsigned char bitstream_read_bit(BitStream* stream, unsigned long long bitPos) 
{ 
    return !!(stream->data[(bitPos/8)] & (128 >> (bitPos % 8))); 
} 

Aber der Funktionsaufruf Overhead selbst ist wahrscheinlich mehr Befehle als die Bit-Tweaking-Code in seinem Inneren. Also, wenn Sie es wirklich noch weiter optimieren möchten, lassen Sie uns die Vorteile von inlining nehmen und es nur zu einem Makro konvertieren:

#define bitstream_read_bit(stream, bitPos) (!!((stream)->data[((bitPos)/8)] & (128 >> ((bitPos) % 8)))) 

Answer 2

Die offensichtliche erste Verbesserung ist den geladenen Wert zu verschieben anstatt der Maske:

Dies beseitigt die Notwendigkeit einer bedingten (No if oder ! oder ?:).

Wenn Sie die struct ändern können, würde ich empfehlen, durch größere Einheiten als Bytes Zugriff:

#include <stddef.h> 
#include <limits.h> 
#include <stdbool.h> 

typedef struct WBitStream 
{ 
    size_t *data; 
    size_t size; 
} WBitStream; 

bool Wbitstream_read_bit(WBitStream* stream, size_t bitPos) 
{ 
    size_t location = bitPos/(sizeof(size_t)*CHAR_BIT); 
    size_t locval = stream->data[location]; 
    size_t maskval = locval >> (bitPos & (sizeof(size_t)*CHAR_BIT-1)); 
    return maskval & 1; 
} 

Bei einigen Prozessoren (vor allem der gemeinsame x86), die Maske der Shift-Menge ist ein NOP, da die native Schichtanweisung des Prozessors nur die niedrigen Bits des Verschiebungsbetrags auf jeden Fall berücksichtigt. Zumindest weiß gcc davon.

Answer 3

Ich habe getestet Makro optimierter im Vergleich zu Ihrer ursprünglichen Quellcode:

static unsigned char tMask[8] = { 128, 64, 32, 16, 8, 4, 2, 1 }; 

#define BITSTREAM_READ_BIT1(stream, bitPos) (((128 >> (bitPos & 7)) & stream->data[bitPos >> 3])!=0) 
#define BITSTREAM_READ_BIT2(stream, bitPos) (((tMask[(bitPos & 7)]) & stream->data[bitPos >> 3])!=0) 

durch mask Berechnung Ersetzen in Array-Leistung nicht erhöht. Die Hauptlücke ist zwischen Funktion und Makro (6 mal schneller auf meinem Computer mit 80.000.000 Anrufe).

Und die statische Inline-Verwendung ist nicht weit vom Makro entfernt.