List: Moving from immutable to changeable structure

Question

I am currently using quite heavily some List and I am looping very frequently via foreach over these lists.
Originally List was immuteable afer the startup. Now I have a requirement to amend the List during runtime from one thread only (a kind of listener). I need to remove from the List in object A and add to the list of object B. A and B are instances of the same class.
Unfortunaly there is no Synchronized List. What would you suggest me to do in this case? in my case speed is more important than synchronisation, thus I am currently working with copies of the lists for add/remove to avoid that the enumerators fail.
Do you have any other recommended way to deal with this?

class X {
    List<T> Related {get; set;}
}

In several places and in different threads I am then using

 foreach var x in X.Related

Now I need to basically perform in yet another thread

a.Related.Remove(t);
b.Related.Add(t);

To avoid potential exceptions, I am currently doing this:

List<T> aNew=new List<T> (a.Related);
aNew.Remove(t);
a.Related=aNew;
List<T>bNew=new List<T>(b.Related){t};
b.Related=bNew;

Is this correct to avoid exceptions?

Answer 1

From this MSDN post: http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx

"...the only way to ensure thread safety is to lock the collection during the entire enumeration. "

Answer 2

Consider using for loops and iterate over your collection in reverse. This way you do not have the "enumerators fail", and as you are going backwards over your collection it is consistent from the POV of the loop.

It's hard to discuss the threading aspects as there is limited detail.

Update

If your collections are small, and you only have 3-4 "potential" concurrent users, I would suggest using a plain locking strategy as suggested by @Jalal although you would need to iterate backwards, e.g.

private readonly object _syncObj = new object();

lock (_syncObj)
{
    for (int i = list.Count - 1; i >= 0; i--)
    {
        //remove from the list and add to the second one.
    }
}

You need to protect all accesses to your lists with these lock blocks.

Your current implementation uses the COW (Copy-On-Write) strategy, which can be effective in some scenarios, but your particular implementation suffers from the fact that two or more threads take a copy, make their changes, but then could potentially overwrite the results of other threads.

Update

Further to your question comment, if you are guaranteed to only have one thread updating the collections, then your use of COW is valid, as there is no chance of multiple threads making updates and updates being lost by overwriting by multiple threads. It's a good use of the COW strategy to achieve lock free synchronization.

If you bring other threads in to update the collections, my previous locking comments stand.

My only concern would be that the other "reader" threads may have cached values for the addresses of the original lists, and may not see the new addresses when they are updated. In this case make the list variables volatile.

Update

If you do go for the lock-free strategy there is still one more pitfall, there will still be a gap between setting a.Related and b.Related, in which case your reader threads could be iterating over out-of-date collections e.g. item a could have been removed from list1 but not yet added to list2 - item a will be in neither lists. You could also swap the issue around and add to list2 before removing from list1, in which case item a would be in both lists - duplicates.

If consistency is important you should use locking.

Answer 3

You should lock before you handle the lists since you are in multithreading mode, the lock operation itself does not affect the speed here, the lock operation is executed in nanoseconds about 10 ns depending on the machine. So:

private readonly object _listLocker = new object();

lock (_listLocker)
{
    for (int itemIndex = 0; itemIndex < list.Count; itemIndex++)
    {
        //remove from the first list and add to the second one.
    }
}

If you are using framework 4.0 I encorage you to use ConcurrentBag instead of list.

Edit: code snippet:

List<T> aNew=new List<T> (a.Related);

This will work if only all interaction with the collection "including add remove replace items" managed this way. Also you have to use System.Threading.Interlocked.CompareExchange and System.Threading.Interlocked.Exchange methods to replace the existing collection with the new modified. if that is not the case then you are doing nothing by coping

This will not work. for instance consider a thread trying to get an item from the collection, at the same time another thread replace the collection. this could leave the item retrieved in a not constant data. also consider while you are coping the collection, another thread want to insert item to the collection at the same time while you are coping?
This will throw exception indicates that the collection modified.

Another thing is that you are coping the whole collection to a new list to handle it. certainly this will harm the performance, and I think using synchronization mechanism such as lock reduce the performance pallet, and it is the much appropriated thing to do while to handle multithreading scenarios.