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

Question

JavadocConcurrentLinkedQueue明确指出 size() 方法的复杂度为 O(n)。我觉得这很令人惊讶。我会通过在柜台累积大小来遵循库存LinkedList.size()方法。鉴于ConcurrentLinkedQueue's 操作的异步性质，计数器自然必须是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()可能不准确，并且正如他们所说，“在并发应用程序中通常不是很有用”。