LinkedList与ConcurrentLinkedQueue

Question

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

谢谢,萨钦

Answer 1

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

所以转移到你的问题并不能真正解决ConcurrentLinkedQueue.你可能没有得到例外,但你必须做好准备,null即使你在它之前检查它是非空的,也会返回.(这仍然是相同的错误,但实现方式不同.)只要在您的代码中没有正确的同步,并且在SAME同步范围内检查空白和元素检索,就是这样.

你很有可能NoSuchElementException在NullPointerException之后进行交易.

这可能不是直接解决你的性能问题的答案,而是将NoSuchElementExceptionLinkedList作为移动到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显然是一个更好的选择.除非经常查询其大小,否则不应存在大的性能问题.但作为免责声明,如果您在自己的具体环境和程序中进行测量,则只能确定性能.