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

Question

Javadoc for ConcurrentLinkedQueue明确指出 size() 方法的复杂度为 O(n)。我觉得这令人惊讶。我会通过在计数器中累积大小来遵循常用的 LinkedList.size() 方法。考虑到 ConcurrentLinkedQueue 操作的异步性质，自然计数器必须是 AtomicInteger。不这样做是因为它违反了非阻塞保证吗？如果是这样，我应该期望 AtomicInteger 计数器引入多少开销？

Answer 1

AtomicInteger 没有错:在非阻塞环境中使用它是一件好事。但是，如果您向队列中添加一个 AtomicInteger 计数器，您将引入一个 pool() 和 offer(E) 都必须的地方保持更新。这会增加 CAS 操作的数量以及失败 CAS 操作的数量。

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

Both head and tail are permitted to lag. In fact, failing to update them every time one could is a significant optimization (fewer CASes).
...
Since head and tail are updated concurrently and independently, it is possible for tail to lag behind head (why not)?

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

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