3

我在我的代码中使用了某种具有 -function 的read_bit()BitStream。这个函数被非常频繁地调用（在单个流中超过 10 亿次）。这是 struct BitStream 的样子：

typedef struct BitStream {
    unsigned char* data;
    unsigned int size;
    unsigned int currentByte;
    unsigned char buffer;
    unsigned char bitsInBuffer;
} BitStream;

并且read_bit()-function 定义如下：

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 秒的改进。因此，我没有使用 mask 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;
}

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

4

3 回答 3

2

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

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

于 2016-10-22T18:35:56.930 回答
1

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

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)

用数组中的掩码替换掩码计算不会提高性能。主要差距在函数和宏之间（在我的电脑上快 6 倍，调用次数为 80.000.000）。

而且静态内联使用离宏也不远。

于 2016-10-22T18:47:08.647 回答
0

以下是我最初优化您的代码的方式：

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))))
于 2016-10-22T17:49:13.220 回答