这两个循环哪一个更快？

我需要遍历一组字节，search一个4字节的值（全部4个字节是相同的）。数据的长度是可变的，这些字节可以在数据中的任何地方; 我正在寻找第一个例子。我试图find最快的实现，因为这个逻辑运行在我的代码的关键部分。

这只能在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字节的常量进行检查，如果没有find，则进入下一个字节并重新开始。从内存中下一个4字节准备好将重叠已经读取3个字节，所以需要再次获取相同的字节。我的4字节标记之前的大多数字节将被读取两次。

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

我的推理是正确的还是我忽略了一些东西？

有人提出来之前，是的，我确实需要进行这种优化。 🙂

编辑：请注意，这个代码将只运行在基于Intel / AMD的计算机上。我不关心其他体系结构是否会运行失败，只要正常的x86 / x64计算机（台式机/服务器）运行这个没有问题或性能处罚。

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

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

如果你幸运的话，那就是每四个字节测试一次，直到你找到一个匹配。

无论是比测试每个单字节更快还是更慢，这都是人们对短模式的猜测。

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

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

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

对皮特来说，展开循环。

编辑：展开。长度是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) ，答案几乎总是一样的。

这种方法并不完整，但基本思想是一次搜索八（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; }

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

每8个字节1个比较而不是8个0xAA不在窗口中。
更少的错误对齐的内存访问。

缺点包括…

这更复杂
如果阵列包含大量0xAA字节（但不包括MARKER），则主搜索中的误报会影响性能。

另一件事 – 因为你提到这只能在Windows下的x86-64上运行，你是否考虑过在汇编中写这个？如果是这样，PCMPEQB指令可能会有用。

希望这可以帮助。