Can I get rid of this read lock?

Question

I have the following helper class (simplified):

public static class Cache
{
    private static readonly object _syncRoot = new object();
    private static Dictionary<Type, string> _lookup = new Dictionary<Type, string>();

    public static void Add(Type type, string value)
    {
        lock (_syncRoot)
        {
            _lookup.Add(type, value);
        }
    }

    public static string Lookup(Type type)
    {
        string result;

        lock (_syncRoot)
        {
            _lookup.TryGetValue(type, out result);
        }

        return result;
    }
}

Add will be called roughly 10/100 times in the application and Lookup will be called by many threads, many of thousands of times. What I would like is to get rid of the read lock.

How do you normally get rid of the read lock in this situation?

I have the following ideas:

1. Require that _lookup is stable before the application starts operation. The could be build up from an Attribute. This is done automatically through the static constructor the attribute is assigned to. Requiring the above would require me to go through all types that could have the attribute and calling RuntimeHelpers.RunClassConstructor which is an expensive operation;

2. Move to COW semantics.

   public static void Add(Type type, string value)
   {
       lock (_syncRoot)
       {
           var lookup = new Dictionary<Type, string>(_lookup);
   
           lookup.Add(type, value);
   
           _lookup = lookup;
       }
   }
   

   (With the lock (_syncRoot) removed in the Lookup method.) The problem with this is that this uses an unnecessary amount of memory (which might not be a problem) and I would probably make _lookup volatile, but I'm not sure how this should be applied. (John Skeets' comment here gives me pause.)

3. Using ReaderWriterLock. I believe this would make things worse since the region being locked is small.

Suggestions are very welcome.

UPDATE:

The values of the cache are immutable.

Answer 1

To remove locks completely (slightly differnt then "lock free" where locks almost eliminated and remaining are cleverly replaced with Interlocked instructions) you need to make sure that your dictionary is immutable. If items in the dictionary are not immutable (and as result have they own locks) you probably should not worry about locking on dictionary level.

1. is the best and easiest solution if you can use it.
2. reasonable and easy to debug. (Note: as written it does not work well for concurrent adding of the same item. Conside double checking locking pattern if needed - Double-checked locking in .NET)
3. I would not do it if 1/2 is an option.

If you can use new 4.0 collections - ConcurrentDictionary there matches your criteria (see http://msdn.microsoft.com/en-us/library/dd997305.aspx and http://blogs.msdn.com/b/pfxteam/archive/2010/01/26/9953725.aspx).

Answer 2

At work at the moment, so nothing elegant, came up with this (untested)

public static class Cache
{
    private static readonly object _syncRoot = new object();
    private static Dictionary<Type, string> _lookup = new Dictionary<Type, string>();

    public static class OneToManyLocker
    {
        private static readonly Object WriteLocker = new Object();
        private static readonly List<Object> ReadLockers = new List<Object>();
        private static readonly Object myLocker = new Object();

        public static Object GetLock(LockType lockType)
        {
            lock(WriteLocker)
            {
                if(lockType == LockType.Read)
                {
                    var newReadLocker = new Object();
                    lock(myLocker)
                    {
                        ReadLockers.Add(newReadLocker);
                    }
                    return newReadLocker;
                }

                foreach(var readLocker in ReadLockers)
                {
                    lock(readLocker) { }
                }

                return WriteLocker;
            }
        }

        public enum LockType {Read, Write};
    }

    public static void Add(Type type, string value)
    {
        lock(OneToManyLocker.GetLock(OneToManyLocker.LockType.Write))
        {
            _lookup.Add(type, value);
        }
    }

    public static string Lookup(Type type)
    {
        string result;
        lock (OneToManyLocker.GetLock(OneToManyLocker.LockType.Read))
        {
            _lookup.TryGetValue(type, out result);      
        }

        return result;
    }
}

You will need some sort of cleanup for the read lockers, but should be threadsafe allowing multiple reads at a time while also locking on writes, unless I'm totally missing something

Answer 3

Either:

• Dont use normal locks, go spinlock if the lookup is fast (dictionary is not).

• If that is not the case, then use http://msdn.microsoft.com/en-us/library/system.threading.readerwriterlock.aspx. This allows multiple readers and only one writer.