我在我的代码中使用了某种具有 read_bit()
功能的 BitStream。此函数被非常频繁地调用(在单个流中调用次数超过 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;
}
我显然也改变了相应的写功能。
最佳答案
明显的第一个改进是移动加载的值而不是掩码:
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 知道这一点。
关于c - 在 C 中检查设置位的非常快的方法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/40194469/