为什么 ConcurrentLinkedQueue.size() 的复杂度不能保持不变？

Question

JavadocConcurrentLinkedQueue明确指出 size() 方法的复杂度是 O(n)。我觉得这很令人惊讶。我会遵循库存LinkedList.size()方法，在柜台中累积规模。鉴于操作的异步性质ConcurrentLinkedQueue，计数器自然必须是AtomicInteger。这样做是不是因为它会违反非阻塞保证？AtomicInteger如果是这样，计数器会带来多少开销？

Answer 1

没有什么问题AtomicInteger：在非阻塞环境中使用它是一件好事。但是，如果您AtomicInteger在队列中添加一个计数器，您将引入一个位置，pool()并且该位置都offer(E)必须保持更新。这将增加 CAS 操作的数量以及失败的CAS 操作的数量。

Javadoc 告诉我们，拥有更少的 CAS 可能是一个很好的优化。

头部和尾部都允许滞后。事实上，每次都不能更新它们是一项重大优化（更少的 CAS）。
...
由于 head 和 tail 是同时独立更新的，所以 tail 有可能落后于 head （为什么不呢）？

^{JDK 8 >java.util.concurrent.ConcurrentLinkedQueue}

请注意，返回的结果size()可能不准确，并且正如他们所说，“在并发应用程序中通常不是很有用”。