c++ - 为什么 vector 和 map 搜索比静态比较慢得多

Question

我正在解析大约 1MB 大小的文件，读取前 300KB 并搜索一些特定的签名。我的策略是，对于每个字节，查看该字节是否在映射/vector/我知道可能位于签名开头的任何字节中，如果是，则寻找完整的签名——对于这个例子，假设那些领先的字节为 x37、x50 和 x52。共处理90个文件(实际9个文件10次)，以下代码执行时间为2.122秒:

        byte * bp = &buffer[1];
        const byte * endp = buffer + bytesRead - 30; // a little buffer for optimization - no signature is that long
        //multimap<byte, vector<FileSignature> >::iterator lb, ub;
        map<byte, vector<FileSignature> >::iterator findItr;
        vector<FileSignature>::iterator intItr;
        while (++bp != endp)
        {
            if (*bp == 0x50 || *bp == 0x52 || *bp == 0x37)  // Comparison line
            {
                findItr = mapSigs.find(*bp);
                for (intItr = findItr->second.begin(); intItr != findItr->second.begin(); intItr++)
                {
                    bool bMatch = true;
                    for (UINT i = 1; i < intItr->mSignature.size(); ++i)
                    {
                        if (intItr->mSignature[i] != bp[i])
                        {
                            bMatch = false;
                            break;
                        }
                    }

                    if (bMatch)
                    {
                        CloseHandle(fileHandle);
                        return true; 
                    }
                }
            }
        }

但是，我的初始实现仅用了 84 秒就完成了。唯一的区别与上面标有“//比较线”的行有关:

findItr = mapSigs.find(*bp);
if (findItr != mapSigs.end())
...

使用包含 3 个值的 vector 的非常相似的实现也会导致处理速度极慢(190 秒):

if (find(vecFirstChars.begin(), vecFirstChars.end(), *bp) != vecFirstChars.end())
{
    findItr = mapSigs.find(*bp);
    ...

但是直接访问 vector 元素的实现执行得相当好(8.1 秒)。不如静态比较好，但仍然比其他选项好得多:

if (vecFirstChars[0] == *bp || vecFirstChars[1] == *bp || vecFirstChars[2] == *bp)
{
    findItr = mapSigs.find(*bp);
    ...

目前最快的实现(受下面的组件 10 启发)如下，耗时约 2.0 秒:

bool validSigs[256] = {0};
validSigs[0x37] = true;
validSigs[0x50] = true;
validSigs[0x52] = true;

while (++bp != endp)
{
    if (validSigs[*bp])
    {
    ...

将其扩展为使用 2 个 validSigs 来查看第二个字符是否有效，并将总运行时间减少到 0.4 秒。

我觉得其他实现应该表现得更好。特别是 map ，它应该随着更多签名前缀的添加而扩展，并且搜索是 O(log(n)) vs O(n)。我错过了什么？我唯一的猜测是，通过静态比较和(现存较少的) vector 索引，我得到了用于比较的值缓存在寄存器或其他位置，这使得它比读取快得多从内存里。如果这是真的，我是否能够明确地告诉编译器将经常使用特定值？对于下面的代码，是否还有其他不明显的优化可供我利用？

我正在使用 Visual Studio 2008 进行编译。

Answer 1

这很简单，可以归结为执行的指令数。 vector 、映射或查找表将完全驻留在 CPU 一级数据缓存中，因此内存访问不会占用时间。至于查找表，只要大多数字节与签名前缀不匹配，分支预测器就会停止流量控制占用时间。 (但其他结构确实会产生流量控制开销。)

非常简单，依次与 vector 中的每个值进行比较需要 3 次比较。 map 是 O(log N)，但由于导航链接数据结构，系数(被大 O 符号忽略)很大。查找表的复杂度为 O(1)，系数很小，因为访问该结构可以通过一条机器指令完成，然后剩下的就是与零进行一次比较。

分析性能的最佳方法是使用分析器工具，例如 valgrind/kcachegrind。