我需要遍历一组字节,search一个4字节的值(全部4个字节是相同的)。 数据的长度是可变的,这些字节可以在数据中的任何地方; 我正在寻找第一个例子。 我试图find最快的实现,因为这个逻辑运行在我的代码的关键部分。
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; }
这种方法应该(希望)有以下优点。
缺点包括…
另一件事 – 因为你提到这只能在Windows下的x86-64上运行,你是否考虑过在汇编中写这个? 如果是这样,PCMPEQB指令可能会有用。
希望这可以帮助。