Java最佳實踐–隊列之戰和鏈接的ConcurrentHashMap

在使用Java編程語言時，我們將繼續討論與建議的實踐有關的系列文章，我們將在四個具有相關語義的流行Queue實現類之間進行性能比較。為了使事情變得更現實，我們將在多線程環境下進行測試，以討論和演示如何將ArrayBlockingQueue ， ConcurrentLinkedQueue ， LinkedBlockingQueue和/或LinkedList用于高性能應用程序。

最后但并非最不重要的一點是，我們將提供自己的ConcurrentHashMap實現。從ConcurrentLinkedHashMap實施不同的ConcurrentHashMap ，它維持于所有條目的運行雙向鏈表。此鏈表定義了迭代順序，通常是將鍵插入映射中的順序。從組合的特點ConcurrentLinkedHashMap利益的ConcurrentHashMap和LinkedHashMap的實現業績略低于該的ConcurrentHashMap的，由于增加了維護鏈接列表的額外費用。

所有討論的主題均基于用例，這些用例來自于電信行業的關鍵任務超高性能生產系統的開發。

在閱讀本文的每個部分之前，強烈建議您參考相關的Java API文檔以獲取詳細信息和代碼示例。

所有測試均針對具有以下特征的Sony Vaio進行：

系統：openSUSE 11.1（x86_64）
處理器（CPU）：Intel（R）Core（TM）2 Duo CPU T6670 @ 2.20GHz
處理器速度：1,200.00 MHz
總內存（RAM）：2.8 GB
Java：OpenJDK 1.6.0_0 64位

應用以下測試配置：

并發工作線程數：50
每個工作人員測試重復次數：100
整體測試次數：100

ArrayBlockingQueue與ConcurrentLinkedQueue與LinkedBlockingQueue與LinkedList

Java開發人員必須執行的最常見任務之一是從Collections中存儲和檢索對象。 Java編程語言提供了一些具有重疊和獨特特征的Collection實現類。從Java 1.5開始， Queue實現類已成為在處理之前保存元素的事實上的標準。除了基本的“ 收集”操作外，隊列還提供其他插入，提取和檢查操作。

但是，使用Queue實現類，尤其是在多線程環境中，可能會很棘手。默認情況下，它們中的大多數提供并發訪問，但是可以以阻塞或非阻塞方式來處理并發。 BlockingQueue實現類支持以下操作：在檢索元素時等待隊列變為非空，并在存儲元素時等待隊列中的空間變為可用。

這里將要討論的案例場景是通過ConcurrentLinkedQueue和LinkedList Queue實現類以及ArrayBlockingQueue和LinkedBlockingQueue BlockingQueue實現類的元素來插入，縮回和迭代多個線程。我們將演示如何在多線程環境中正確利用上述集合實現類，并提供相關的性能比較表，以顯示在每個測試用例中哪個性能更好。

為了進行票價比較，我們將假定不允許使用NULL元素，并且在適用的情況下限制每個隊列的大小。因此，我們的測試組的BlockingQueue實現類將被初始化，其最大大小為5000個元素–請記住，我們將使用50個工作線程來執行100次測試重復。此外，由于LinkedList是我們測試組中唯一不默認提供并發訪問的Queue實現類，因此將使用同步塊訪問列表來實現LinkedList的并發性。在這一點上，我們必須明確指出LinkedList Collection實現類的Java文檔建議使用Collections.synchronizedList靜態方法來維護對列表的并發訪問。此方法提供指定Collection實現類的“包裝”同步實例，如下所示：

列表syncList = Collections.synchronizedList（new LinkedList（））;

當您要將特定的實現類用作List而不是Queue時，此方法是合適的。為了能夠使用特定Collection實現類的“隊列”功能，必須按原樣使用它，或將其強制轉換為Queue接口。

測試案例1 –在隊列中添加元素

對于第一個測試用例，我們將有多個線程在每個Queue實現類中添加String元素。為了保持String元素之間的唯一性，我們將如下所示構造它們：

靜態的第一部分，例如“ helloWorld”
工作線程ID，請記住，我們有50個并發運行的工作線程
worker線程測試重復次數，請記住，每個worker線程每次測試執行100次測試重復

對于每個測試運行，每個工作線程將插入100個String元素，如下所示：

對于第一次測試重復
- 工作線程1將插入String元素：“ helloWorld-1-1”
- 工作線程2將插入String元素：“ helloWorld-2-1”
- 工作線程3將插入String元素：“ helloWorld-3-1”
- 等等...
對于第二次測試重復
- 工作線程1將插入String元素：“ helloWorld-1-2”
- 工作線程2將插入String元素：“ helloWorld-2-2”
- 工作線程3將插入String元素：“ helloWorld-3-2”
- 等等...
等等...

在每次測試運行結束時，每個Queue實現類都將填充5000個不同的String元素。為了添加元素，我們將使用BlockingQueue實現類的“ put（）”操作和Queue實現類的“ offer（）”操作，如下所示：

arrayBlockingQueue.put（“ helloWorld-” + id +“-” + count）;
linkedBlockingQueue.put（“ helloWorld-” + id +“-” + count）;
parallelLinkedQueue.offer（“ helloWorld-” + id +“-” + count）;
已同步（linkedList）{
linkedList.offer（“ helloWorld-” + id +“-” + count）;
}

下面我們提供了上述四個Queue實現類之間的性能比較表

橫軸表示測試運行的次數，縱軸表示每次測試運行的每秒平均事務數（TPS）。因此，較高的值更好。如您所見，向其添加元素時，所有Queue實現類的執行幾乎相同。與LinkedList和LinkedBlockingQueue相比， ArrayBlockingQueue和ConcurrentLinkedQueue的性能稍好。后者表現最差，平均得分為625000 TPS。

測試案例2 –從隊列中刪除元素

對于第二個測試用例，我們將有多個線程從每個Queue實現類中刪除String元素。所有隊列實現類都將使用來自先前測試用例的String元素進行預填充。每個線程將從每個Queue實現類中刪除單個元素，直到Queue為空。

為了刪除元素，我們將對BlockingQueue實現類使用“ take（）”操作，對Queue實現類使用“ poll（）”操作，如下所示：

arrayBlockingQueue.take（）;
linkedBlockingQueue.take（）;
concurrentLinkedQueue.poll（）;
已同步（linkedList）{
linkedList.poll（）;
}

下面我們提供了上述四個Queue實現類之間的性能比較表

橫軸表示測試運行的次數，縱軸表示每次測試運行的每秒平均事務數（TPS）。因此，較高的值更好。同樣，從隊列中刪除String元素時，所有Queue實現類的性能幾乎相同。與LinkedList和LinkedBlockingQueue相比， ArrayBlockingQueue和ConcurrentLinkedQueue的性能稍好。后者是最差的性能，平均得分為710000 TPS。

測試案例＃3 –迭代器

對于第三個測試用例，我們將有多個工作線程在每個Queue實現類的元素上進行迭代。每個工作線程將使用Queue的“ iterator（）”操作檢索對Iterator實例的引用，并使用Iterator的“ next（）”操作遍歷所有可用的Queue元素。所有Queue實現類都將使用第一個測試用例的String值預先填充。下面是上述測試用例的性能比較表。

橫軸表示測試運行的次數，縱軸表示每次測試運行的每秒平均事務數（TPS）。因此，較高的值更好。與ConcurrentLinkedQueue和LinkedList實現類相比， ArrayBlockingQueue和LinkedBlockingQueue實現類的性能均較差。 LinkedBlockingQueue平均得分為35 TPS，而ArrayBlockingQueue平均得分為81 TPS。另一方面， LinkedList的性能優于ConcurrentLinkedQueue ，平均導致15000 TPS。

測試案例4 –添加和刪除元素

對于我們的最終測試用例，我們將實現測試用例1和測試用例2場景的組合。換句話說，我們將實現生產者－消費者測試用例。一組輔助線程將向每個Queue實現類插入String元素，而另一組輔助線程將從其中撤回String元素。每一個主題從“插入元素”組將會只有一個元素插入，而每一次的主題從“縮回元素”組是要收回一個元素。因此，我們將從每個Queue實現類中同時插入和撤回5000個唯一的String元素。

要正確模擬上述測試情況下，我們必須啟動所有工作線程是收回之前的元素開始工作者線程是插入的元素。為了使“收回元素”組的工作線程能夠收回單個元素，如果相關隊列為空，它們必須等待并重試。默認情況下， BlockingQueue實現類提供等待功能，而Queue實現類則不提供。因此，為了刪除元素，我們將對BlockingQueue實現類使用“ take（）”操作，對Queue實現類使用“ poll（）”操作，如下所示：

arrayBlockingQueue.take（）;
linkedBlockingQueue.take（）;
while（結果== null）
結果= parallelLinkedQueue.poll（）;
while（結果== null）
已同步（linkedList）{
結果= linkedList.poll（）; }

如您所見，我們實現了最低限度的while循環，以使ConcurrentLinkedQueue和LinkedList使用者能夠在從空Queue撤回時執行重新連接。當然，您可以嘗試并實施更復雜的方法。盡管如此，請記住，上述內容以及任何其他人工實現方法都不是建議的解決方案，應避免使用BlockingQueue “ take（）”操作，如以下性能比較表所示。

下面是上述測試用例的添加部分的性能比較表。

以下是上述測試案例的收回部分的性能比較表。

橫軸表示測試運行的次數，縱軸表示每次測試運行的每秒平均事務數（TPS）。因此，較高的值更好。不出所料， ArrayBlockingQueue和LinkedBlockingQueue的表現均優于LinkedList和ConcurrentLinkedQueue 。 BlockingQueue實現被設計為主要用于生產者-消費者隊列。在這種情況下，特別是當生產者線程和使用者線程的數量相對較高時，它們的阻塞行為使它們具有無與倫比的性能和效率。實際上，根據相關的性能比較，隨著生產者線程和使用者線程數量的增加， Queue實現類和BlockingQueue實現類之間的性能相對增益會有所提高，而后者則有所提高。

從提供的性能結果中可以看出， LinkedBlockingQueue獲得了最佳的組合（添加和刪除元素）性能結果，并且應該是實施生產者（消費者）方案的第一候選人。

ConcurrentLinkedHashMap

我們的ConcurrentLinkedHashMap實現是最初由Doug Lea編碼并在OpenJDK 1.6.0_0上發現的ConcurrentHashMap實現的調整版本。我們提出了ConcurrentMap接口的并發哈希圖和鏈表實現，并具有可預測的迭代順序。此實現與ConcurrentHashMap的不同之處在于，它維護一個遍歷其所有條目的雙向鏈接列表。此鏈表定義了迭代順序，通常是將鍵插入映射的順序（插入順序）。請注意，如果將密鑰重新插入到映射中，則插入順序不會受到影響。

此實現使客戶擺脫了ConcurrentHashMap和Hashtable提供的未指定的，通常混亂的排序，而不會增加與TreeMap相關的成本。無論原始地圖的實現如何，都可以使用它來生成與原始地圖具有相同順序的地圖副本：

void foo（Map m）{
地圖副本=新的ConcurrentLinkedHashMap（m）;
… }

如果模塊在輸入上獲取映射，將其復制并隨后返回結果（其順序由副本的順序確定），則此技術特別有用。（客戶通常喜歡按退貨的順序退貨。）

提供了一個特殊的“ ConcurrentLinkedHashMap（int，float，int，boolean）”構造函數，以創建并發鏈接的哈希映射，該哈希映射的迭代順序是其條目的最后訪問順序，即從最近訪問到最近訪問（訪問-訂購）。這種映射非常適合構建LRU緩存。調用put或get方法將導致對相應條目的訪問（假設調用完成后該條目存在）。 “ putAll（）”方法為指定映射中的每個映射生成一個條目訪問，其順序為指定映射的條目集迭代器提供鍵-值映射。沒有其他方法可以生成條目訪問。特別是，對集合視圖的操作不會影響支持映射的迭代順序。

可以重寫“ removeEldestEntry（Map.Entry）”方法，以強加一個策略，以便在將新映射添加到地圖時自動刪除陳舊的映射。

由于維護鏈接列表會增加開銷，因此性能可能會略低于ComcurrentHashMap，但有一個例外：對ConcurrentLinkedHashMap的集合視圖進行迭代需要的時間與地圖的大小成正比，而無論其容量如何。在ConcurrentHashMap上進行迭代可能會更昂貴，所需的時間與其容量成正比。

您可以從此處下載最新版本的ConcurrentLinkedHashMap源代碼和二進制代碼

您可以從此處，此處和此處下載用于進行性能比較的所有“測試器”類的源代碼。

快樂編碼

賈斯汀

相關文章：