size of ConcurrentLinkedQueue

Question

Reading Java's ConcurrentLinkedQueue Docs, I wonder why it is not possible for the implementation to store the size:

Beware that, unlike in most collections, the size method is NOT a constant-time operation. Because of the asynchronous nature of these queues, determining the current number of elements requires a traversal of the elements.

Where in the source is this "asynchronous nature"? I only see a while-loop to retry enqueing until the AtomicReferences match the expected values/references. Why is it not possible to increment an size:AtomicInteger after successfully offering a value to the Queue?

Thanks alot.

Answer 1

Imagine you have two threads, one adding a new item, and the other deleting an item. There are no items in the queue at the start.

Suppose the first thread adds the item, immediately followed by the other thread removing the item and decrementing the size, at which point your size is at -1, then the first thread increments the size to 0.

A slightly contrived example, but you would need to make the whole operation atomic in order to ensure that no other threads could get access to the size of -1.