Is it possible for a Dictionary in .Net to cause dead lock when reading and writing to it in parallel?

Question

I was playing with TPL, and trying to find out how big a mess I could make by reading and writing to the same Dictionary in parallel.

So I had this code:

    private static void HowCouldARegularDicionaryDeadLock()
    {
        for (var i = 0; i < 20000; i++)
        {
            TryToReproduceProblem();
        }
    }

    private static void TryToReproduceProblem()
    {
        try
        {
            var dictionary = new Dictionary<int, int>();
            Enumerable.Range(0, 1000000)
                .ToList()
                .AsParallel()
                .ForAll(n =>
                {
                    if (!dictionary.ContainsKey(n))
                    {
                        dictionary[n] = n; //write
                    }
                    var readValue = dictionary[n]; //read
                });
        }
        catch (AggregateException e)
        {
            e.Flatten()
                .InnerExceptions.ToList()
                .ForEach(i => Console.WriteLine(i.Message));
        }
    }

It was pretty messed up indeed, there were a lot of exceptions thrown, mostly about key does not exist, a few about index out of bound of array.

But after running the app for a while, it hangs, and the cpu percentage stays at 25%, the machine has 8 cores. So I assume that's 2 threads running at full capacity.

Then I ran dottrace on it, and got this:

It matches my guess, two threads running at 100%.

Both running the FindEntry method of Dictionary.

Then I ran the app again, with dottrace, this time the result is slightly different:

This time, one thread is running FindEntry, the other Insert.

My first intuition was that it's dead locked, but then I thought it could not be, there is only one shared resource, and it's not locked.

So how should this be explained?

ps: I am not looking to solve the problem, it could be fixed by using a ConcurrentDictionary, or by doing parallel aggregation. I am just looking for a reasonable explanation for this.

Answer 1

So your code is executing Dictionary.FindEntry. It's not a deadlock - a deadlock happens when two threads block in a way which makes them wait for one another to release a resource, but in your case you're getting two seemingly infinite loops. The threads aren't locked.

Let's take a look at this method in the reference source:

private int FindEntry(TKey key) {
    if( key == null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (buckets != null) {
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
        }
    }
    return -1;
}

Take a look at the for loop. The increment part is i = entries[i].next, and guess what: entries is a field which is updated in the Resize method. next is a field of the inner Entry struct:

public int next;        // Index of next entry, -1 if last

If your code can't exit the FindEntry method, the most probable cause would be you've managed to mess the entries in such a way that they produce an infinite sequence when you're following the indexes pointed by the next field.

As for the Insert method, it has a very similar for loop:

for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next)

---

As the Dictionary class is documented to be non-threadsafe, you're in the realm of undefined behavior anyway.

Using a ConcurrentDictionary or a locking pattern such as a ReaderWriterLockSlim (Dictionary is thread-safe for concurrent reads only) or a plain old lock nicely solves the problem.

Answer 2

Looks like a race condition (not a deadlock) - which, as you comment, causes the messed up internal state.

The dictionary is not thread safe so concurrent reads and writes to the same container from seperate threads (even if there are as few as one of each) is not safe.

Once the race condition is hit, it becomes undefined what will happen; in this case what appears to be an infinite loop of some sort.

In general, once write access is required, some form of synchronization is required.

Answer 3

Just to complement (and correlate) the previous 2 great answers:

Dictionary<T> is a HashMap implementation, and like most HashMap implementations it internally uses LinkedLists (to store multiple elements in case different keys result into the same bucket position after being hashed and after taking the hash modulo) and uses an internal array which can grow as the number of elements in the dictionary grow.

Since the code starts with an empty dictionary and adds a lot of elements, the dictionary starts with a small internal array (probably size=3) and increases it frequently. Since there are multiple threads trying to add elements to the dictionary, there's a great chance of different threads trying to Resize() the dictionary at the same time. Since Dictionary is not thread-safe class, if two threads try to modify the same LinkedList at the same time, this could leave the LinkedList in an inconsistent state (that's a race condition - two threads modifying the same data, causing unpredictable results).

As explained in other answer, a race condition while modifying the LinkedList could put the LinkedList into an invalid state, which would explain the infinite loop occurring on the methods which iterate through the LinkedList (both FindEntry and Insert). The high cpu (each thread using 100% cpu) is explained by this infinite loop - if it was a deadlock the thread would be in a low-cpu state waiting for some locked resource.

Since we know the number of elements we could pre-initialize the dictionary with a larger size (like 1000000), to reduce the chances of a race condition. But that doesn't solve the issue - the best solution is still to use a thread-safe class (ConcurrentDictionary<T>).