java LinkedList 与 ConcurrentLinkedQueue

LinkedList Vs ConcurrentLinkedQueue

提问by Sachin

Currently in a multithreaded environment, we are using a LinkedList to hold data. Sometimes in the logs we get NoSuchElementException while it is polling the linkedlist. Please help in understanding the performance impact if we move from the linkedlist to ConcurrentLinkedQueue implementation.

目前在多线程环境中，我们使用 LinkedList 来保存数据。有时在日志中我们会在轮询链表时得到 NoSuchElementException。如果我们从链表转移到 ConcurrentLinkedQueue 实现，请帮助理解性能影响。

Thanks, Sachin

谢谢，萨钦

回答by Fabian Barney

When you get a NoSuchElementExceptionthen this maybe because of not synchronizing properly. For example: You're checking with it.hasNext()if an element is in the list and afterwards trying to fetch it with it.next(). This may fail when the element has been removed in between and that can also happen when you use synchronized versions of Collection API.

当你得到一个NoSuchElementException那么这可能是因为没有正确同步。例如：您正在检查it.hasNext()元素是否在列表中，然后尝试使用it.next(). 当元素在中间被删除时这可能会失败，当您使用 Collection API 的同步版本时也可能发生这种情况。

So your problem cannot really be solved with moving to ConcurrentLinkedQueue. You may not getting an exception but you've to be prepared that nullis returned even when you checked before that it is not empty. (This is still the same error but implementation differs.) This is true as long as there is no proper synchronization in YOUR code having checks for emptiness and element retrieving in the SAME synchronized scope.

所以你的问题不能通过移动到ConcurrentLinkedQueue. 您可能不会收到异常，但您必须做好准备，null即使您之前检查过它不是空的，也会返回。（这仍然是相同的错误，但实现有所不同。）只要您的代码中没有适当的同步检查空性和在相同同步范围内检索元素，这就是正确的。

There is a good chance that you trade NoSuchElementExceptionfor having new NullPointerExceptionafterwards.

你很有可能NoSuchElementException在NullPointerException之后换新的。

This may not be an answer directly addressing your question about performance, but having NoSuchElementExceptionin LinkedList as a reason to move to ConcurrentLinkedQueuesounds a bit strange.

这可能不是直接解决您关于性能的问题的答案，但NoSuchElementException在 LinkedList 中作为转移到的理由ConcurrentLinkedQueue听起来有点奇怪。

Edit

编辑

Some pseudo-code for broken implementations:

一些用于损坏实现的伪代码：

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

Some pseudo-code for proper sync:

一些用于正确同步的伪代码：

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

Some code for "broken" sync (does not work as intended). This maybe the result of directly switching from LinkedList to CLQ in the hope of getting rid of synchronization on your own.

一些用于“损坏”同步的代码（无法按预期工作）。这可能是直接从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!
}

Some proper code:

一些正确的代码：

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

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

or

或者

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

回答by Péter T?r?k

ConcurrentLinkedQueue[is] an unbounded, thread-safe, FIFO-ordered queue. It uses a linked structure, similar to those we saw in Section 13.2.2 as the basis for skip lists, and in Section 13.1.1 for hash table overflow chaining. We noticed there that one of the main attractions of linked structures is that the insertion and removal operations implemented by pointer rearrangements perform in constant time. This makes them especially useful as queue implementations, where these operations are always required on cells at the ends of the structure, that is, cells that do not need to be located using the slow sequential search of linked structures.

ConcurrentLinkedQueueuses a CAS-based wait-free algorithm that is, one that guarantees that any thread can always complete its current operation, regardless of the state of other threads accessing the queue. It executes queue insertion and removal operations in constant time, but requires linear time to execute size. This is because the algorithm, which relies on co-operation between threads for insertion and removal, does not keep track of the queue size and has to iterate over the queue to calculate it when it is required.

ConcurrentLinkedQueue[是] 一个无界、线程安全、FIFO 排序的队列。它使用链接结构，类似于我们在第 13.2.2 节中看到的作为跳过列表的基础，以及在第 13.1.1 节中看到的哈希表溢出链接的结构。我们在那里注意到链接结构的主要吸引力之一是通过指针重排实现的插入和移除操作在恒定时间内执行。这使得它们作为队列实现特别有用，这些操作总是需要在结构末端的单元格上进行，即不需要使用链接结构的缓慢顺序搜索来定位的单元格。

ConcurrentLinkedQueue使用基于 CAS 的无等待算法，即保证任何线程始终可以完成其当前操作，而不管其他线程访问队列的状态如何。它在恒定时间内执行队列插入和移除操作，但需要线性时间来执行size。这是因为该算法依赖于线程之间的协作来进行插入和删除，它不会跟踪队列大小，并且必须在需要时遍历队列来计算它。

From Java Generics and Collections, ch. 14.2.

来自Java 泛型和集合，ch。14.2.

Note that ConcurrentLinkedQueuedoes not implement the Listinterface, so it suffices as a replacement for LinkedListonly if the latter was used purely as a queue. In this case, ConcurrentLinkedQueueis obviously a better choice. There should be no big performance issue unless its size is frequently queried. But as a disclaimer, you can only be sure about performance if you measure it within your own concrete environment and program.

请注意，ConcurrentLinkedQueue它没有实现List接口，因此LinkedList仅当后者纯粹用作队列时，它才足以替代。在这种情况下，ConcurrentLinkedQueue显然是更好的选择。除非经常查询其大小，否则应该没有大的性能问题。但作为免责声明，只有在您自己的具体环境和程序中衡量性能，您才能确定性能。