c# Parallel For Loop index exceptions after removing the element

Question

In my algorithm, what I am trying to do is following.

while (R.Count > 0)
{
    //R is also  List<string>()   
    var N = new List<string>();
    var first = R[0];
    N.Add(first);
    R.Remove(first);
    //below commented code runs just fine but it takes a lot of time that is why i need to do multithreading to make it faster
    //for (int i = R.Count - 1; i >= 0; i--)
    //{
    //    if (hamming(first, R[i]))
    //    {   //hamming is a function just compare two strings and returns true or false.
    //        N.Add(R[i]);
    //        R.RemoveAt(i);
    //    }
    //}

    //Below is code of my attempt of multithreading the loop. I have tried it with foreach loop as well and it gives same error 'index out of range or argument exception'

    //ATTEMPT 1 :-
    Parallel.For(0,R.Count, i =>
    {

        if (hamming(first, R[i]))
        {
            N.Add(R[i]);
            R.RemoveAt(i);
        }
    });
    //ATTEMPT 2 :-
    Parallel.For(0,R.Count, i =>
    {

        if (hamming(first, R[i]))
        {
            N.Add(R[i]);
            R[i]="";
        }
    });
    var K = R.Where(a => a == "").ToList();
    var nc = cou - N.Count;
    //the value of 'K.Count' and 'nc' should be same here but I have checked in debugger its not the same.

    N_Total.Add(N);//this is just a List<List<string>>

}

The Code is pretty self explanatory but I will still try to elaborate ir further here.

Basically I need to run this algo and compare values as shown in the code and if hamming returns true I have to add that value to 'N' and remove it from 'R', I have to remove it because when next time the outer while loop runs List 'R' should be smaller and only those values should be present in R which didn't satisfy the hamming condition in previous run of the loop.

I can elaborate further if someone needs to understand more.

What I want is that to achieve this goal in some multithread way and without exceptions of index out of range or Argument exceptions.

Thanks a lot in advance.

Answer 1

Use Parallel.Foreach on R. Parallel.Foreach will split your list into smaller chunks and starts processing them. so indexes from different threads will not collide with each other.

for N you will use ConcurrentBag instead of List because its thread safe. that means when two threads happen to add item to your bag strange things will not happen.

if you remove items inside Parallel you should notify all threads from new changes which will be hard (and quite ugly) to implement.

List<string> R = new List<string>();


while (R.Count > 0)
{
    var removing = new ConcurrentBag<long>();

    var N = new ConcurrentBag<string>();
    var first = R[0];
    N.Add(first);
    R.Remove(first);

    Parallel.ForEach(R, (item, state, index) =>
    {
        if(hamming(first, item))
        {
            N.Add(item);

            R[(int)index] = null; // mark as null and ignore. 
                                  // this is not thread safe for versioning of list but doesn't matter.
                                  // for R ConcurrentBag can be used too but it doesn't change results after all.
        }
    });

    // now we are safe to reorganize our collection.
    R = R.Where(str => str != null).ToList(); // parallel execution doesn't help. see comments below. 
                                              // for very large collection this will finish in few milliseconds.

    // get other stuff...
}

Answer 2

First of all List<string> is not ThreadSafe which means it should't be used in parallel operations at all.

Try that: ConcurrentBag<string> instead.

ConcurentBag exists in System.Collections.Concurrent namespace, which contains few more thread safe collections.

---

Another thing is:

You want to make sure if that index exists before doing anything with it.

---

ConcurentBag may have some restrictions, maybe it's worth of checking other collections from that namespace: System.Collections.Concurrent as those are ThreadSafe.

https://msdn.microsoft.com/en-us/library/system.collections.concurrent.aspx