8

Consider the following code:

Dictionary<string, string> list = new Dictionary<string, string>();
object lockObj = new object();

public void MyMethod(string a) {

    if (list.Contains(a))
        return;

    lock (lockObj) {
        list.Add(a,"someothervalue");
    }
}

Assuming I'm calling MyMethod("mystring") from different threads concurrently.

Would it be possible for more than one thread (we'll just take it as two) enter the if (!list.Contains(a)) statement in the same time (with a few CPU cycles differences), both threads get evaluated as false and one thread enters the critical region while another gets locked outside, so the second thread enters and add "mystring" to the list again after the first thread exits, resulting in the dictionary trying to add a duplicate key?

4
  • 13
    Calling a dictionary list is really mean. It gives the impression that it's a list, rather than a dictionary. Commented Oct 24, 2013 at 14:11
  • @Servy I named my dog "cat" though. Was that mean too? Commented Oct 24, 2013 at 20:37
  • @Cruncher No, because cats are awesome. Commented Oct 24, 2013 at 20:46
  • @Servy So what you're saying is that you don't like lists? Commented Oct 24, 2013 at 20:47

7 Answers 7

18

No, it's not thread-safe. You need the lock around the list.Contains too as it is possible for a thread to be switched out and back in again between the the if test and adding the data. Another thread may have added data in the meantime.

Sign up to request clarification or add additional context in comments.

Comments

11

You need to lock the entire operation (check and add) or multiple threads may attempt to add the same value.

Thread Timeline

I would recommend using the ConcurrentDictionary(TKey, TValue) since it is designed to be thread safe.

private readonly ConcurrentDictionary<string, string> _items
    = new ConcurrentDictionary<string, string>();

public void MyMethod(string item, string value)
{
    _items.AddOrUpdate(item, value, (i, v) => value);
}

2 Comments

I believe your diagram is wrong. You need to move Thread 2's acquire lock after thread 1 has added the item.
I should have worded it, "Attempt to Acquire Lock." T1 will acquire the lock and T2 will be blocked until T1 leaves the lock.
1

You need to lock around the whole statement. It's possible for you to run into issues on the .Contains portion (the way your code is now)

Comments

1

You should check the list after locking. e.g.

if (list.Contains(a))
return;

    lock (lockObj) {
       if (list.Contains(a))
         return;
       list.Add(a);
    }
}

3 Comments

the problem with this is that microsoft do not guarantee that the list.Contains method will work if another thread is modifiying the collection
This doesn't seem 100% safe. Another thread could be writing to the list as the Contains() in the locked region is being evaluated.
1
private Dictionary<string, string> list = new Dictionary<string, string>();

public void MyMethod(string a) {
   lock (list) {
      if (list.Contains(a))
        return;
      list.Add(a,"someothervalue");
    }
}

Check out this guide to locking, it's good

A few guidelines to bear in mind

  1. Generally lock around a private static object when locking on multiple writeable values
  2. Do not lock on things with scope outside the class or local method such as lock(this), which could lead to deadlocks!
  3. You may lock on the object being changed if it is the only concurrently accessed object
  4. Ensure the object you lock is not null!
  5. You can only lock on reference types

Comments

0

I am going to assume that you meant write ContainsKey instead of Contains. Contains on a Dictionary is explicitly implemented so it is not accessible via the type you declared.1

Your code is not safe. The reason is because there is nothing preventing ContainsKey and Add from executing at the same time. There are actually some quite remarkable failure scenarios that this would introduce. Because I looked at how the Dictionary is implemented I can see that your code could cause a situation where data structure contains duplicates. And I mean it literally contains duplicates. The exception will not necessarily be thrown. The other failure scenarios just keep getting stranger and stranger, but I will not go into those here.

One trivial modification to your code might involve a variation of the double-checked locking pattern.

public void MyMethod(string a) 
{
  if (!dictionary.ContainsKey(a))
  {
    lock (dictionary)
    {
      if (!dictionary.ContainsKey(a))
      {
        dictionary.Add(a, "someothervalue");
      }
    }
  }
}

This, of course, is not any safer for the reason I already stated. Actually, the double-checked locking pattern is notoriously difficult to get right in all but the simplest cases (like the canonical implementation of a singleton). There are many variations on this theme. You can try it with TryGetValue or the default indexer, but ultimately all of these variations are just dead wrong.

So how could this be done correctly without taking a lock? You could try ConcurrentDictionary. It has the method GetOrAdd which is really useful in these scenarios. Your code would look like this.

public void MyMethod(string a) 
{
  // The variable 'dictionary' is a ConcurrentDictionary.
  dictionary.GetOrAdd(a, "someothervalue");
}

That is all there is to it. The GetOrAdd function will check to see if the item exists. If it does not then it will be added. Otherwise, it will leave the data structure alone. This is all done in a thread-safe manner. In most cases the ConcurrentDictionary does this without waiting on a lock.2


1By the way, your variable name is obnoxious too. If it were not for Servy's comment I may have missed the fact that we were talking about a Dictionary as opposed to a List. In fact, based on the Contains call I first thought we were talking about a List.

2On the ConcurrentDictionary readers are completely lock free. However, writers always take a lock (adds and updates that is; the remove operation is still lock free). This includes the GetOrAdd function. The difference is that the data structure maintains several possible lock options so in most cases there is little or no lock contention. That is why this data structure is said to be "low lock" or "concurrent" as opposed to "lock free".

2 Comments

Oddly, the overload of GetOrAdd that accepts a factory delegate will attempt a lockless TryGetValue before acquiring the write lock. The non-delegate overload, however, does not - so prefer the former for high-concurrency scenarios blog.basildoncoder.com/2014/01/…
@Russ: Good point. I've noticed other oddities with the ConcurrentDictionary as well. For example, AddOrUpdate can execute the factory delegate more than once, but GetOrAdd will not.
-2

You can first do a non-locking check, but if you want to be thread-safe you need to repeat the check again within the lock. This way you don't lock unless you have to and ensure thread safety.

Dictionary<string, string> list = new Dictionary<string, string>();
object lockObj = new object();

public void MyMethod(string a) {

    if (list.Contains(a))
        return;

    lock (lockObj) {
       if (!list.Contains(a)){
        list.Add(a,"someothervalue");
       }
    }
}

2 Comments

This is not safe. Contains and Add could still execute simultaneously.
Yes, but does that cause any inconsistency problems?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.