3

我正在解析大约 1MB 大小的文件，读取前 300KB 并搜索一些特定的签名。我的策略是，对于每个字节，查看该字节是否在映射/向量/我知道可能位于签名开头的任何字节中，如果是，则查找完整签名-对于本示例，假设那些领先字节为 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 个值的向量的非常相似的实现也会导致处理速度极慢（190 秒）：

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

但是直接访问向量元素的实现执行得相当好（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 来查看第 2 个字符是否有效，从而使总运行时间降低到 0.4 秒。

我觉得其他实现应该表现更好。尤其是地图，它应该随着更多签名前缀的添加而缩放，并且搜索是 O(log(n)) 与 O(n)。我错过了什么？我唯一的猜测是，通过静态比较和（在较少的情况下）矢量索引，我将用于比较的值缓存在寄存器或其他位置，这使得它比读取快得多从记忆里。如果这是真的，我是否能够明确告诉编译器将经常使用特定值？对于以下不明显的代码，我是否可以利用其他优化？

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

4

2 回答 2

1

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

很简单，依次与向量中的每个值进行比较需要 3 次比较。该映射为 O(log N)，但由于导航链接的数据结构，系数（被大 O 表示法忽略）很大。查找表是 O(1)，系数很小，因为对结构的访问可以通过一条机器指令完成，然后剩下的就是与零的比较。

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

于 2012-11-08T00:42:15.980 回答
0

“与常量比较”将 3 个内存地址与 3 个常量进行比较。如果编译器愿意，这种情况将非常容易进行展开或进行位优化等操作。书面 ASM 将在这里拥有的唯一分支将是高度可预测的。

对于文字 3 元素向量查找，取消引用向量值的地址会产生额外的成本。

对于向量循环，编译器此时不知道向量有多大。所以它必须编写一个通用循环。这个循环中有一个分支，一个分支向一个方向走 2 次，然后另一个方向。如果计算机使用启发式“分支按照上次的方式进行”，则会导致大量分支预测失败。

要验证该理论，请尝试使分支更可预测——一次搜索每个元素最多 100 个不同的输入字节，然后搜索下一个。这将使幼稚的分支预测在大约 98% 的时间内工作，而不是代码中的 33%。即，为签名 0 扫描 100 个（或其他）字符，然后为签名 1 扫描 100 个（或其他）字符，直到您用完签名。然后继续下一个 100 个字符的块以扫描签名。我选择 100 是因为我试图避免分支预测失败，而且我认为百分之几的分支预测失败并不是那么糟糕。:)

至于map解决方案，wellmap具有很高的恒定开销，因此它的速度很慢是可以预见的。a 的主要用途map是处理大型 n 查找，以及它们非常容易编写代码的事实。

于 2012-11-08T03:09:58.933 回答