List.Add() thread safety

Question

I understand that in general a List is not thread safe, however is there anything wrong with simply adding items into a list if the threads never perform any other operations on the list (such as traversing it)?

Example:

List<object> list = new List<object>();
Parallel.ForEach(transactions, tran =>
{
    list.Add(new object());
});

Solution 1

Behind the scenes lots of things happen, including reallocating buffers and copying elements. That code will cause danger. Very simply, there are no atomic operations when adding to a list, at the least the "Length" property needs to be updates, and item needs to be put in at the right location, and (if there's a separate variable) the index needs to be updated. Multiple threads can trample over each other. And if a grow is required then there is lots more going on. If something is writing to a list nothing else should be reading or writing to it.

In .NET 4.0 we have concurrent collections, which are handily threadsafe and don't require locks.

Solution 2

You current approach is not thread-safe - I would suggest avoiding this altogether - since you basically do a data transformation PLINQ might be a better approach ( I know this is a simplified example but in the end you are projecting each transaction into another "state" object).

List<object> list = transactions.AsParallel()
                                .Select( tran => new object())
                                .ToList();

Solution 3

I solved my problem using ConcurrentBag<T> instead of List<T> like this:

ConcurrentBag<object> list = new ConcurrentBag<object>();
Parallel.ForEach(transactions, tran =>
{
    list.Add(new object());
});

Solution 4

If you want to use List.add from multiple threads and do not care about the ordering, then you probably do not need the indexing ability of a List anyway, and should use some of the available concurrent collections instead.

If you ignore this advice and only do add, you could make add thread safe but in unpredictable order like this:

private Object someListLock = new Object(); // only once

...

lock (someListLock)
{
    someList.Add(item);
}

If you accept this unpredictable ordering, chances are that you as mentioned earlier do not need a collection that can do indexing as in someList[i].

Solution 5

It's not an unreasonable thing to ask. There are cases where methods which can cause thread-safety issues in combination with other methods are safe if they are the only method called.

However, this clearly isn't a case of it, when you consider the code shown in reflector:

public void Add(T item)
{
    if (this._size == this._items.Length)
    {
        this.EnsureCapacity(this._size + 1);
    }
    this._items[this._size++] = item;
    this._version++;
}

Even if EnsureCapacity was in itself threadsafe (and it most certainly is not), the above code is clearly not going to be threadsafe, considering the possibility of simultaneous calls to the increment operator causing mis-writes.

Either lock, use ConcurrentList, or perhaps use a lock-free queue as the place multiple threads write to, and the read from it - either directly or by filling a list with it - after they have done their work (I'm assuming that multiple simultaneous writes followed by single-threaded reading is your pattern here, judging from your question, as otherwise I can't see how the condition where Add is the only method called could be of any use).

View more solutions

Comments

[JK.]

Exact duplicate of List<T> thread safety

[osmiumbin]

I once used a List<T> only to add new objects from multiple tasks run in parallel. Sometimes, very rare, when iterating through the list after all the tasks have completed it ended up with a record that was null, which, if no extra threads would have been involved, it would have been practically impossible for this to happen. I guess that, when the list was internally re-allocating its elements to expand, somehow another thread messed it up by trying to add another object. So its not a good idea to do so!

[Blackey]

Exactly what I'm currently seeing @osmiumbin with regard to an object inexplicably being null when simply adding from multiple threads. Thanks for the confirmation.

[e36M3]

That makes perfect sense, I will definitely look at the new Concurrent collections for this. Thank you.

[e36M3]

I presented an overly simplified example to stress the aspect of List.Add that I was interested in. My Parallel.Foreach in fact will do a good amount of work and will not be a simple data transformation. Thanks.

[LukeH]

Note that there's no built-in ConcurrentList type. There are concurrent bags, dictionaries, stacks, queues etc, but no lists.

[BrokenGlass]

concurrent collections can cripple your parallel performance if used unneeded - another thing you can do is use a fixed size array and use the Parallel.Foreach overload that takes in index - in that case each thread is manipulating a different array entry and you should be safe.

[Bas Smit]

@royi are you running this on a single core machine?

[Dave Walker]

Hi, I think there is a problem with this example as it is setting the AutoResetEvent whenever it finds the number 1000. Because it can process these threads kinda whenever it wants it can get to 1000 before it gets to 999 for instance. If you add a Console.WriteLine in the AddTol method then you will see that the numbering is not in order.

[Bas Smit]

@dave, its setting the event when i == 0