Index out of range exception when using Parallel for loop

Question

I am trying to execute the following code and I keep getting an Index out of range exception when trying to assign array values to the list:-

        int[] array = new int[1000000];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = i;
        }

        List<int> list = new List<int>();
        Parallel.For(0, array.Length, i => list.Add(array[i]));

Am I doing something wrong here ? I understand that the process is unordered/asynchronous, but why does "i" get values that are higher than the value of "array.Length" ?

Answer 1

The problem is that you cannot call List.Add() concurrently on multiple threads. If you need thread-safe collections, see the System.Collections.Concurrent namespace.

If you break into the debugger when you get an exception, you'll see that i is not greater than array.Length, but is instead a power of 2 that is substantially less than array.Length. What happens is that the List starts out with an empty array of something like 4 elements. Whenever you add an element to a list whose array is full, it creates an array of twice the length of the old array, copies the old elements to it, and stores the new array.

Now let's say that your list is up to 31 elements (meaning it has space for one more) and two threads try to add a 32nd element. They will both execute code like this:

if (_size == _items.Length)
{
    EnsureCapacity(_size + 1);
}
_items[_size++] = item;

First they will both see that _size (31) is not _items.Length (32), so they both execute _size++. The first thread will get 31 (the correct index of the 32nd element) and change _size to 32. The second thread will get 32 and try to index _items[32], which gives you your exception because it's trying to access the 33rd element of a 32-element array.