Parallelised loop with adding to list

Question

Is it possible to parallelise a loop where the length of the loop is increased within?

List<int> list = new List<int>() { 0, 1 };

for (int i = 0; i < list.Count; i++)
//Parallel.For(0, list.Count, (i) =>
{
    Console.WriteLine(list[i]);
    if (i == 0) list.Add(2);
}//);

//foreach (int i in list)
//Parallel.ForEach(list, (i) =>
//{
//    Console.WriteLine(i);
//    if (i == 0) list.Add(2);
//}//);

Console.ReadLine();

In this simple example, the intended output is:

0
1
2

The above code works correctly with a serial 'for', but fails for the serial 'foreach' due to the collection being modified. For both parallelised implementations, the code completes but the output is missing the final '2'.

You could split the code into a threadsafe list of workitems and some code that can be multithreaded to handle the workitems. Use a pointer of 'next' workitem and some locking and you should be fine. — CodingBarfield, Mar 28 '14 at 14:23

score 3 · Answer 1 · edited May 23 '17 at 12:11

It isn't valid to change a collection in a for each loop. Basically modifying the list in any way invalidates the enumerator. The following is a quote from the documents for IEnumerator:

An enumerator remains valid as long as the collection remains unchanged. If changes are made to the collection, such as adding, modifying, or deleting elements, the enumerator is irrecoverably invalidated and its behavior is undefined.

For more information take a look at this post. As far as the parallel implementations:

Parallel.ForEach - This is subject to the same IEnumerator issues that a standard for each is
Parallel.For - This passes the number of loops into the for as a constant, not as a reference. That means when count changes it doesn't change the number of times it will loop

A safer pattern is to add, remove, and modify your list elements prior to calling the parallels implementation. Then threads can process these elements. If that can't be done, then determine the number of elements that you will have after the loop, then use an array to store/process these by index. Finally pull any non-null values back into a list. That way you don't have to worry about thread safety with regards to your list (Insert would push other elements forward making your indexes invalid). The following should work:

// EX: might be initialized with a call to the database: "COUNT(id)"
int expectedElements = 10;
if (myList.Count < expectedElements)
  for (var idx = myList.Count; idx <= expectedElements; idx++) myList.Add(null);

var elements = myList.ToArray();
System.Threading.Tasks.Parallel.For(0, expectedElements, (idx) =>
{
  // "remove" the element
  if (idx % 3 == 0) elements[idx] = null;

  // "modify" the element
  if (idx % 3 == 1) elements[idx] = DifferentElement(idx);

  // "add" an element
  if (idx % 3 == 2) elements[idx] = GetNewElement(idx);
});

// clear current list, add new elements, remove null values
myList.Clear();
myList.AddRange(elements);
myList.RemoveAll(item => item == null);

Now you can "add", "remove" and "modify" as much as you want and the result is back in a list!

Anthony Raymond · Answer 2 · 2014-03-28T13:28:07.590

0

for (int i = 0; i < list.Count; i++) //list.Count will only checked at first call
{
    Console.WriteLine(list[i]);
    if (i == 0) list.Add(2);
}

Sounds like Your list.Count will be asked one, then it will be kept in memory, in your case, list.Count will be 2 and never move, so you will print list[0] then list[1].
You may also be interested by lock :

Thread A:

lock (list) {
    foreach (Object obj in list) {
        obj.doSomething();
        if(meet_condition) list2.add(obj)
    }
}

Where list2 is a Static attribute.

Thread B :

lock (list) {
  list.Remove(Element);
}

As soon as a Thread lock the list, other Thread wait until it is released to use it. It's hard to help you more than that without knowing what you are attempt to do with it.

edited Mar 28 '14 at 13:28

answered Mar 28 '14 at 13:07

Anthony Raymond

7,434
6
42
59

Yes, it looks like the serial for loop reevaluates with each pass, so it sees that list.Count has incremented. Evidentally, the parallel implementations do not reevaluate. Is there a way around this? – user1765603 Mar 28 '14 at 13:10
If you aim is to print numbers in console, you can Override add method from list, instead of simple add to the list you can add a Console.WriteLine(value) then list.Add(value); – Anthony Raymond Mar 28 '14 at 13:13
This is a simple example of the problem I face. The actual algorithm is far more complicated. – user1765603 Mar 28 '14 at 13:17
Maybe you can create a temporary copy of your List and iterate througt this copyed List – Anthony Raymond Mar 28 '14 at 13:19
Be careful with `lock` - if used too much it basically negates the value of threading entirely. – drew_w Mar 28 '14 at 13:35

Parallelised loop with adding to list

2 Answers2