LinkedList與併發鏈接隊列

Question

當前處於多線程環境中，我們使用LinkedList來保存數據。有時在日誌中，我們在輪詢鏈接列表時收到NoSuchElementException。如果我們從鏈表移動到ConcurrentLinkedQueue實現，請幫助理解性能影響。

感謝， 薩欽

Answer 1

當你得到一個NoSuchElementException那麼這可能是因爲沒有正確同步。 例如：您正在使用it.hasNext()檢查一個元素是否在列表中，然後嘗試使用it.next()來獲取它。當元素已被刪除時，這可能會失敗，並且在使用Collection API的同步版本時也會發生。

所以你的問題不能真正解決移動到ConcurrentLinkedQueue。你可能沒有得到例外，但是你必須做好準備，即使你在檢查之前它已經被返回，但它不是空的。 （這仍然是相同的錯誤，但實現不同。）只要您的代碼中沒有正確的同步檢查空同步和元素在SAME同步範圍內檢索，就是如此。

您很有可能在交易NoSuchElementException之後有新的NullPointerException。

這可能不是直接解決您關於性能問題的答案，但在LinkedList中有NoSuchElementException作爲轉移到ConcurrentLinkedQueue的原因聽起來有點奇怪。

編輯

斷開的實現方式中的一些僞代碼：

//list is a LinkedList 
if(!list.isEmpty()) { 
    ... list.getFirst() 
} 

適當同步的一些僞代碼：

//list is a LinkedList 
synchronized(list) { 
    if(!list.isEmpty()) { 
     ... list.getFirst() 
    } 
} 

爲 「斷」 同步的某些代碼（不不按預期工作）。 這可能是直接從LinkedList切換到CLQ的結果，希望自己擺脫同步。

//queue is instance of CLQ 
if(!queue.isEmpty()) { // Does not really make sense, because ... 
    ... queue.poll() //May return null! Good chance for NPE here! 
} 

一些適當的代碼：

//queue is instance of CLQ 
element = queue.poll(); 

if(element != null) { 
    ... 
} 

或

//queue is instance of CLQ 
synchronized(queue) { 
    if(!queue.isEmpty()) { 
     ... queue.poll() //is not null 
    } 
} 

Answer 2

ConcurrentLinkedQueue [是]一個無界的，線程安全的，FIFO排序隊列。它使用鏈接結構，類似於我們在13.2.2節中看到的鏈接結構作爲跳過列表的基礎，在13.1.1節中用於散列表溢出鏈接。我們在那裏注意到，鏈接結構的主要吸引力之一是通過指針重排實現的插入和移除操作在不變的時間內執行。這使得它們作爲隊列實現特別有用，其中這些操作總是在結構末端的單元上需要，也就是說，不需要使用鏈接結構的緩慢順序搜索來定位單元。

ConcurrentLinkedQueue使用基於CAS的無等待算法，即保證任何線程始終可以完成其當前操作，而不管其他線程訪問隊列的狀態如何。它在一段時間內執行隊列插入和刪除操作，但需要線性時間來執行size。這是因爲依賴於線程之間的插入和移除協作的算法沒有跟蹤隊列大小，並且必須在需要時迭代隊列以計算它。

從Java Generics and Collections，ch。 14.2。

請注意，ConcurrentLinkedQueue沒有實現List接口，所以它只能作爲LinkedList的替代，只要後者僅用作隊列。在這種情況下，ConcurrentLinkedQueue顯然是更好的選擇。除非經常查詢其大小，否則不應該有大的性能問題。但作爲免責聲明，如果您在自己的具體環境和計劃中進行衡量，則只能確定其性能。