快速並行添加到字典，當鍵不會碰撞

我有一種情況，其中字典創建，鍵值對添加，並且之後點字典僅用於讀取值。快速並行添加到字典，當鍵不會碰撞

我試圖實現在初始化階段添加到字典的最快捷方式。

ConcurrentDictionary的TryAdd方法非常慢（還有GetOrAdd） - 在我的6個核心CPU（12個線程）上，CPU使用率通常保持在25％，表明只有3個線程被使用。

與使用ConcurrentDictionary和Parallel.For相比，將所有密鑰（大約2500萬）順序添加到Dictionary實際上更快。

我該如何提高速度？很容易分開鍵值對，使密鑰時添加到字典中從來沒有發生衝突，但只是用下面的代碼產生了一些問題：

Dictionary<long,string> d = new Dictionary<long,string>(); 
d[key] = value;

看來，這在多線程環境中使用時，因爲Dictionary有時會進行一些內部更改（調整大小？）失敗。

將這項工作呢？

capacity = 250000000 //basically big enough to store all data 
Dictionary<long,string> d = new Dictionary<long,string>(capacity); 
d[key] = value;

我更喜歡使用Dictionary over ConcurrentDictionary，因爲讀取速度也快得多（速度對於我的應用程序來說也是非常重要的）。

2014-06-26 Michal

當你說他們不會碰撞時，你的意思是說他們從來沒有相同的價值，或者他們實際上不會碰撞？字典是散列表，並且可以與兩個不同名稱的鍵發生衝突。 –

你玩過'ConcurrentDictionary'的'concurrencyLevel'構造函數嗎？ –

@MikePrecup我的意思是，我可以分開所有要添加的密鑰，以便每個線程都有唯一的密鑰來添加，並且每個密鑰都有唯一的哈希碼（類似於將1到100的數字添加到字典中 - 沒有重複項或哈希碼碰撞） – Michal

如果你知道字典的最大尺寸，那麼你可以通過預分配來提高速度。但是，這並不會阻止可能會混淆字典的併發添加。內部列表被更新，並且兩個線程很可能最終將密鑰存儲在列表中的相同索引處。

你試過這個明顯的事嗎？那就是：

lock (dictionaryLock) 
{ 
    dict[key] = value; 
}

如果這個鎖沒有被爭用，它可能需要20納秒。如果它是的爭用，那麼延遲時間稍長一點，但是你正在做一個很短的操作。這是否會更快將取決於撥打Add的呼叫之間進行了哪些處理。

2014-06-26 00:49:58

吉姆的建議是偉大的。但是，這可能是你沒有任何重大努力就能夠最快的。這也是一個明顯的方法，我相信你應該自己考慮。假設你對效率和併發水平仍然不滿意，這裏有一個來自兩層頁表的想法：

1，想出一個標準來把你的大字典分成一堆小字典。

2，將第二級字典存儲在靜態容器中，以免運行時自組織可能會破壞併發訪問的前提。

3，想出一個快速映射算法，直接跳轉到任何二級字典。

作爲一個沒有任何基準的非常具體的例子：在你的情況下，你可以考慮一個由250個元素組成的數組，每個元素都是一個字典的引用，它反過來保存100k個字符串。你需要想出一個算法，將長數據映射到數組的索引。一個簡單的可以長250％。再次，這可能需要一些基準來達到最有效的解決方案。

這個建議的理念是：

1）一種字典具有最佳容量，超過該基礎散列函數可能會看到更多的碰撞。

2）儘可能允許併發 - 在提案中，你需要250個鎖，每個二級字典一個鎖。

3）最重要的是，通過一些基準測試和實現的努力，您可以將想法擴展到多級字典 - 就像多級頁表一樣。

2015-01-30 14:19:09 h9uest

回答