Threadsafe foreach enumeration of lists

Question

I need to enumerate though generic IList<> of objects. The contents of the list may change, as in being added or removed by other threads, and this will kill my enumeration with a "Collection was modified; enumeration operation may not execute."

What is a good way of doing threadsafe foreach on a IList<>? prefferably without cloning the entire list. It is not possible to clone the actual objects referenced by the list.

Answer 1

Cloning the list is the easiest and best way, because it ensures your list won't change out from under you. If the list is simply too large to clone, consider putting a lock around it that must be taken before reading/writing to it.

Answer 2

Your problem is that an enumeration does not allow the IList to change. This means you have to avoid this while going through the list.

A few possibilities come to mind:

• Clone the list. Now each enumerator has its own copy to work on.
• Serialize the access to the list. Use a lock to make sure no other thread can modify it while it is being enumerated.

Alternatively, you could write your own implementation of IList and IEnumerator that allows the kind of parallel access you need. However, I'm afraid this won't be simple.

Answer 3

There is no such operation. The best you can do is

lock(collection){
    foreach (object o in collection){
       ...
    }
}

Answer 4

You'll find that's a very interesting topic.

The best approach relies on the ReadWriteResourceLock which use to have big performance issues due to the so called Convoy Problem.

The best article I've found treating the subject is this one by Jeffrey Richter which exposes its own method for a high performance solution.

Answer 5

So the requirements are: you need to enumerate through an IList<> without making a copy while simultaniously adding and removing elements.

Could you clarify a few things? Are insertions and deletions happening only at the beginning or end of the list? If modifications can occur at any point in the list, how should the enumeration behave when elements are removed or added near or on the location of the enumeration's current element?

This is certainly doable by creating a custom IEnumerable object with perhaps an integer index, but only if you can control all access to your IList<> object (for locking and maintaining the state of your enumeration). But multithreaded programming is a tricky business under the best of circumstances, and this is a complex probablem.

Answer 6

Forech depends on the fact that the collection will not change. If you want to iterate over a collection that can change, use the normal for construct and be prepared to nondeterministic behavior. Locking might be a better idea, depending on what you're doing.

Answer 7

ICollection MyCollection;
// Instantiate and populate the collection
lock(MyCollection.SyncRoot) {
  // Some operation on the collection, which is now thread safe.
}

From MSDN

Answer 8

Default behavior for a simple indexed data structure like a linked list, b-tree, or hash table is to enumerate in order from the first to the last. It would not cause a problem to insert an element in the data structure after the iterator had already past that point or to insert one that the iterator would enumerate once it had arrived, and such an event could be detected by the application and handled if the application required it. To detect a change in the collection and throw an error during enumeration I could only imagine was someone's (bad) idea of doing what they thought the programmer would want. Indeed, Microsoft has fixed their collections to work correctly. They have called their shiny new unbroken collections ConcurrentCollections (System.Collections.Concurrent) in .NET 4.0.

Answer 9

Wrap the list in a locking object for reading and writing. You can even iterate with multiple readers at once if you have a suitable lock, that allows multiple concurrent readers but also a single writer (when there are no readers).

Answer 10

I recently spend some time multip-threading a large application and had a lot of issues with the foreach operating on list of objects shared across threads.

In many cases you can use the good old for-loop and immediately assign the object to a copy to use inside the loop. Just keep in mind that all threads writing to the objects of your list should write to different data of the objects. Otherwise, use a lock or a copy as the other contributors suggest.

Example:

foreach(var p in Points)
{
    // work with p...
}

Can be replaced by:

for(int i = 0; i < Points.Count; i ++)
{
   Point p = Points[i];
   // work with p...
}

Answer 11

This is something that I've recently had to deal with and to me it really depends on what you're doing with the list.

If you need to use the list at a point in time (given the number of elements currently in it) AND another thread can only ADD to the end of the list, then maybe you just switch out to a FOR loop with a counter. At the point you grab the counter, you're only seeing X numbers of elements in the list. You can walk through the list (while others are adding to the end of it) . . . should not cause a problem.

Now, if the list needs to have items taken OUT of it by other threads, or CLEARED by other threads, then you'll need to implement one of the locking mechanisms mentioned above. Also, you may want to look at some of the newer "concurrent" collection classes (though I don't believe they implement IList - so you may need refactor for a dictionary).