Multi tool use

Clash Royale CLAN TAG

Why does List<>.Add from multiple threads lead to varying results?

I was wondering, if List<T> is thread-safe and read that several readers are no problem, but more than one writer may cause issues. So I wrote the following test to see what actually happens.

List<T>

[TestClass]
public class ListConcurrency
{
[TestMethod]
public void MultipleWritersTest()
{
var taskCnt = 10;
var addCnt = 100;

var list = new List<object>();
var tasks = new List<Task>();
for (int i = 0; i < taskCnt; i++)
{
var iq = i;
tasks.Add(Task.Run(() =>
{
Console.WriteLine("STARTING : " + iq);
for (int j = 0; j < addCnt; j++)
{
try
{
list.Add(new object());
}
catch (Exception e)
{
Console.WriteLine(e);
}
}
Console.WriteLine("FINISHING: " + iq);

}));
}

Task.WhenAll(tasks).Wait();

Console.WriteLine("FINISHED: " + list.Count);
}
}


And here is an example output:

STARTING : 0
FINISHING: 0
STARTING : 1
FINISHING: 1
STARTING : 8
STARTING : 9
FINISHING: 9
FINISHING: 8
STARTING : 2
FINISHING: 2
STARTING : 7
STARTING : 3
FINISHING: 3
FINISHING: 7
STARTING : 4
FINISHING: 4
STARTING : 6
FINISHING: 6
STARTING : 5
FINISHING: 5
FINISHED: 979


I was surprised by two things:

If both would happen (expections and wrong item count) it would make sense... Is this simply the way List<T> demonstrates its non-thread-safety?

List<T>

EDIT: My opening line was badly phrased, I know that List<T> is not thread-safe (e.g. for iterating), but I wanted to see what happens, if it is "abused" in this way. As I wrote in a comment below, the results (that no exceptions will be thrown) may be useful for others when debugging.

List<T>

List<T>

list.Add(new object());

List<T>

It is safe to perform multiple read operations on a List<T>, but issues can occur if the collection is modified while it’s being read.

3 Answers
3

List<T> isn't threadsafe and you'll need to work with a different collection. You should try using ConcurrentBag<T> or any of the other collection types specified here in the documentation.

List<T>

ConcurrentBag<T>

Okay, let's look at Add and consider what happens when mutliple threads are accessing it:

Add

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


Looks alright. But let's consider what happens for a particularly unlucky thread that has already gone past line 1 of this code before another thread manages to execute line 2, resulting in _size becoming equal to _items.Length. Our unlucky thread is now going to walk off the end of the _items array and throw an exception.

_size

_items.Length

_items

So, despite your "proof" that it won't throw an exception, I found an obvious race that would lead to one after about 2 minutes of inspecting the code.

If you check the source code of List you will see that internally it operates on array. The Add method expands array size and inserts new item:

// Adds the given object to the end of this list. The size of the list is
// increased by one. If required, the capacity of the list is doubled
// before adding the new element.
//
public void Add(T item)
{
if (_size == _items.Length) EnsureCapacity(_size + 1);
_items[_size++] = item;
_version++;
}


Now imagine you have array with size of 10 and 2 threads inserts at the same time - both expands array to 11 and one thread inserts at index 11 and other overwrites item at index 11. And that's why you get list count of 11 not 12.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.