List <T>: Transition from immutable to mutable structure

Question

I am currently using some kind of list quite heavily, and I very often loop through foreach on these lists.
The initial list was incredible. Now I have a requirement to amend the List at runtime from only one thread (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.
Sorry, no synced list. What would you suggest me to do in this case? in my case, speed is more important than synchronization, so I'm currently working with copies of lists to add / remove to avoid enumeration failures.
Do you have another recommended way to handle this?

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

In several places and in different threads I use

  foreach var x in X.Related 

Now I need to basically execute 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 it right to exclude exceptions?

Answer 1

Consider using for loops and repeat the selection in your collection in reverse order. Thus, you do not have “enumerators,” and as you go back through your collection, this is consistent with the POV loop.

It is difficult to discuss multithreading aspects as there are detailed details.

Update

If your collections are small, and you only have 3-4 “potential” concurrent users, I would suggest using the usual blocking strategy suggested by @Jalal, although you will need to iterate back, for example.

 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 calls to your lists with these lock blocks.

Your current implementation uses the COW (Copy-On-Write) strategy, which may be effective in some scenarios, but your particular implementation suffers from two or more threads taking a copy, making their changes, but then potentially rewriting results from other threads.

Update

In addition to your comment on the question, if you have only one thread updating collections, then your use of COW is acceptable, as there is no chance that multiple threads will cause updates and updates to get lost when overwriting with multiple threads. This is a good use of the COW strategy to provide synchronization without blocking.

If you add other threads to update collections, my previous lock comments are worth it.

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

Update

If you go to the blocking strategy, there is another mistake, there will still be a gap between the a.Related and b.Related , in which case your reader threads can iterate out of date, for example, the a element could be removed from list1, but not yet added to list2 - the a element will not be in any lists. You can also change the problem and add to list2 before deleting from list1, in which case the element a will be duplicates in both lists.

If consistency is important, you should use a lock.

Answer 2

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

"... the only way to guarantee thread safety is to block collection during the entire transfer."

Answer 3

You must lock before processing the lists, since you are in multithreading mode, the lock operation itself does not affect the speed here, the lock operation is performed in nanoseconds of 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 use ConcurrentBag instead of a list.

Edit: code snippet:

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

This will work if only all interaction with the collection is “managed including deletion remove replacement elements”. You should also use System.Threading.Interlocked.CompareExchange and System.Threading.Interlocked.Exchange to replace the existing collection with a new one. if it’s not, you do nothing by managing

This will not work. for example, consider a thread trying to get an item from a collection, while another thread will replace the collection. this may cause the item to be received not in persistent data. also consider when you are managing a collection, does another thread want to insert an element into the collection at the same time while you are managing?
This exception will mean that the collection has been modified.

Another thing is that you are processing the entire collection in a new list to process it. Of course, this will hurt performance, and I think that using a synchronization mechanism such as lock reduces the performance palette, and it is very important to do this for multithreading scripts.