STL隊列推送行爲

我遇到了STL隊列推送中的行爲，我不太明白。STL隊列推送行爲

基本上，我有兩個結構

structA{ 
    string a; 
} 

structB{ 
char b[256]; 
} 

structA st1; 
structB st2; 

...assign a 256 characters string to both st1 and st2... 


queue<structA> q1; 
queue<structB> q2; 
for(int i=0 ; i< 10000; i++){ 
    q1.push(st1); 
} 

for(int i=0 ; i< 10000; i++){ 
    q2.push(st2); 
}

我知道的是，使用char結構隊列會在比較字符串結構推動結構使用更長的時間（如5次）。在檢查個別推送時，我意識到char結構推送性能在這裏和那裏有相當多的尖峯（範圍從2X到10X）。這是什麼原因？

謝謝。

來源

2010-10-21 Steveng

與您的其他性能問題一樣，這嚴重缺乏可重複性。顯示您的_exact_代碼，您測量的_exact_方式以及數字。這裏提到的許多性能謎題都可以通過指出測試工具中的錯誤來解決。性能測試非常困難，而且隨機海報首次出現的可能性非常小。在你提供這些信息之前，我正在投票結束這件事。 – sbi 2010-10-21 07:27:07

您的C++實現可能使用了copy-on-write字符串實現，這意味着字符串副本並不真正複製字符串（而是鏈接回副本），並且僅當您複製字符串「for real」寫信給它。再次

++st1.a[0];

然後時間：

爲了測試是否是這種情況下，把這個循環裏面，q1.push(st1)行之後。

顯然，字符數組沒有寫時複製行爲，並且每次要求將其複製時都會將其「複製」。

來源

2010-10-21 03:37:45

字符數組大於一個空字符串 - 尖峯可能與重新分配必需的重新分配必要的，因爲向量增長爲它使用的大量內存。

如果字符串不爲空，那麼copy-on-write踢任何地方，所以你正在交易一些鎖定時間/引用計數器遞增等與內存使用：更快的是系統依賴。

來源

2010-10-21 03:38:17

從我讀過的內容來看，COW在單線程場景中速度更快，沒有真正的鎖定爭用等等。這當然與OP的時序利用一致 - 我看不到任何線程在問題中被提及。 – 2010-10-21 03:44:07

感謝您的回覆。其實我有另一個線程訪問隊列。那麼在這種情況下，它是如何工作的？ – Steveng 2010-10-21 03:49:14

不客氣。爲了安全地將'push（）'與其他讀者線程一起使用，所有這些線程都需要使用鎖（互斥鎖或讀/寫鎖）。獲得該鎖定不會阻止std :: string在處理複製/引用計數器時執行可能不必要的鎖定，因爲std :: string中的代碼不知道代碼中的鎖以及是否有更多的線程不要使用鎖，但可能嘗試從其中一個字符串讀取數據。不知道這是否回答你的問題...？無論如何，安全地使用鎖編碼然後分析是最好的方法。 – 2010-10-21 04:52:47

的原因很可能是由於：

1）的存儲器中的動態分配以保持每個字符串
2）內的字符數據有可能，但不太可能，所述雙端隊列頁緩衝器的大小調整該支持隊列。

來源

2010-10-21 03:39:18

每次將st1或st2推入隊列時，實際上是在推送它的副本（而不是參考或指針）。成本差異在於複製數據。在structB你必須每次複製完整的256字節。在structA中，您只複製字符串實例，該實例最有可能具有寫時複製語義，因此直到其中一個被修改，它們將共享相同的對基礎字符串數據的引用。

來源

2010-10-21 03:40:58

複製寫入？ http://stackoverflow.com/questions/1116040/memory-efficient-c-strings-interning-ropes-copy-on-write-etc/1116059#1116059顯然，gcc仍然實現它，儘管它通常被認爲是不推薦的「 optmization」。 – 2010-10-21 07:20:24

問一個普遍的問題，得到一個普遍的答案。 – 2010-10-21 10:16:47

std :: queue是另一個容器（實現front，back，push_back和pop_front）的適配器，除非您指定要調整哪個容器，否則將使用std :: deque。 Deque在後臺執行一些塊分配魔術，它應該提供類似於矢量的大小調整，但性能更好，因爲它管理多個非連續塊，並且不必在每次調整大小時都複製所有內容。無論如何，這是一個猜測，但我會說這就是原因。

由於爲所有這些數組騰出空間，字節數組結構正在更頻繁地看到命中，我打賭一個更長的字符串結構也會產生尖峯，它現在只是更小，因爲字符串可能會保持對下載字符存儲，直到有東西改變它。

讓您有機會熟悉您選擇的分析器並找出肯定！消防valgrind（--callgrind）或您的平臺支持的任何分析器，並準確查看哪些調用正在使用時間和地點。

來源

2010-10-21 03:51:16 Olson

牛？非常不可能。 – sbi 2010-10-21 07:23:52

STL隊列推送行爲

回答

相關問題