这两个循环哪一个更快?

我需要遍历一组字节,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; } 

这种方法应该(希望)有以下优点。

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

缺点包括…

  1. 这更复杂
  2. 如果阵列包含大量0xAA字节(但不包括MARKER),则主搜索中的误报会影响性能。

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

希望这可以帮助。