非常快速的方法来检查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;
}
我已经很明显也改变了相应的写入功能。
答
这是我最初如何优化你的代码:
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))))
答
明显的第一个改进是转移加载的值而不是面具:
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知道这一点。
答
我已经测试相比初始源代码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倍)。
而静态内联使用离宏不远。
目前速度有多慢?如何“慢”(但比当前更快)是可以接受的?你可以为此献出多少内存?你能否包含当前实现的反汇编? – Amit
特定行使用总共28s中的大约10s。至少应该可以使它在5秒(或更少)内工作。我可以为此献出相当多的内存(至少10MB)。我将很快发布反汇编。提前致谢 –
用一个静态掩码数组替换'128 >>(bitPos&7)'。 –