谷歌:: dense_hash_map vs boost :: unordered_map性能問題

我最近一直在努力提高軟件的性能，它花費60％的時間在hashmap中搜索（用valgrind分析器確認）。谷歌:: dense_hash_map vs boost :: unordered_map性能問題

當前實施方案使用boost::unordered_map<long long, FrequencyKey>。我想將它與google::dense_hash_map<long long, FrequencyKey>進行比較。我在我的代碼

boost::unordered_map<long long, FrequencyKey> result;

改變一行

地圖

google::dense_hash_map<long long, FrequencyKey> result; 
result.set_empty_key(-1);

接口被稱爲在兩個地方。大循環之前result.clear()。在循環result[key]內。

With boost::unordered_map<long long, FrequencyKey>我的軟件性能是118請求/ s。隨着上面所列的變化，我得到0.5 req/s。

我明顯做錯了事，但在通過docs和github code後我無法弄清楚自己。

我正在用gcc/g ++ 4.4.7編譯CentOS 6.5上的代碼。

來源

2016-01-05 Maciej Donajski

檢查散列圖的性能時，第一步是檢查發生的衝突。使用'std :: unordered_map'和類似的接口，您可以迭代桶的列表並計算項的數量，每當桶包含N> 1項時，就會有（N-1）個碰撞使您放慢速度。除此之外...你的問題不幸的是缺少代碼：產生一個[MCVE]（http://stackoverflow.com/help/mcve）或遭受無用的（對你）的答案：x –

-3

我不認爲你做錯了什麼。 dense_hash_map針對內存不足而進行了優化。

我懷疑你的散列函數真的很慢，或者這個數據對散列圖來說並不是很好。

如果您在hash_map中有很少的值（如< 128），請嘗試使用矢量並進行線性搜索。它往往有時足夠快。

如果您有自定義哈希函數，請嘗試爲其編寫基準。如果它在二進制文件中被內聯，Valgring可能會跳過它。

此外，如果您可以分配您的條目連續ID您可以跳過地圖，只是使用一個向量來存儲數據。並不總是可能，但總是比hash_map更快。

最後，result [key]應該插入帶有默認值的密鑰。該值的構造函數可能是問題的根源，或者是副本（如果有的話）。再次，這可能被內聯爲二進制的優化，所以你不能保證在Valgrind中看到它。如果您不希望發生插入操作，可能會使地圖膨脹得足以產生性能問題。

來源

2016-01-05 16:24:48 Sorin

感謝您的輸入@Sorin，但我恐怕你的評論在我的情況下都不適用。我平均存儲500k條目並且不超過150萬條。關鍵是很長的哈希fn'std :: tr1 :: hash '。根據文檔，'dense_hash_map'爲速度優化，'sparse_hash_map'爲內存優化。構造函數對於映射的值並不重要，我嘗試過沒有更好性能的對象池。最後，由operator []插入默認值（當key不存在於map中）時的行爲是有意使用的，'boost :: unordered_map'完全相同。 –

@MaciejDonajski對不起，沒有任何建議工作。請再次檢查文檔，我們其中一個錯了。如果hash_map是稀疏的，它會使用更多的內存（它很稀疏，因爲使用的條目遠在兩者之間）。我可能是錯的，但可能值得雙重檢查。 – Sorin

我有同樣的直覺，但github repo自述文件中的確切引用是'sparse_hash_map每個散列映射條目具有大約2位的內存開銷，dense_hash_map具有2-3個內存開銷的因子：如果您的散列表數據需要X個字節， dense_hash_map將使用3X-4X內存total.'和'sparse_hash_map使用非常小的空間開銷，每個條目1-2位。 dense_hash_map非常快，特別是查找.'。但我會嘗試它:)。 –

谷歌:: dense_hash_map vs boost :: unordered_map性能問題

回答

相關問題