在C语言中快速检查位集的方法

Question

我在我的代码中使用了一种名为BitStream的数据流，其中包含一个read_bit()函数。该函数被频繁调用（单个数据流中超过10亿次）。以下是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;
}

我显然也已经改变了相应的写入函数。

- user4424299

---

目前速度有多慢？可以接受多大程度的“慢”（但比目前快）？您可以为此分配多少内存？您能包括当前实现的反汇编吗？ - Amit

返回 ((掩码 & 字节值)!=0) 可以节省时间。也许 bitPos / 8 => bitPos >> 3。你正在使用哪些优化选项？ - Jean-François Fabre

完整的场景是什么？你经常花费这28秒钟的时间吗，为什么将它减少到23秒很重要？如果您要调用函数1e+9次，那么您可能会按顺序执行此操作-您应该利用这一点。 - Amit

你尝试过将其编写为宏而不是可调用函数吗？函数调用可能比你的小掩码计算更昂贵。还要注意@Amit的第一个评论... - Jean-Baptiste Yunès

你可以尝试在一次调用中读取多个位吗？例如，将一个字节解包成一个8字节向量。我认为这应该可以通过单个乘法实现。优化这段代码将非常困难，因为它的操作非常简单廉价。因此，也许可以从更高层面进行优化。 - usr

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、! 或 ?:）。

如果您可以修改结构体，建议按较大的单位而不是字节访问：

#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知道这一点。

- EOF

Answer 2

我已经测试了与您初始源代码相比进行优化的宏：

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倍）。

而静态内联使用与宏并没有太大差别。

- J. Piquard

Answer 3

这是我最初优化您的代码的方法：

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

- selbie

---

没关系。函数调用开销远大于具有低效位操作的成本。但这并不意味着我们不能将两种解决方案结合起来。 - selbie

或者通过在函数前缀加上 static inline 来利用内联的优势？ - Jonathan Leffler

@Mike 上次我检查时，gcc 能够使用二的幂中间值来优化 / 和 % 运算。它们应该不会比等效的位运算慢。 - Petr Skocik