c - 这两个循环中哪个更快？

Question

我需要遍历一组字节，搜索一个 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++;
}

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

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

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

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

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

编辑:请注意，此代码只能在基于 Intel/AMD 的计算机上运行。我不在乎其他架构是否无法运行它，只要正常的 x86/x64 计算机(台式机/服务器)运行它没有问题或性能损失。

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

Answer 1

您也可以尝试 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;
    }
}

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

对于像这样的短模式，任何人都可以猜测这比测试每个字节快还是慢。