Using lock on the key of a Dictionary<string, object>

Question

I have a Dictionary<string, someobject>.

EDIT: It was pointed out to me, that my example was bad. My whole intention was not to update the references in a loop but to update different values based on differnt threads need to update/get the data. I changed the loop to a method.

I need to update items in my dictionary - one key at a time and i was wondering if there are any problems in using the lock on the .key value of my Dictionary object?

private static Dictionary<string, MatrixElement> matrixElements = new Dictionary<string, MatrixElement>();

//Pseudo-code

public static void UpdateValue(string key)
{
    KeyValuePair<string, MatrixElement> keyValuePair = matrixElements[key];
    lock (keyValuePair.Key)
    {
        keyValuePair.Value  = SomeMeanMethod();
    }
}

Would that hold up in court or fail? I just want each value in the dictionary to be locked independantly so locking (and updating) one value does not lock the others. Also i'm aware the locking will be holding for a long time - but the data will be invalid untill updated fully.

Answer 1

No, this would not work.

The reason is string interning. This means that:

string a = "Something";
string b = "Something";

are both the same object! Therefore, you should never lock on strings because if some other part of the program (e.g. another instance of this same object) also wants to lock on the same string, you could accidentally create lock contention where there is no need for it; possibly even a deadlock.

Feel free to do this with non-strings, though. For best clarity, I make it a personal habit to always create a separate lock object:

class Something
{
    bool threadSafeBool = true;
    object threadSafeBoolLock = new object(); // Always lock this to use threadSafeBool
}

I recommend you do the same. Create a Dictionary with the lock objects for every matrix cell. Then, lock these objects when needed.

PS. Changing the collection you are iterating over is not considered very nice. It will even throw an exception with most collection types. Try to refactor this - e.g. iterate over a list of keys, if it will always be constant, not the pairs.

Answer 2

Locking on an object that is accessible outside of the code locking it is a big risk. If any other code (anywhere) ever locks that object you could be in for some deadlocks that are hard to debug. Also note that you lock the object, not the reference, so if I gave you a dictionary, I may still hold references to the keys and lock on them - causing us to lock on the same object.

If you completely encapsulate the dictionary, and generate the keys yourself (they aren't ever passed in, then you may be safe.

However, try to stick to one rule - limit the visibility of the objects you lock on to the locking code itself whenever possible.

That's why you see this:

public class Something
{
  private readonly object lockObj = new object();

  public SomethingReentrant()
  {
    lock(lockObj)    // Line A
    {
      // ...
     }
   }
}

rather than seeing line A above replaced by

  lock(this)

That way, a separate object is locked on, and the visibility is limited.

Edit Jon Skeet correctly observed that lockObj above should be readonly.

Answer 3

In your example, you can not do what you want to do!

You will get a System.InvalidOperationException with a message of Collection was modified; enumeration operation may not execute.

Here is an example to prove:

using System.Collections.Generic;
using System;

public class Test
{
    private Int32 age = 42;

    static public void Main()
    {
       (new Test()).TestMethod();
    }

    public void TestMethod()
    {
        Dictionary<Int32, string> myDict = new Dictionary<Int32, string>();

        myDict[age] = age.ToString();

        foreach(KeyValuePair<Int32, string> pair in myDict)
        {
            Console.WriteLine("{0} : {1}", pair.Key, pair.Value);
            ++age;
            Console.WriteLine("{0} : {1}", pair.Key, pair.Value);
            myDict[pair.Key] = "new";
            Console.WriteLine("Changed!");
        }
    }   
}

The output would be:

42 : 42
42 : 42

Unhandled Exception: System.InvalidOperationException: Collection was modified; enumeration operation may not execute.
   at System.ThrowHelper.ThrowInvalidOperationException(ExceptionResource resource)
   at System.Collections.Generic.Dictionary`2.Enumerator.MoveNext()
   at Test.TestMethod()
   at Test.Main()

Answer 4

I can see a few potential issues there:
1. strings can be shared, so you don't necesarily know who else might be locking on that key object for what other reason
2. strings might not be shared: you may be locking on one string key with the value "Key1" and some other piece of code may have a different string object that also contains the characters "Key1". To the dictionary they're the same key but as far as locking is concenrned they are different objects.
3. That locking won't prevent changes to the value objects themselves, i.e. matrixElements[someKey].ChangeAllYourContents()

Answer 5

Note: I assume exception when modifying collection during iteration is already fixed

Dictionary is not thread-safe collection, which means it is not safe to modify and read collection from different threads without external synchronization. Hashtable is (was?) thread-safe for one-writer-many-readers scenario, but Dictionary has different internal data structure and doesn't inherit this guarantee.

This means that you cannot modify your dictionary while you accessing it for read or write from the other thread, it can just broke internal data structures. Locking on the key doesn't protect internal data structure, because while you modify that very key someone could be reading different key of your dictionary in another thread. Even if you can guarantee that all your keys are same objects (like said about string interning), this doesn't bring you on safe side. Example:

1. You lock the key and begin to modify dictionary
2. Another thread attempts to get value for the key which happens to fall into the same bucket as locked one. This is not only when hashcodes of two objects are the same, but more frequently when hashcode%tableSize is the same.
3. Both threads are accessing the same bucket (linked list of keys with same hashcode%tableSize value)

If there is no such key in dictionary, first thread will start modifying the list, and the second thread will likely to read incomplete state.

If such key already exists, implementation details of dictionary could still modify data structure, for example move recently accessed keys to the head of the list for faster retrieval. You cannot rely on implementation details.

There are many cases like that, when you will have corrupted dictionary. So you have to have external synchronization object (or use Dictionary itself, if it is not exposed to public) and lock on it during entire operation. If you need more granular locks when operation can take some long time, you can copy keys you need to update, iterate over it, lock entire dictionary during single key update (don't forget to verify key is still there) and release it to let other threads run.

Answer 6

If I'm not mistaken, the original intention was to lock on a single element, rather than locking the whole dictionary (like table-level lock vs. row level lock in a DB)

you can't lock on the dictionary's key as many here explained.

What you can do, is to keep an internal dictionary of lock objects, that corresponds to the actual dictionary. So when you'd want to write to YourDictionary[Key1], you'll first lock on InternalLocksDictionary[Key1] - so only a single thread will write to YourDictionary.

a (not too clean) example can be found here: http://www.kenegozi.com/Blog/2008/08/24/keylevel-locked-cache-real-life-implementation.aspx