这两个循环中的哪一个更快？

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++;
}

我认为Option 2速度更快,但我不确定我的推理是否正确.

Option 1首先从内存中读取4个字节,然后根据4字节常量进行检查,如果没有找到,则进入下一个字节并重新开始.来自内存的下一个4字节就绪将重叠已经读取的3个字节,因此需要再次获取相同的字节.我的4字节标记之前的大多数字节将被读取两次.

Option 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;
    }
}

如果你很幸运,那么在你找到匹配项之前,它只测试每四个字节.

无论是比测试每个字节更快还是更慢,都是因为这样对短模式的猜测.