非常快速的方法来检查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; 
}

我已经很明显也改变了相应的写入功能。

来源

2016-10-22 Pieter Verschaffelt

目前速度有多慢？如何“慢”（但比当前更快）是可以接受的？你可以为此献出多少内存？你能否包含当前实现的反汇编？ – Amit

特定行使用总共28s中的大约10s。至少应该可以使它在5秒（或更少）内工作。我可以为此献出相当多的内存（至少10MB）。我将很快发布反汇编。提前致谢 –

用一个静态掩码数组替换'128 >>（bitPos＆7）'。 –

这是我最初如何优化你的代码：

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-22 17:49:13 selbie

你使用'％'遇到任何性能问题吗？ – Mike

没关系。函数调用的开销远远大于进行低效位调整操作的成本。但这并不意味着我们无法将两种解决方案结合在一起。 – selbie

或者通过在静态内联函数前添加内联来利用内联？ –

明显的第一个改进是转移加载的值而不是面具：

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-22 18:35:56 EOF

我已经测试相比初始源代码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倍）。

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

来源

2016-10-22 18:47:08

非常快速的方法来检查C中的设置位

回答

相关问题