Javadoc for ConcurrentLinkedQueue explicitly states that the complexity of the size() method is O(n). I find this surprising. I would follow the stock LinkedList.size() approach by accumulating the size in a counter. Given the asynchronous nature of ConcurrentLinkedQueue's operations, naturally the counter would have to be AtomicInteger. Was this not done because it would run against the non-blocking guarantees? If so, how much of an overhead should I expect the AtomicInteger counter to introduce?
There is nothing wrong with AtomicInteger: it's a good thing to use in a non-blocking environment. However, if you added an AtomicInteger counter to the queue, you would introduce a place which both pool() and offer(E) have to keep updated. That would increase the number of CAS operations as well as the number of failed CAS operations.
The Javadoc tells us that having fewer CASes might be a good optimization.
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)?
Note that the returned result of size() may be inaccurate, and, as they put it, "is typically not very useful in concurrent applications".