为什么 ConcurrentLinkedQueue.size() 的复杂度不能保持不变？
Why can't complexity of ConcurrentLinkedQueue.size() be constant?
Javadoc for ConcurrentLinkedQueue明确指出size()方法的复杂度为O(n)。我觉得这令人惊讶。我会通过在计数器中累积大小来遵循股票 LinkedList.size() 方法。鉴于 ConcurrentLinkedQueue 操作的异步性质，自然计数器必须是 AtomicInteger。不这样做是因为它会 运行 违反非阻塞保证吗？如果是这样，我应该期望 AtomicInteger 计数器引入多少开销？
AtomicInteger没有错：在非阻塞环境下使用是个好东西。但是，如果您向队列中添加一个 AtomicInteger 计数器，则会引入一个 pool() 和 offer(E) 都必须保持更新的位置。这将增加 CAS 操作的数量以及 failed 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)?
请注意，size()返回的结果可能不准确，正如他们所说，"is typically not very useful in concurrent applications"。
Javadoc for ConcurrentLinkedQueue明确指出size()方法的复杂度为O(n)。我觉得这令人惊讶。我会通过在计数器中累积大小来遵循股票 LinkedList.size() 方法。鉴于 ConcurrentLinkedQueue 操作的异步性质，自然计数器必须是 AtomicInteger。不这样做是因为它会 运行 违反非阻塞保证吗？如果是这样，我应该期望 AtomicInteger 计数器引入多少开销？
AtomicInteger没有错：在非阻塞环境下使用是个好东西。但是，如果您向队列中添加一个 AtomicInteger 计数器，则会引入一个 pool() 和 offer(E) 都必须保持更新的位置。这将增加 CAS 操作的数量以及 failed 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)?
请注意，size()返回的结果可能不准确，正如他们所说，"is typically not very useful in concurrent applications"。