非常快速的方法來檢查C中的設置位

我在我的代碼中使用某種類型的BitStream，它具有read_bit()功能。這個函數被非常頻繁地調用（單個流中超過10億次）。這是結構比特流的樣子：非常快速的方法來檢查C中的設置位

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

而且read_bit() - 函數的定義如下：

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

現在，我發現通過試錯，該行unsigned char mask = 128 >> (bitPos & 7);很慢。有什麼方法可以加快檢查的速度？我已經嘗試過使用索引8種不同可能掩碼的數組，但這不是更快（我認爲是由於內存訪問）。

編輯：我在過去一週嘗試了很多答案，並執行了很多基準測試，但沒有太多的性能改進。我最終設法通過顛倒比特流中的比特順序來獲得10秒的改進。因此，而不是使用掩膜128 >> (bitPos & 7)，我使用的功能：

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

我已經很明顯也改變了相應的寫入功能。

來源

2016-10-22 Pieter Verschaffelt

目前速度有多慢？如何「慢」（但比當前更快）是可以接受的？你可以爲此獻出多少內存？你能否包含當前實現的反彙編？ – Amit

特定行使用總共28s中的大約10s。至少應該可以使它在5秒（或更少）內工作。我可以爲此獻出相當多的內存（至少10MB）。我將很快發佈反彙編。提前致謝 –

用一個靜態掩碼數組替換'128 >>（bitPos＆7）'。 –

這是我最初如何優化你的代碼：

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

但是函數調用的開銷本身可能比它裏面的一些調整代碼更多的指令。所以，如果你真的想進一步優化它，讓我們的內聯的優勢，只是把它轉換成一個宏：

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

來源

2016-10-22 17:49:13 selbie

你使用'％'遇到任何性能問題嗎？ – Mike

沒關係。函數調用的開銷遠遠大於進行低效位調整操作的成本。但這並不意味着我們無法將兩種解決方案結合在一起。 – selbie

或者通過在靜態內聯函數前添加內聯來利用內聯？ –

明顯的第一個改進是轉移加載的值而不是面具：

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

這消除了對有條件的需求（沒有if或!或?:）。

如果你可以修改struct，我會用較大的個股建議訪問不是字節：

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

在某些處理器（特別是普通的x86），移位量的面具是一個NOP，因爲處理器的本地移位指令只考慮移位量的低位。至少gcc知道這一點。

來源

2016-10-22 18:35:56 EOF

我已經測試相比初始源代碼optimzed宏：

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)

通過掩模在陣列更換掩模計算不提高性能。功能和宏之間的主要差距（在我的電腦上通過80.000.000個電話快6倍）。

而靜態內聯使用離宏不遠。

來源

2016-10-22 18:47:08

非常快速的方法來檢查C中的設置位

回答

相關問題