Why does ConcurrentWhatever.Count take a snapshot

Question

On C#/.NET Little Wonders article for ConcurrentStack / Concurrent Queue, 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 1

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.

Answer 2

I don't know for sure, but here's a guess.

The stack could be implemented as a singly-linked list, consisting of immutable cells, where each cell points to the cell underneath it on the stack. Then a "snapshot" would simply be to make a copy of the top of the stack; because the cells are immutable, this pulls along the rest of the current stack as well.

Thus, the snapshot would be an O(1) operation, but counting the actual items is still O(n).