2

我需要遍历一组字节，搜索一个 4 字节的值（所有 4 个字节都相同）。数据的长度是可变的，这些字节可以在数据中的任何位置；我正在寻找第一个实例。我试图找到最快的实现，因为这个逻辑在我的代码的关键部分运行。

这只会在 Windows 下的 x86 和 x64 上运行。

typedef unsigned char Byte;
typedef Byte* BytePtr;
typedef unsigned int UInt32;
typedef UInt32* UInt32Ptr;

const Byte MARKER_BYTE = 0xAA;
const UInt32 MARKER = 0xAAAAAAAA;

UInt32 nDataLength = ...;
BytePtr pData = ...;
BytePtr pEnd = pData + nDataLength - sizeof ( UInt32 );

// Option 1 -------------------------------------------
while ( pData < pEnd )
{
    if ( *( (UInt32Ptr) pData ) == MARKER )
    {
        ... // Do something here
        break;
    }

    pData++;
}

// Option 2 -------------------------------------------
while ( pData < pEnd )
{
    if ( ( *pData == MARKER_BYTE ) && ( *( (UInt32Ptr) pData ) == MARKER ) )
    {
        ... // Do something here
        break;
    }

    pData++;
}

我认为Option 2更快，但我不确定我的推理是否正确。

Option 1首先从内存中读取 4 个字节，根据 4 字节常量检查它，如果没有找到，它会进入下一个字节并重新开始。从内存中准备好的下一个 4 字节将与已经读取的 3 个字节重叠，因此需要再次获取相同的字节。我的 4 字节标记之前的大多数字节将被读取两次。

Option 2一次只读取 1 个字节，如果该单个字节匹配，则从该地址读取完整的 4 字节值。这样，所有字节只被读取一次，并且只有 4 个匹配的字节被读取两次。

我的推理是正确的还是我忽略了什么？

在有人提出之前，是的，我确实需要执行这种优化。:)

编辑：请注意，此代码只能在基于 Intel / AMD 的计算机上运行。我不在乎其他架构是否无法运行它，只要普通的 x86/x64 计算机（台式机/服务器）运行它而不会出现问题或性能损失。

编辑 2：编译器是 VC++ 2008，如果有帮助的话。

4

4 回答 4

6

您也可以尝试 Boyer-Moore 方法。

pData = start + 3;
int i;

while(pData < pEnd) {
    for(i = 0; i < 4; ++i) {
        if (*(pData-i) != MARKER_BYTE) {
            pData += 4-i;
            break;
        }
    }
    if (i == 4) {
        /* do something here with (pData-3) */
        break;
    }
}

如果幸运的话，它只测试每四个字节，直到找到匹配项。

对于这样的短模式，任何人都猜测这是否比测试每个字节更快或更慢。

于 2012-05-15T20:06:03.943 回答
3

选项 1 将执行大量未对齐的内存访问。我不确定这是否适用于硬件。至少在某些硬件上，Windows 会拦截产生的异常，并且非常缓慢地模拟内存访问。性能的彻底灾难。

无论如何，你已经有了代码。你为什么不测量它并 100% 确定呢？

于 2012-05-15T19:40:25.000 回答
1

选项 2。如果 256 次中的 255 次第一个不是您想要的，则没有理由获取 4 个字节。

为了皮特的缘故，展开循环。

编辑：展开。长度为nDataLength。你可以这样说：

pEnd1 = pData + (nDataLength & -8);
while (pData < pEnd1){
  if (pData[0] == theByteIWant){ ... }
  if (pData[1] == theByteIWant){ ... }
  ...
  if (pData[7] == theByteIWant){ ... }
  pData += 8;
}
while(pData < pEnd){
  if (pData[0] == theByteIWant){ ... }
  pData++;
}

看看有什么作用？你不会花一半的时间问一个(pData < pEnd)答案几乎总是相同的问题。

于 2012-05-15T20:59:51.063 回答
1

这种方法并不完整，但基本思想是一次搜索八 (8) 个字节以查找 0xAA 模式。如果找到，则可以对 MARKER 模式执行二次搜索。

阶段 1：逐字节进行测试，直到您的数组是 8 字节对齐的。

阶段 2：#define HAS_NUL_BYTE(x) ((x) - 0x0101010101010101ull) & ~x & 0x8080808080808080ull)

uint64_t  value;
for (...) {
    value = *(uint64_t *) array[i] ^ 0xAAAAAAAAAAAAAAAAull;
    if (HAS_NUL_BYTE (value) != 0) {
        perform secondary search for the MARKER pattern
    }
    i += 8;
}

这种方法应该（希望）具有以下优点。

  1. 当 0xAA 不在窗口中时，每 8 个字节进行 1 次比较，而不是 8 次。
  2. 更少的未对齐内存访问。

缺点包括...

  1. 它更复杂
  2. 如果数组包含大量 0xAA 字节（但不包含 MARKER），则主搜索中的误报会影响性能。

另一件事——既然你提到这只会在 Windows 下的 x86-64 上运行，你是否考虑过在汇编中编写它？如果是这样，PCMPEQB 指令可能会被证明是有用的。

希望这可以帮助。

于 2012-05-16T01:28:27.017 回答