Is a Dictionary<K,V> thread safe for simulataneous reading and additions?

Question

There question relates to a very specific and common scenario in which a dictionary is being used for on-demand caching of items in a multi-threaded environment. To avoid thread locking it's preferable to test for an existing cache item outside of a sync lock, but if we subsequently have to add an item then that counts as a write to the dictionary and therefore most advice I've been reading on stackoverflow is that you need to lock on the read as well as the write because the dictionary's internal state might be being altered by the calls to add().

However, looking through Microsoft's AjaxControlToolkit (scriptObjectBuilder class) the code does in fact perform TryGet() outside of any locks and only locks to Add() new items to the dictionary. I can see how this might be possible if the bucket that an item is placed into never changes once added, but my suspicion is that this is wrong and might be a source of bugs.

Thanks.

UPDATE Going by the .Net documentation I think that the described pattern is indeed wrong. However I was wondering if the particular implementation of Dictionary allows it and that the AjaxControlToolkit was relying on this(which would be dubious). On examining the code in Reflector I'm pretty sure that this is indeed wrong, the Dictionary.Resize() method reallocates the number of buckets and moves bucket items around, so any thread in teh middle of a TryGet() could potentially be working with on unstable data.

UPDATE A defect was already logged against the AjaxControlToolkit on codeplex. See:

• Possible Thread Safety bug in ScriptObjectBuilder
• Thread safety issue in ScriptObjectBuilder.

Answer 1

Tess Ferrandez has an excellent blog post about threading issues with generic dictionaries:

the FindEntry method walks through the dictionary, trying to find the key. If multiple threads are doing this at the same time, especially if the dictionary is modified in the meantime you may end up in an infinite loop in FindEntry causing the high CPU behavior and the process may hang.

Answer 2

I would say this is definitely a bug in the AjaxControlToolkit, and would recommend you raise a bug on CodePlex. It should be using a ReaderWriteLock(Slim).

Answer 3

To answer my own question following some investingation: On examining the code for Dictionary I can see that the Dictionary.Resize() method reallocates the number of internal buckets that are used for storing data, and redistributes the bucket contents so that items are in the correct bucket based on their hashcode. As such any thread in the middle of a TryGet() risks working on unstable data.

As an aside, a possible low-locking approach for a Dictionary class might be to place a lock arounf just the Resize() method.