Why does ConcurrentWhatever.Count take a picture

Question

The C # /. NET Little Wonders article for ConcurrentStack / Parallel Queue states the following with respect to the .Count operation on ConcurrentStack :

The graph takes a snapshot of the stack and then counts the elements. That means this is O (n) operation, if you just want to check for an empty stack, call IsEmpty, namely O (1).

I am not very versed in multithreaded programming yet, but I understand why you cannot just iterate over elements in collections and read them, because the collection can be simultaneously changed by other threads. However, if you need to lock ConcurrentStack long enough to take a snapshot, wouldn’t it be easier to count the elements while you locked it, return this account and release the lock, instead of overhead and time-consuming to create the whole snapshot until the lock is released?

Perhaps I am missing something in common with how this works, and I would appreciate any thoughts or insights that you may have.

Answer 1

I do not know for sure, but here's a hunch.

The stack can be implemented as a single-linked list consisting of immutable cells, where each cell points to a cell below it in the stack. Then the “snapshot” just had to make a copy of the top of the stack; because cells are immutable, this pulls the rest of the current stack as well.

Thus, the snapshot will perform the O (1) operation, but the count of the actual elements is still O (n).

Answer 2

I don’t know if this is implemented like this, but if you implement it as a singly linked list with immutable nodes, then the snapshot is almost free and does not require blocking. You just get the current top element. Then follow the linked list until the beginning.

You can save the position of each node on the node stack, but it will trade memory for Count performance. And, probably, the count is not called generic enough to guarantee that extra memory is on the node.

Most ConcurrentCollection work without locks. Such a supported stack with binding can, for example, be built using Interlocked.CompareExchange in a field that points to the current node. And if you make some operations inactive, you usually need to make all of them locked, since unblocked operations will not abide by the lock.

Answer 3

You assume that in order to count on a snapshot, he must take out a big lock.

I believe that parallel collections are being developed with a cheap - perhaps optimistic - picture. For example, if you iterate over ConcurrentStack via GetEnumerator() , which also uses a snapshot. I doubt very much that he always performs an O (n) operation to create a snapshot.

Answer 4

ConcurrentStack and ConcurrentQueue are thread safe collections, so locking is not involved. for example, in ConcurrentStack, the count is calculated by reading the node header and then moving the copied count list

Answer 5

I believe the biggest reason is that setting up a parallel queue (where two or more threads always control the content) to count elements is an incorrect concept to start with. I suspect that they only provided the Count property for existing interfaces. Therefore, if the only reason api exists is to satisfy the requirements for the interface, then who cares about how it works, since you should not use it for a start.

When working with objects that are modified by several threads, you should never ask the object about any state / value that another thread can change. Because by the time you answer your question, it can no longer be the correct answer. This seems to be the main problem in the WinForm "InvokeRequired" property. Some APIs are just a bad idea in a multi-threaded environment, and I think this graph falls into this category.

Ultimately, it is strange that the developers did not use an explicit member of the interface for the ICollection.Count property, but did not publish it. Then at least you know that you should not use it. They pointed to the use of IsEmpty on MSDN; however, it is easy to miss it.