按位循环遍历大数据块的最快方法是什么

StackOverflow https://stackoverflow.com/questions/418266

题

我正在按字节运行二进制数据的内存块。

目前我正在做这样的事情：

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）

在美丽代码一书中，有一整章介绍了不同的技巧。您可以在Google图书上阅读（大部分）从这里开始

提取比特的更快方法是使用：

bitmask= data->Data[i];

while (bitmask)
{
    bit_set_as_power_of_two= bitmask & -bitmask;
    bitmask&= bitmask - 1;
}

如果您只想计算位数，则每个缓存中的LUT会很快，但您也可以使用这个答案中的链接

不隶属于 StackOverflow
scroll top