std ::設置快而慢，發生了什麼？

我想到了std :: set的一個奇怪的行爲。std ::設置快而慢，發生了什麼？

下面是代碼：

#include <cstdio> 
#include <windows.h> 
#include <stdlib.h> 

#include <vector> 
#include <set> 

using namespace std; 

int main(int argc, char *argv[]) 
{ 
    set<int> b[100]; 

    for (int o=0; o<10; o++) 
    { 
     int tt = GetTickCount(); 

     for (int i=0; i<5000000; i++) 
     { 
      b[o].insert(i); 
     } 

     tt = GetTickCount() - tt; 

     b[o].clear(); 

     printf("%d\n", tt); 
    } 

    return 0; 
}

我在Windows XP上運行。

以下是有趣的部分：這第一次打印時間大約是3500毫秒，而所有下一個超過9000毫秒！這是爲什麼發生？

哦，這隻發生在發佈版本（-O2優化）。

它不會發生在Linux上（在改變代碼編譯之後）。

還有一件事：當我在使用英特爾VTune進行性能分析時運行它時，總是需要大約3000毫秒，所以它應該是這樣。

UPDATE：下面是一些新的代碼：

#include <cstdio> 
#include <windows.h> 
#include <stdlib.h> 

int main(int argc, char *argv[]) 
{ 
const int count = 10000000; 
int **a = new int*[count]; 

for (int o=0; o<10; o++) 
{ 
    int ttt = GetTickCount(); 

    for (int i=0; i<count; i++) 
    { 
     a[i] = new int; 

     *a[i] = i; 
    } 

    int ttt2 = GetTickCount(); 

    for (int i=0; i<count; i++) 
    { 
     int r1 = rand() * 10000 + rand(); 
     int r2 = rand() * 10000 + rand(); 
     r1 = r1%count; 
     r2 = r2%count; 

     int *e = a[r1]; 
     a[r1] = a[r2]; 
     a[r2] = e; 
    } 

    int ttt3 = GetTickCount(); 

    for (int i=0; i<count; i++) 
    { 
     delete a[i]; 
    } 

    int ttt4 = GetTickCount(); 

    printf("%d %d\n", ttt2-ttt, ttt4-ttt3); 
} 

return 0; 
}

這是同樣的問題。會發生什麼是我分配許多小對象，然後以隨機順序刪除它們 - 因此它類似於它在std :: set中的樣子。所以這是Windows內存管理問題。它不能真正處理很多小的分配和刪除。

來源

2011-11-16 tweety3d

這可能與您的標準庫/平臺的一些實現細節有關。你可以嘗試在分析器中運行它，並檢查時間花在哪裏。可能會有很多事情發生，從第一次和連續傳遞（您釋放內存）的分配方案的差異到其他任何事情。另請注意，您應該使用-O3來提高性能。 –

也許它與系統線程調度有關。你的線程不是唯一需要處理器時間的線程。您可以使用'GetThreadTimes'來查看您的線程實際消耗了多少處理器時間 – valdo

您最好的辦法可能是查看使用'-O2'生成的彙編代碼，看看有沒有什麼東西可以解釋這種行爲。 – NPE

我無法解釋爲什麼會發生這種情況，但我可以提出解決方案。當我在調試器下運行發行版本時（我的電腦已經能夠在我的電腦上重現這一點）（F5）。當我從命令行或Ctrl-F5運行構建時，我不會得到這種行爲。

這與您在調試器下啓動時默認打開的調試堆有關。詳細描述如下here。爲了防止發生這種情況

從命令行或Ctrl-F5（調試 - >無需調試開始）運行。
轉到項目 - >屬性 - >調試 - >環境並添加_NO_DEBUG_HEAP=1。

如果我不得不猜測，我會說它與Windows/VS運行時內存分配跟蹤的實現有關。可能有些內部列表會填滿並重新分配，或沿着這些線路進行其他操作。

來源

2011-11-16 15:40:11 detunized

這個_NO_DEBUG_HEAP選項對我來說是新的。很好的答案。 – Dialecticus

我總是在沒有調試器的情況下運行它，所以這不是問題。我用VS2010測試過它，它工作正常（沒有異常），但在VS2008上工作不好。但是，我提供的第二個代碼在VS2008和VS2010上工作不好。注意：VS2010實現STL庫（特別是集合）比VS2008要好得多，它在複雜性方面不符合官方的STL規範（例如：插入元素向量到集合中，他們忘記了使用insert（end（），element）（可能是O（1），它們使用insert（element）（總是O（logN）） – tweety3d

我認爲std::set是作爲二叉查找樹實現的。由於每當你實質上爲這種類型的數據結構創建敵對（最壞情況）場景時，你就會增加1（幾乎每個插入都需要重新平衡樹）。

此外，它是5000萬插入，所以有些時間是預期的，但我不認爲它會是5毫秒。

此外，我會做你的「清晰」後，你打印的時間，因爲我沒有看到你將基準插入和刪除項目的基準。

來源

2011-11-17 16:35:55 Alex

實際上，清除整個集合比添加所有內容慢3到10倍。因爲Windows內存管理器讓它很慢 – tweety3d

@ tweety3d任何想法爲什麼清楚它是如此緩慢？我可以想象刪除將是線性時間，無論Windows抽象底層數據結構嗎？ – Alex

這可能是因爲內存管理器被優化爲了進行快速分配，所以重新整理其指針/迭代列表/加入釋放空間的整個處理過程都是在釋放器中完成的。 – tweety3d

std ::設置快而慢，發生了什麼？

回答

相關問題