c - 在 C 中检查设置位的非常快速的方法

Question

我在我的代码中使用了某种具有 read_bit() 函数的 BitStream。这个函数被调用得非常频繁(在单个流中超过十亿次)。这就是结构 BitStream 的样子:

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

我显然也更改了相应的写入功能。

Answer 1

第一个明显的改进是移动加载的值而不是掩码:

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，因为处理器的 native 移位指令只考虑移位量的低位无论如何。至少 gcc 知道这一点。