std :: pair <int, int> vs兩個int的結構

在一個ACM示例中，我必須爲動態編程構建一個大表。我必須在每個單元中存儲兩個整數，所以我決定去找std::pair<int, int>。然而，分配一個巨大的人陣了1.5秒：std :: pair <int, int> vs兩個int的結構

std::pair<int, int> table[1001][1001];

之後，我改變了這個代碼

struct Cell { 
    int first; 
    int second; 
} 

Cell table[1001][1001];

，並分配了0秒。

什麼解釋了這種巨大的時間差異？

來源

2009-10-22 Etan

我相信你的意思是ACM ** ICPC **。 – 2009-10-22 12:52:44

您是否已啓用優化來測試此功能？ – jalf 2009-10-24 08:45:03

如果向'Cell'添加無參數構造函數，性能如何？ – outis 2009-10-24 08:46:22

std::pair<int, int>::pair()構造函數初始化與域的默認值（零中的int情況下），你的struct Cell沒有（因爲你只能有一個自動生成的默認構造函數，什麼也不做）。

初始化需要寫入每個字段，這需要大量相對耗時的內存訪問。用struct Cell什麼都不做，反而更快一點。

來源

2009-10-22 12:35:16 sharptooth

是否需要1.5秒將大約8 MB設置爲零？ – Etan 2009-10-22 12:37:40

不要忘記緩存未命中。 – sharptooth 2009-10-22 12:38:39

不，問題是對構造函數的函數調用。如果你的數組是全局的，無論如何它都被初始化爲零。編譯器可能不會優化構造函數調用。 – 2009-10-22 12:38:48

我的猜測是std :: pair被創建的方式。在調用一個構造函數1001x1001次的時候，比剛剛分配一個內存範圍的時候有更多的開銷。

來源

2009-10-22 12:45:08 Ashalynd

-1

這真是一個很好的例子，應該寫一個C++並仔細使用STL。有什麼想法嗎？

我的項目正在研究一個C++代碼級基準測試工具，我們將在其中編寫大量代碼樣本以找出什麼是「好」代碼，什麼是「壞」編碼習慣。請參閱http://effodevel.googlecode.com瞭解更多關於C9B.M.規劃。如果你遇到過很多這樣的情況，請加入該項目來幫助我們。

來源

2009-10-22 12:47:27 Test

這不是問題的答案 – 2009-10-22 17:44:09

有什麼想法嗎？是的，你的項目似乎納入了一個普遍的想法，即優化是關於低級優化*（和大O）的。我認爲這個問題比這個問題要大得多，也就是*馳騁的一般性*，你可能會考慮更廣泛的範圍。 http://stackoverflow.com/questions/926266/performance-optimization-strategies-of-last-resort/927773#927773 – 2009-10-24 15:20:31

沒有計劃做一個更大的目前。 su。一步一步地進步如代碼級別，算法級別和體系結構級別等。我們現在正在理解語言和編譯器。感謝您的評論 – Test 2009-10-25 05:30:07

到目前爲止的答案並沒有解釋問題的全部重要性。

正如銳利指出的那樣，這對解決方案將這些值初始化爲零。正如Lemurik指出的那樣，這對解決方案不僅僅是初始化一個連續的內存塊，而是調用表中每個元素的pair構造函數。但是，即使這也不佔用1.5秒的時間。其他事情正在發生。

這裏是我的邏輯：

假設你是一個古老的機器上，說爲1.33GHz運行，然後加入1.5秒2E9個時鐘週期。你有2e6對構造，所以每對構造函數都花費1000個週期。 調用只將兩個整數設置爲零的構造函數不需要1000個週期。我無法看到緩存未命中如何會花費那麼長時間。如果數量少於100個週期，我會相信它。

我認爲看看所有這些CPU週期還有哪些地方會很有趣。我用我能找到的最古老的C++編譯器來查看是否可以達到所需的浪費水平。該編譯器是VC++ v6。在調試模式下，它做了一些我不明白的事情。它有一個很大的循環，爲表中的每個項目調用pair構造函數 - 足夠公平。該構造函數將這兩個值設置爲零 - 夠公平的。但在這之前，它將68字節區域中的所有字節設置爲0xcc。該區域就在大桌子開始之前。然後用0x28F61200覆蓋該區域的最後一個元素。對構造函數的每次調用重複此操作。據推測，這是某種由編譯器保留的書籍，因此它知道在運行時檢查指針錯誤時哪些區域被初始化。我很想知道這是什麼。

無論如何，這將解釋額外時間的去向。很明顯，另一個編譯器可能不會這麼糟糕。當然，優化的發佈版本不會。

來源

2009-10-23 23:49:09

這不是VC++ V6的錯。在調試模式下，所有VC編譯器都會將堆棧上分配的所有字節初始化爲一個陷阱值（默認爲0xCC），並將所有分配的堆內存初始化爲0xCD。目的有兩點：因爲任何對未初始化的變量進行操作的代碼會大聲失敗，並讓您在內存調試器中看到未初始化的堆棧。您看到的最後一個值是用於檢測堆棧溢出（「.com *咯咯」*）的「堆棧金字塔值」。 – 2014-03-31 15:25:41

這些都是很好的猜測，但衆所周知，猜測是不可靠的。

我會說在1.5秒內隨機pause it，但你必須非常快。如果將每個維度增加了大約3倍，則可能需要10秒鐘以上，因此暫停會更容易。或者，您可以在調試器下獲取它，在對構造函數代碼中分解它，然後單步查看它在做什麼。

無論哪種方式，你都會得到一個確切的答案，而不僅僅是猜測。

來源

2009-10-24 15:07:34

std :: pair <int, int> vs兩個int的結構

回答

相關問題