我在我的代码中使用了某种具有 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/

10-11 23:22
查看更多