按位循环遍历大数据块的最快方法是什么
-
03-07-2019 - |
题
我正在按字节运行二进制数据的内存块。
目前我正在做这样的事情:
for (i = 0; i < data->Count; i++)
{
byte = &data->Data[i];
((*byte & Masks[0]) == Masks[0]) ? Stats.FreqOf1++; // syntax incorrect but you get the point.
((*byte & Masks[1]) == Masks[1]) ? Stats.FreqOf1++;
((*byte & Masks[2]) == Masks[2]) ? Stats.FreqOf1++;
((*byte & Masks[3]) == Masks[3]) ? Stats.FreqOf1++;
((*byte & Masks[4]) == Masks[4]) ? Stats.FreqOf1++;
((*byte & Masks[5]) == Masks[5]) ? Stats.FreqOf1++;
((*byte & Masks[6]) == Masks[6]) ? Stats.FreqOf1++;
((*byte & Masks[7]) == Masks[7]) ? Stats.FreqOf1++;
}
面具在哪里:
for (i = 0; i < 8; i++)
{
Masks[i] = 1 << i;
}
(不知怎的,我没能在循环或内联函数中做到那么快,所以我把它写出来了。)
有人对如何改进第一个循环有任何建议吗?我对细化细节缺乏经验。
这似乎是一件愚蠢的事情。但我正在实现压缩算法。我只想将位访问部分放在右边。
谢谢!
附:这是 Visual Studio 2008 编译器中的。因此,如果这些建议适用于该编译器,那就太好了。
聚苯醚:我刚刚意识到,我不需要增加两个计数。一个就足够了。然后计算最后总位数的差值。但这仅适用于计数。我真正想要快速完成的是位提取。
编辑:提出的查找表想法很好。我意识到我在标题中提出了错误的问题。因为最终我想做的不是计算位数,而是尽可能快地访问每一位。
另一个编辑:是否可以将数据中的指针前进一位?
另一个编辑:感谢您迄今为止的所有回答。
我想在接下来的步骤中实现的是一个不复杂的二进制算术编码器,它不分析上下文。所以我现在只对单个位感兴趣。最终它将成为上下文自适应 BAC,但我将其留到以后再说。
处理 4 个字节而不是 1 个字节可能是一种选择。但是超过 32 位的循环成本也很高,不是吗?
解决方案
我真的不明白你要做什么。但是如果你只是想访问位图的位,你可以使用这些(未经测试的!!!)函数:
#include <stddef.h>
_Bool isbitset(unsigned char * bitmap, size_t idx)
{
return bitmap[idx / 8] & (1 << (idx % 8)) ? 1 : 0;
}
void setbit(unsigned char * bitmap, size_t idx)
{
bitmap[idx / 8] |= (1 << (idx % 8));
}
void unsetbit(unsigned char * bitmap, size_t idx)
{
bitmap[idx / 8] &= ~(1 << (idx % 8));
}
void togglebit(unsigned char * bitmap, size_t idx)
{
bitmap[idx / 8] ^= (1 << (idx % 8));
}
编辑:好的,我想我明白你想做什么:快速迭代一系列比特。因此,我们不想使用上面的随机访问函数,而是一次读取整个数据字。
您可以使用任何您喜欢的无符号整数类型,但您应该选择一个可能与您的体系结构的字大小相对应的整数类型。我将使用 stdint.h
中的 uint_fast32_t
:
uint_fast32_t * data = __data_source__;
for(; __condition__; ++data)
{
uint_fast32_t mask = 1;
uint_fast32_t current = *data;
for(; mask; mask <<= 1)
{
if(current & mask)
{
// bit is set
}
else
{
// bit is not set
}
}
}
从内部循环中,您可以使用
设置位*data |= mask;
用
取消设置位*data &= ~mask;
并用
切换位*data ^= mask;
警告:代码可能会在big-endian架构上出现意外行为!
其他提示
最快的方法可能是构建一个字节值查找表与该字节中设置的位数。至少那是我在Google采访时的答案。
请参阅以下链接,了解十几个相关内容: Bit Twiddling Hacks
使用将每个字节值(256)映射到其中1的数字的表。 (0的#只是(8 - 1的1))。然后迭代字节并对每个字节执行单个查找,而不是多次查找和比较。例如:
int onesCount = 0;
for (i = 0; i < data->Count; i++)
{
byte = &data->Data[i];
onesCount += NumOnes[byte];
}
Stats.FreqOf1 += onesCount;
Stats.FreqOf0 += (data->Count * 8) - onesCount;
您可以使用预先计算的查找表,即:
static int bitcount_lookup[256] = { ..... } ; /* or make it a global and compute the values in code */
...
for( ... )
byte = ...
Stats.FreqOf1 += bitcount_lookup[byte];
这是一个如何计算32位整数的1位的方法(基于Java的 Integer.bitCount(i)
方法):
unsigned bitCount(unsigned i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i + (i >> 4)) & 0x0f0f0f0f;
i = i + (i >> 8);
i = i + (i >> 16);
return i & 0x3f;
}
因此,您可以将数据转换为int并以4个字节的步长向前移动。
这是我仅用一个 32 位值编写的一个简单的值,但您可以看到将其适应任何位数并不困难......
int ones = 0;
int x = 0xdeadbeef;
for(int y = 0;y < 32;y++)
{
if((x & 0x1) == 0x1) ones++;
x = (x >> 1);
}
printf("%x contains %d ones and %d zeros.\n", x, ones, 32-ones);
但请注意,它会修改过程中的值。如果您对需要保留的数据执行此操作,那么您需要先复制它。
在 __asm 中执行此操作可能是一种更好、更快的方法,但很难说编译器可以优化到什么程度......
对于您考虑的每一种解决方案,每一种都会有缺点。查找表或位移位器(如我的)都有缺点。
拉里
ttobiass - 请记住,您的内联函数在您正在谈论的应用程序中很重要,但是您需要记住一些事情。你 能 要发挥内联代码的性能,只需记住几件事即可。
- 调试模式下的内联不存在。(除非你强迫)
- 编译器将根据需要内联函数。通常,如果你告诉它内联一个函数,它可能根本不做。即使你使用__forceinline。有关内联的更多信息,请查看 MSDN。
- 甚至只有某些函数可以内联。例如,您不能内联递归函数。
您将从 C/C++ 语言的项目设置以及构建代码的方式中获得最佳性能。此时,了解堆与堆非常重要。堆栈操作、调用约定、内存对齐等。
我知道这并不能完全回答你的问题,但你提到了性能,以及如何获得最佳性能,这些都是关键。
加入旅行车: 计算位数
如果这不是过早优化的情况,并且你真的需要挤出每一个飞秒,那么你最好使用一个256元素的静态数组,用每个字节值的位数填充一次,那么
Stats.FreqOf1 + = bitCountTable [byte]
当循环完成时:
Stats.FreqOf0 =((data-&gt; Count * 8) - Stats.FreqOf1)
提取比特的更快方法是使用:
bitmask= data->Data[i];
while (bitmask)
{
bit_set_as_power_of_two= bitmask & -bitmask;
bitmask&= bitmask - 1;
}
如果您只想计算位数,则每个缓存中的LUT会很快,但您也可以使用这个答案中的链接一>