爲什麼矢量和地圖搜索比靜態比較慢得多

我正在解析大小約爲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來查看第二個字符是否有效以及總運行時間降至0.4秒。

我覺得其他的實現應該更好。尤其是地圖應該按照更多的簽名前綴進行縮放，並且搜索是O（log（n））和O（n）。我錯過了什麼？我唯一的黑暗中猜測是，通過靜態比較和向量索引（對於較小的現有值），我將得到的值用於緩存在寄存器或其他位置的比較值，這使得它比閱讀速度快得多從記憶裏。如果這是真的，我能夠明確告訴編譯器經常使用特定值嗎？有沒有其他優化方法可以利用下面的代碼不明顯？

我與Visual Studio 2008編譯

來源

2012-11-08 Rollie

您的預先過濾只有三個值肯定會加快速度，因爲它實際上會拋出其他可能的253個已知未命中條件。在地圖上只有三個值，我真的不明白爲什麼你有一個。對三個值（你已經在做）進行內聯測試並打上適當的後續列表也會更快。如果這全部是關於搜索子字符串（字節等），我建議你閱讀有關[Knuth-Morris-Pratt]（http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm）等算法 – WhozCraig

你考慮使用一個稀疏矢量作爲你的簽名值？聽起來像這可能是在這些情況下體面優化，特別是如果您的簽名的範圍是一個字節。 –

我還沒有讀過關於Knuth-Morris-Pratt的文章 - 有趣的閱讀，但不太適用。假設字節的均勻分佈，我只會看到每256個比較中的第3個（或7個）第一個字符的匹配。當我得到一場比賽時，每個後續角色的匹配機率更低（1/256）。我不認爲這裏會有很多好處。 @ Component10我不知道一個稀疏矢量會有幫助，但是一個連續的數組會加速它 - 更新問題與另一個案例。 – Rollie

這是很簡單的歸結到執行的指令數。矢量，映射或查找表將完全駐留在CPU 1級數據高速緩存中，因此內存訪問不佔用時間。至於查找表，只要大多數字節不符合簽名前綴，分支預測器將停止流量控制佔用時間。（但其他結構的確會產生流量控制開銷。）

所以很簡單，與向量中的每個值進行比較需要3次比較。該映射是O（log N），但由於導航鏈接的數據結構，該係數（由大O符號忽略）很大。查找表是一個小系數的O（1），因爲訪問結構可以通過一條機器指令完成，然後剩下的只是一個比較零的比較。

分析性能的最佳方式是使用諸如valgrind/kcachegrind之類的分析器工具。

來源

2012-11-08 00:42:15 Potatoswatter

不錯的建議，但我不認爲這解釋了爲什麼find（vec.begin，vec.end，* bp）實現需要比靜態比較方法長90倍 - 它可能有一些額外的指令，但我可以'不要想象它會跳躍3 - > 270！與地圖一樣 - 我預計會有一點額外的開銷，長2-3倍，但從2s - > 84s似乎表明其他事情正在影響執行時間。 – Rollie

@Rollie地圖和矢量'find'每次都會導致至少一個分支預測失誤。我沒有及時瞭解最新的CPU，但錯誤預測增加了大約20個週期。比1-2個單週期指令慢2至3倍將是4-9個週期。很少有事情是那麼快，當然不是'std :: map'。 – Potatoswatter

「比較常量」將3個內存地址與3個常量進行比較。如果編譯器感覺像這樣，這種情況將非常容易做到像展開或做位優化那樣的事情。書面ASM將在這裏擁有的唯一分支將具有高度的可預測性。

對於文字3元素矢量查找，需要額外的引用矢量值地址的引用。

對於矢量循環，編譯器不知道這個矢量有多大。所以它必須編寫一個通用循環。這個循環在其中有一個分支，一個分支單向2次，然後另一個分支。如果計算機使用啓發式「分支機構按照他們上次所做的方式」，則會導致大量分支預測失敗。

要驗證理論，請嘗試使分支更具可預測性 - 一次搜索每個元素最多100個不同的輸入字節，然後搜索下一個。這會使得樸素的分支預測工作在98％的時間內完成，而不是代碼中的33％。即，掃描100（或其他）字符作爲簽名0，然後掃描100（或其他）字符作爲簽名1，直到用完簽名。然後繼續下一個由100個字符組成的塊來掃描簽名。我選擇了100個，因爲我試圖避免分支預測失敗，並且我認爲幾個百分比的分支預測失敗並不是那麼糟糕。 :)

至於map解決方案，井map s有一個很高的恆定開銷，所以它很慢是相當可預測的。 map的主要用途是處理大量的n查找，並且它們很容易編碼。

來源

2012-11-08 03:09:58 Yakk

爲什麼矢量和地圖搜索比靜態比較慢得多

回答

相關問題