Can multiple threads add items to Concurrent collections EXACTLY at the same time?

Question

I am trying to figure out concurrent collections in C#.

ConcurrentBag, ConcurrentDictionary and ConcurrentQueue.

Is it possible for multiple threads to add items to them EXACTLY at the same time? Or they wait one after the other?

I tried to examine their source code, but I really couldn't tell for sure.

I see here that there is an answer for C++, but I would like to know if this is the case also for C#?

It's not a good post, but you might find an answer here: https://stackoverflow.com/questions/28781817/how-collections-concurrent-library-work-under-the-hood — gunr2171, Mar 22 '22 at 15:17
Define "at the same time"? Adding an item will take multiple CPU instructions, which are then translated to micro-ops inside the processor, and dispatched into this big superscalar system which schedules and re-orders micro-ops at will. Could two threads execute exactly the same instructions, in lockstep, to add two items at the same time? Maybe, but it's vanishing unlikely: modern CPUs just don't work that way. It also depends on the collection: they often have lock-free paths and paths which require locks, depending on various conditions — canton7, Mar 22 '22 at 15:18

Theodor Zoulias · Answer 1 · 2022-03-22T21:36:46.867

It's not provable, at the software level. Meaning that you can't write a program that can prove or disprove the theory that two items can be inserted by two threads in the same collection at exactly the same time.

One attempt to prove it would be to have a third thread acting as the observer, that would enumerate the collection repeatedly in a tight loop while the other two threads are doing the two concurrent insertions. Let's say that the observer thread observed zero elements in one enumeration and two elements in the next enumeration, what would this prove? A thread can be suspended by the operating system at any moment for a duration measured in milliseconds, so you haven't learned anything conclusive about the issue at hand. The two insertions might have happened exactly the same time, or milliseconds apart from one another, who knows?

If you want to answer this question at the hardware level, then at this level the concept of "collection" does not exist. You have registers, CPU instructions, memory chips etc. There are no software objects to talk about at this level.

@MiBuena Solomon Slow's [answer](https://stackoverflow.com/a/71575562/11178549) might be more useful and informative than mine. — Theodor Zoulias, Mar 22 '22 at 17:36
yes, it goes in little more detail. Still both answers are very useful. :) Thx a lot. :) — MiBuena, Mar 22 '22 at 18:38

score 1 · Accepted Answer · answered Mar 22 '22 at 16:25

Adding an object to a collection is not a simple operation. It's a sequence of events.

Events can be simultaneous, but when we're talking about sequences of events, either the sequences overlap, or they are disjoint.

Computer hardware is designed such that, if two events happen simultaneously, the outcome will always be as if one of them happened before the other. The reason is simple. Suppose thread A assigns v=3, and suppose thread B assigns v=5. If thread A goes first, the final outcome will be v==5. If thread B goes first, the final outcome will be v==3. No programmer ever wants to have to deal with a third possible outcome. What would it even be?

Regardless of what happens in the hardware, when we talk about events in programs, we never say "simultaneous." We trust the hardware to behave as if that possibility did not exist.

When we talk about overlapping sequences of operations (e.g., adding objects to some collection), that's a major concern. That's what concurrency control is all about.

If concurrency control is done right, then after two threads each insert an object into a collection, the collection will be guaranteed to contain both objects. If it's done wrong, almost anything is possible, (including the possibility that any further attempt to use the collection will crash the program.)

You could literally spend years studying all of the different methods of concurrency control.

score 0 · Answer 3 · answered Mar 22 '22 at 15:31

In a very general sense, the answer is that additions are serialized, ie they wait for each other.

The exact mechanism depends on a slew of conditions, and as much as possible they try to do it without locks (interlocked exchanges instead of locks or mutexes), but there are some paths that require locks (at a glance, if the internal array needs to be resized or if someone else is requesting a synchronized enumeration for example).

Can multiple threads add items to Concurrent collections EXACTLY at the same time?

3 Answers3