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

Question

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.

[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:

Running the test several times shows that sometimes the resulting list count is not the expected 1000 (=10 x 100), but less.
No exceptions occur during adding.

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?

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.

The point of non-thread-safety is that it often leads to bugs that will not reproduce *100%* of the time. I seem to remember seeing it sometimes manage to dereference nulls in the past and that would raise an exception. But what's the *point* of this test? You now know `List` isn't thread safe, so why do any more work to "prove" it? — Damien_The_Unbeliever, Jul 27 '18 at 09:16
Where do you find that List is thread-safe? [Documentation](https://msdn.microsoft.com/en-us/library/6sh2ey19(v=vs.110).aspx) (bottom of page) states `It is safe to perform multiple read operations on a List, but issues can occur if the collection is modified while it’s being read.` and that's what you are doing. — Renatas M., Jul 27 '18 at 09:21
Doing something that is not threadsafe is like driving through a red light at an intersection. Sometimes nothing happens at all. Sometimes there's an enormous crash and everyone dies. Sometimes other bad things happen in between those two extremes. The result is never guaranteed to be the same. — J..., Jul 27 '18 at 09:22
@Reniuz: Why am I modifying the list while it is being read? — mike, Jul 27 '18 at 09:26
@J - I like that analogy because also, sometimes nothing *seems* to have gone wrong and then suddenly weeks later (or back to code, somewhere completely unrelated) things do suddenly go wrong (you receive a fine from someone operating a camera on that light) — Damien_The_Unbeliever, Jul 27 '18 at 09:27
@Damien_The_Unbeliever: Out of curiosity, because I like seeing for myself how things work and/or fail and the result of the test is relevant, because it shows that wrongly using a `List` as done in the test will not throw an exception, but fail silently - which is good to know for future debugging scenarios. — mike, Jul 27 '18 at 09:31
Example: you adding object in the list (modifying) and writing list count (reading) to console. Imagine that you adding item - expanding capacity and trying to get list capacity at the same time. You may get capacity value before it is expanded so it will be incorrect. — Renatas M., Jul 27 '18 at 09:31
But as Reniuz has already pointed you, if you want to know what you can *trust*, you ought to be reading the official *documentation*. Experiments can tell you what *may* happen but they don't tell you what the developers have guaranteed *not to change about internal implementation details in the future*. All of .NET framework documentation has *specific* sections on thread safety. — Damien_The_Unbeliever, Jul 27 '18 at 09:33
And even if you found that it did throw exceptions (sometimes, which it may still do, you haven't proved that it *won't*), that information is pointless because it would be throwing exceptions *due to programmer errors*. You shouldn't catch those exceptions, you should fix your code. — Damien_The_Unbeliever, Jul 27 '18 at 09:36
There is little to no code in .NET that *checks* that it isn't incorrectly used by multiple threads at the same time. The only code is probably the one in WPF/Windows Forms (that have a stricter rule: only the thread that created the window can manipulate it). — xanatos, Jul 27 '18 at 09:43

Renatas M. · Accepted Answer · 2018-07-27T09:49:12.023

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 and you will loose one item.

Damien_The_Unbeliever · Answer 2 · 2018-07-27T09:47:53.907

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

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.

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.

¹Code taken from the reference source which of course means that it may not be exactly the same as the code that is actually running, because the developers are free to change their implementations, only respecting documented guarantees.

@Reniuz - yes, but we raced on two different race conditions :-). Yours is a lost update. Mine is inconsistent state leading to an exception. — Damien_The_Unbeliever, Jul 27 '18 at 09:48

score 1 · Answer 3 · answered Jul 27 '18 at 09:24

1

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.

answered Jul 27 '18 at 09:24

Fabulous

2,393
2
20
27

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

3 Answers3