How to show that the double-checked-lock pattern with Dictionary's TryGetValue is not threadsafe

Clearly the code is not threadsafe. What we have here is a clear case of the hazards of premature optimization.

Remember, the purpose of the double-checked locking pattern is to improve the performance of code by eliminating the cost of the lock. If the lock is uncontested it is incredibly cheap already. Therefore, the double-checked locking pattern is justified only in the cases (1) where the lock is going to be heavily contested, or (2) where the code is so incredibly performance-sensitive that the cost of an unconstested lock is still too high.

Clearly we are not in the second case. You're using a dictionary for heaven's sake. Even without the lock it will be doing lookups and comparisons that will be hundreds or thousands of times more expensive than the savings of avoiding an uncontested lock.

If we are in the first case then figure out what is causing the contention and eliminate that. If you're doing a lot of waiting around on a lock then figure out why that is and replace the locking with a slim reader-writer-lock or restructure the application so that not so many threads are banging on the same lock at the same time.

In either case there is no justification for doing dangerous, implementation-sensitive low-lock techniques. You should only be using low-lock techniques in those incredibly rare cases where you really, truly cannot take the cost of an uncontested lock.

In this example, exception #1 is thrown almost instantly on my machine:

var dict = new Dictionary<int, string>() { { 1234, "OK" } };new Thread(() =>{    for (; ; )    {        string s;        if (!dict.TryGetValue(1234, out s))        {            throw new Exception();  // #1        }        else if (s != "OK")        {            throw new Exception();  // #2        }    }}).Start();Thread.Sleep(1000);Random r = new Random();for (; ; ){    int k;    do { k = r.Next(); } while (k == 1234);    Debug.Assert(k != 1234);    dict[k] = "FAIL";}

However, the exact behaviour of code that is not designed to be thread-safe is unpredictable.
You cannot rely on it. So the double-checking code is indeed broken.

I'm not sure if I'd unit test this, though, as testing concurrent code (and getting it right) is much more complicated than writing the concurrent code in the first place.

I don't really think that you need to prove this, you just need to refer people to the documentation for Dictionary<TKey, TValue>:

A Dictionary can support multiple readers concurrently, as long as the collection is not modified. Even so, enumerating through a collection is intrinsically not a thread-safe procedure. In the rare case where an enumeration contends with write accesses, the collection must be locked during the entire enumeration. To allow the collection to be accessed by multiple threads for reading and writing, you must implement your own synchronization.

It's actually a well-known fact (or should be) that you cannot read from a dictionary while another thread is writing to it. I've seen a few "bizarre multi-threading issue" kinds of questions here on SO where it turned out that the author didn't realize that this wasn't safe.

The problem isn't specifically related to double-checked locking, it's just that the dictionary is not a thread-safe class, not even for a single-writer/single-reader scenario.

I'll go one step further and show you why, in Reflector, this isn't thread-safe:

private int FindEntry(TKey key){    // Snip a bunch of code    for (int i = this.buckets[num % this.buckets.Length]; i >= 0;        i = this.entries[i].next)    // Snip a bunch more code}private void Resize(){    int prime = HashHelpers.GetPrime(this.count * 2);    int[] numArray = new int[prime];    // Snip a whole lot of code    this.buckets = numArray;}

Look at what can happen if the Resize method happens to be running while even one reader calls FindEntry:

1. Thread A: Adds an element, resulting in a dynamic resize;
2. Thread B: Calculates the bucket offset as (hash code % bucket count);
3. Thread A: Changes the buckets to have a different (prime) size;
4. Thread B: Chooses an element index from the new bucket array at the old bucket index;
5. Thread B's pointer is no longer valid.

And this is exactly what fails in dtb's example. Thread A searches for a key that is known in advance to be in the dictionary, and yet it isn't found. Why? Because the FindValue method picked what it thought was the correct bucket, but before it even had a chance to look inside, Thread B changed the buckets, and now Thread A is looking in some totally random bucket that does not contain or even lead to the right entry.

Moral of the story: TryGetValue is not an atomic operation, and Dictionary<TKey, TValue> is not a thread-safe class. It's not just concurrent writes you need to worry about; you can't have concurrent read-writes either.

In reality the problem actually runs a lot deeper than this, due to instruction reordering by the jitter and CPU, stale caches, etc. - there are no memory barriers whatsoever being used here - but this should prove beyond a doubt that there's an obvious race condition if you have an Add invocation running at the same time as a TryGetValue invocation.