Double checked locking on Dictionary "ContainsKey"

Question

My team is currently debating this issue.

The code in question is something along the lines of

if (!myDictionary.ContainsKey(key))
{
    lock (_SyncObject)
    {
        if (!myDictionary.ContainsKey(key))
        {
            myDictionary.Add(key,value);
        }
    }
}

Some of the posts I've seen say that this may be a big NO NO (when using TryGetValue). Yet members of our team say it is ok since "ContainsKey" does not iterate on the key collection but checks if the key is contained via the hash code in O(1). Hence they claim there is no danger here.

I would like to get your honest opinions regarding this issue.

Cattier

you may want to check out ConcurrentDictionary. – Calen

Just a detail but you probably mean !ContainsKey() – Alderman

Have you found efficiency problems from locking the whole dictionary? – Deodorize

the dictionary will be used as a static cache. so this check is do for each instance creation. so thats a lot of locking... – Cattier

But have you actually found any efficiency problems? It's sometimes better not to worry about problems until they occur. – Deodorize

Answer 1

Don't do this. It's not safe.

You could be calling ContainsKey from one thread while another thread calls Add. That's simply not supported by Dictionary<TKey, TValue>. If Add needs to reallocate buckets etc, I can imagine you could get some very strange results, or an exception. It may have been written in such a way that you don't see any nasty effects, but I wouldn't like to rely on it.

It's one thing using double-checked locking for simple reads/writes to a field, although I'd still argue against it - it's another to make calls to an API which has been explicitly described as not being safe for multiple concurrent calls.

If you're on .NET 4, ConcurrentDictionary is probably the way forward. Otherwise, just lock on every access.

Govea

What if this code is accessed a lot within the application? Then that might be a performance issue. Any other way to do this besides ConcurrentDictionary? – Cattier

@Amir: I'd rather suffer a tiny amount of performance loss than have the application blow up. Have you profiled the application to see whether this is causing an actual performance issue? Uncontested locks are cheap: don't start trying to roll your own lock-free code without proving that you really need it. – Govea

Am i correct to assume that if i go with a lock on access instead of DCL then i will need to lock every access in every method to this dictionary? – Cattier

@Amir: Yes. You could potentially use ReaderWriterLockSlim to allow concurrent readers, but I'd just try locking on every access first, and profile your application to see whether it's a problem. – Govea

Sadly there are side-effects. If another thread calls Add while you check for ContainsKey there's a good chance the code checking for key will enter a loop and your application will hang. – Invitation

We just had this happen with the side effect of high CPU and possibly failed requests. Here's a nice post that explains in more detail: blogs.msdn.microsoft.com/tess/2009/12/21/… – Massimo

@Cattier "What if this code is accessed a lot within the application?" - I added a possible solution for low write volume scenarios below :) – Ciliary

Answer 2

If you are in a multithreaded environment, you may prefer to look at using a ConcurrentDictionary. I blogged about it a couple of months ago, you might find the article useful: http://colinmackay.co.uk/blog/2011/03/24/parallelisation-in-net-4-0-the-concurrent-dictionary/

Zygophyllaceous

What is an ample solution to this issue if using .Net 4.0 is not an option? (using 3.5) – Cattier

Good alternative and article but it doesn't actually answer whether the proposed locking is "OK". – Kissinger

Answer 3

This code is incorrect. The Dictionary<TKey, TValue> type does not support simultaneous read and write operations. Even though your Add method is called within the lock the ContainsKey is not. Hence it easily allows for a violation of the simultaneous read / write rule and will lead to corruption in your instance

Tumbler

Answer 4

It doesn't look thread-safe, but it would probably be hard to make it fail.

The iteration vs hash lookup argument doesn't hold, there could be a hash-collision for instance.

Alderman

Answer 5

If this dictionary is rarely written and often read, then I often employ safe double locking by replacing the entire dictionary on write. This is particularly effective if you can batch writes together to make them less frequent.

For example, this is a cut down version of a method we use that tries to get a schema object associated with a type, and if it can't, then it goes ahead and creates schema objects for all the types it finds in the same assembly as the specified type to minimize the number of times the entire dictionary has to be copied:

    public static Schema GetSchema(Type type)
    {
        if (_schemaLookup.TryGetValue(type, out Schema schema))
            return schema;

        lock (_syncRoot) {
            if (_schemaLookup.TryGetValue(type, out schema))
                return schema;

            var newLookup = new Dictionary<Type, Schema>(_schemaLookup);

            foreach (var t in type.Assembly.GetTypes()) {
                var newSchema = new Schema(t);
                newLookup.Add(t, newSchema);
            }

            _schemaLookup = newLookup;

            return _schemaLookup[type];
        }
    }

So the dictionary in this case will be rebuilt, at most, as many times as there are assemblies with types that need schemas. For the rest of the application lifetime the dictionary accesses will be lock-free. The dictionary copy becomes a one-time initialization cost of the assembly. The dictionary swap is thread-safe because pointer writes are atomic so the whole reference gets switched at once.

You can apply similar principles in other situations as well.

Ciliary