Question: On [C#/.NET Little Wonders article for ConcurrentStack / Concurrent Queue](http://geekswithblogs.net/BlackRabbitCoder/archive/2011/02/10/c.net-little-wonders-the-concurrent-collections-1-of-3.aspx), the following is mentioned regarding the `.Count` operation on the `ConcurrentStack`:

> 
> Count takes a snapshot of the stack
>  and then counts the items. This means
>  it is a O(n) operation, if you just
>  want to check for an empty stack, call
>  IsEmpty instead which is O(1).
> 
> 
> 

I'm not greatly experienced in multi-threaded programming yet, but I understand why you can't just loop through the items on the collection and count them, because the collection may be changing by other threads at the same time. However, if you have to lock the `ConcurrentStack` long enough to make a snapshot, wouldn't it be easier just to count the items while you have it locked, return that count, and release the lock, instead of taking the overhead and time cost of generating an entire snapshot before releasing the lock?

I may be missing something basic about how this works, and I would appreciate any thoughts or insight you may have.

Answer: 
I don't know if it's implemented like that, but if you implement it as a singly linked list with immutable nodes then a snapshot is almost free and requires no locking. You just get the current top element. And then follow the linked list to the beginning.

You could save the position of each node on the stack the node, but that'd trade memory for performance of `Count`. And probably count isn't called commonly enough to warrant that extra memory per node.

Most ConcurrentCollection work without locks at all. Such a linked-list backed stack could for example be built using `Interlocked.CompareExchange` on the field pointing to the current node. And if you make some operations lockless, you usually need to make all of them lockless, since the lockless operations won't respect the lock.
ConcurrentStack and ConcurrentQueue are thread safe collections, so no locking is involved. in ConcurrentStack for example, the count is calculated by reading the head node then traversing the list accumulation the count