Iterate and do operations on a generic collection concurrently

Question

I've created a game emulation program using c# async socks. I need to remove/add & do iterations on a collection (a list that holds clients) concurrently. I am currently using "lock", however, it's a a huge performance drop. I also do not want to use "local lists/copies" to keep the list up-to-date. I've heard about "ConcurrentBags", however, I am not sure how thread safe they are for iterations (for instance if a thread removes an element from the list while another thread is doing an iteration on it!?).

What do you suggest?

Edit: here is a situation this is when a packet is sent to all the users in a room

lock (parent.gameClientList)
{
    for (int i = 0; i <= parent.gameClientList.Count() - 1; i++) if (parent.gameClientList[i].zoneId == zoneId) parent.gameClientList[i].SendXt(packetElements); //if room matches - SendXt sends a packet
}

When a new client connects

 Client connectedClient = new Client(socket, this);
 lock (gameClientList)
 {
     gameClientList.Add(connectedClient);
 }

Same case when a client disconnects.

I am asking for a better alternative (performance-wise) because the locks slow down everything.

Well have you read the documentation on `ConcurrentBag`? http://msdn.microsoft.com/en-us/library/dd381779.aspx — Jon Skeet, Sep 12 '13 at 16:58
It's not clear what you want to happen. If one thread is iterating a collection and an item is removed what do you *want* to happen. By "iterating" do you mean taking a snapshot of the collection at a point in time? Always returning any item that you haven't yet been given until there are none, or what? — Servy, Sep 12 '13 at 16:58
Sometimes, I have to send a packet to every user in a specific room, that's when I use an iteration to check if my roomId matches with theirs. If I didn't lock the client list, it would throw an exception (collection was modified..). — Gabe, Sep 12 '13 at 17:01
@Gabe Yes, and it throws an exception because it doesn't know what it should do. What do you *want* it to do? What should it return when the collection is modified? — Servy, Sep 12 '13 at 17:03
I do not want any interruptions. I want every task from every thread to be done properly. — Gabe, Sep 12 '13 at 17:04
@Gabe "done properly" means nothing. As I've told you several times, there is no obvious "proper" result. It's unclear what should happen, which is why an exception is thrown. You need to define *exactly* what needs to happen, to get an answer. Are you fine with any result other than throwing an exception? That's easy, but then you'll likely be back here soon with some unexpected results you want "fixed" because you didn't define what to do in the case of unusual modifications. — Servy, Sep 12 '13 at 17:06
You really need to show the code since you are talking about and describing an "arbitary" situation but want a specific answer that applies to a non provided issue — Daniel MesSer, Sep 12 '13 at 17:07
I'm looking for an alternative. I've provided a few examples in my post. — Gabe, Sep 12 '13 at 17:16
The `ConcurrentBag` will make a copy for you to iterate over, allowing anybody else to modify it during your iteration. — Gabe, Sep 12 '13 at 17:31
`ReaderWriter` locks don't seem to carry as big a performance hit as they used to. If you do a lot of iterating over the list compared to how often you modify it, you might be able to keep your approach but get a performance boost. Essentially many threads can read simultaneously but when a thread wants to write, it gets exclusive access (akin to the lock you use now). http://msdn.microsoft.com/en-us/library/system.threading.readerwriterlockslim.aspx — Erik Noren, Sep 12 '13 at 20:36

Dax Fohl · Answer 1 · 2013-09-12T18:05:07.120

It sounds like the problem is that you're doing all the work within your foreach loop, and it's locking out the add/remove methods for too long. The way around this is to quickly make a copy of the collection while it's locked, and then you can close the lock and iterate on the copy.

Thing[] copy;
lock(myLock) {
  copy = _collection.ToArray();
}
foreach(var thing in copy) {...}

The drawback is that by the time you get around to operating on some object of that copy, it may have been removed from the original collection and so maybe you don't want to operate on it anymore. That's another thing you'll just have to figure out the requirements. If that's a problem, a simple option would be to lock each iteration of the loop, which of course will slow things down but at least it won't lock for the entire duration the loop is running:

foreac(var thing in copy) {
  lock(myLock) {
    if (_collection.Contains(thing)) //check that it's still in the original colleciton
      DoWork(thing); //If you can move this outside the lock it'd make your app snappier, but it could also cause problems if you're doing something "dangerous" in DoWork.
  }
}

If this is what you meant by "local copies", then you can disregard this option, but I figured I'd offer it in case you meant something else.

Arturo Hernandez · Answer 2 · 2013-09-16T14:07:09.453

Every time you do something concurrently you are going to have loss due to task management (i.e. locks). I suggest you look at what is the bottleneck in your process. You seem to have a shared memory model, as opposed to a message passing model. If you know you need to modify the entire collection at once, there may not be a good solution. But if you are making changes in a particular order you can leverage that order to prevent delays. Locks is an implementation of pessimistic concurrency. You could switch to an optimistic concurrency model. In one the cost is waiting in the other the cost is retrying. Again the actual solution depends on your use case.

score 0 · Answer 3 · edited May 23 '17 at 11:56

On problem with ConcurrentBag is that it is unordered so you cannot pull items out by index the same way you are doing it currently. However, you can iterate it via foreach to get the same effect. This iteration will be thread-safe. It will not go bizerk if an item is added or removed while the iteration is happening.

There is another problem with ConcurrentBag though. It actually copies the contents to a new List internally to make the enumerator work correctly. So even if you wanted to just pick off a single item via the enumerator it would still be a O(n) operation because of the way enumerator works. You can verify this by disassembling it.

However, based on context clues from your update I assume that this collection is going to be small. It appears that there is only one entry per "game client" which means it is probably going to store a small number of items right? If that is correct then the performance of the GetEnumerator method will be mostly insignificant.

You should also consider ConcurrentDictionary as well. I noticed that you are trying to match items from the collection based on zoneId. If you store the items in the ConcurrentDictionary keyed by zoneId then you would not need to iterate the collection at all. Of course, this assumes that there is only one entry per zoneId which may not be the case.

You mentioned that you did not want to use "local lists/copies", but you never said why. I think you should reconsider this for the following reasons.

Iterations could be lock-free.
Adding and removing items appears to be infrequent based context clues from your code.

There are a couple of patterns you can use to make the list copying strategy work really well. I talk about them in my answers here and here.

Iterate and do operations on a generic collection concurrently

3 Answers3