Frank Bakker talks about software development: CacheDictionary for .Net 3.5, using ReaderWriterLockSlim ?

In my previous post I described how to create a thread safe data cache using PFX. PFX however is scheduled to be released as a part of the .Net framework 4.0 which means we will have to wait a while before we can use this in real world applications. That’s why I created an implementation using the generic Dictionary combined with a ReaderWriterLockSlim which are both available in .Net 3.5. today.

public class CacheDictionary
{
    ReaderWriterLockSlim _cacheLock = new ReaderWriterLockSlim();
    Dictionary> _cacheItemDictionary = new Dictionary>();
  
    public TValue Fetch(TKey key, Func producer)
    {
        LazyInit cacheItem;
        bool found;
  
        _cacheLock.EnterReadLock();
        try
        {
            found = _cacheItemDictionary.TryGetValue(key, out cacheItem);
        }
        finally
        {
            _cacheLock.ExitReadLock();
        }
  
        if (!found)
        {
            _cacheLock.EnterWriteLock();
            try
            {
                if (!_cacheItemDictionary.TryGetValue(key, out cacheItem))
                {
                    cacheItem = new LazyInit(producer);
                    _cacheItemDictionary.Add(key, cacheItem);
                }
            }
            finally
            {
                _cacheLock.ExitWriteLock();
            }
        }
  
        return cacheItem.Value;
    }
}

This Implementation uses the (thread safe version of) the double-check locking pattern. This code first checks if the item exists using only a read lock, and only if the item is not found it acquire a write lock. To be sure the item was not added in between it checks again and adds the new item if it is still not found. Assuming there will be a fairly large amount of cache hits compared to cache misses, this is (in theory) more efficient than exclusively locking the dictionary right away, because multiple readers can get items from the cache concurrently and we only block other threads if we need to add a new item.
Just like in my previous implementation, I did not want to keeping the cache locked while actually retrieving or creating the item that needs to be cached. In the PFX version I did this by using LazyInit, which will also be part of .Net 4.0 (They actually just renamed it to Lazy). Because I wanted the cache to work on .Net 3.5, I created my own implementation of LazyInit which is not as versatile and highly optimized as the .Net 4.0 version, but does the job and is actually quite simple (see code below). While the cache-wide write lock is held, all I do is create an instance of LazyInit and store that instance in the dictionary. After the cache-wide lock is released I call LazyInit.Value which will actually call the delegate to create the item as needed. LazyInit uses a lock as well, but each instance has it’s own lock object, this way each instance will be initialized exactly once, but different items can be initialized concurrently.

public class LazyInit
{
    Func _producer;
    object _lock = new object();
    T _data;
    volatile bool _created;
  
    public LazyInit(Func producer)
    {
        _producer = producer;
    }
  
    public T Value
    {
        get
        {
            if (!_created)
            {
                lock (_lock)
                {
                    if (!_created)
                    {
                        _data = _producer.Invoke();
                        _created = true;
                        _producer = null;
                    }
                }
            }
            return _data;
        }
    }
}

Actually being quite happy with this implementation which does a minimum of locking while still being thread safe I sat back and relaxed.
Only A short time after I created this implementation, a blog post by Joe Duffy, the Lead developer / Architect behind PFX, showed up in my feed reader:

Reader/writer locks and their (lack of) applicability to fine-grained synchronization

In this post Joe compares the ReaderWriterLockSlim to (among others) a normal Mutex better known as the C# lock() statement. On a 4 core machine, when there are mostly readers and only a few writers, the reader/writer lock should theoretically be about 4 times as fast as the mutex. The reader / writer lock will allow multiple reader to execute concurrent on all four cores and the mutex only allows one thread to execute at a time leaving 3 cores idle while the other is holding the lock.
As it turns out, the mutex outperforms the ReaderWriterLockSlim in many scenario’s, especially in those cases where the locks are held for a relatively short time (like in a single peek in a dictionary). In stead of being 4 times faster the ReaderWriterLockSlim is actually about half as fast as the mutex! It seems that the internal book-keeping that needs to be done by the ReaderWriterLockSlim is way more expensive than the penalty of 3 cores being idle for a short time while 1 thread is holding the lock. Even Joe’s experimental highly optimized spinning ReaderWriterLock does not do a much better job in these scenario’s
ReaderWriterLockSlim start to outperform the mutex when the lock needs to be kept for a longer time (which you should generally avoid anyway). The number of cores will probably influence the results as well, I think running the same test on a 256 core box will increase the performance of the reader writer lock compared to the mutex, but unfortunately I have not been able to test this.
To test how this influenced my CacheDictionary, I created yet another implementation using a mutex in stead of the reader writer lock. Compared to the ReaderWriterLockSlim version this code is actually quite simple because it does not need to do the double check locking and the lock() statement does not require an explicit finally block. I did stick to the LazyInit aproach the avoid locking the whole cache while creating the items to cache.

public class CacheDictionary
{
    object _cacheLock = new object();
    Dictionary> _cacheItemDictionary = new Dictionary>();
  
    public TValue Fetch(TKey key, Func producer)
    {
        LazyInit cacheItem;
  
        lock (_cacheLock)
        {
            if (!_cacheItemDictionary.TryGetValue(key, out cacheItem))
            {
                cacheItem = new LazyInit(producer);
                _cacheItemDictionary.Add(key, cacheItem);
            }
        }
        return cacheItem.Value;
    }
}

I ran some simple performance test on my dual core machine to compare this code to the ReaderWriterLockSlim version. My results were similar to Joe’s, the version with the Mutex is way faster then ReaderWriterLockSlim, even when there are only readers and not a single writer! The actual results depend on a lit of factors, like the number of items in the dictionary and of course the amount of work that is done in the delegate that produces the cache item, but in general the reader/writer version took about 1.5 times as long on the same scenario as the Mutex version. As in many cases: Simplicity wins!
For the near future, I will stay away from reader writer locks unless it is absolutely necessary to hold a lock for a fair amount of time. Maybe I will revisit this statement when commodity hardware reaches 32 or 64 cores.
Joe Duffy concludes his post on this topic with: “Sharing is evil, fundamentally limits scalability, and is best avoided.” While in general I think he is right, the whole point of a cache is to share the result of a previous request with future requests in order to improve performance. Since caching implies sharing you should always be aware of the concurrency issues involved, that is why I tried to handle most of these issues in this generic utility.

Frank Bakker talks about software development

Sunday, March 15, 2009

CacheDictionary for .Net 3.5, using ReaderWriterLockSlim ?

Reader/writer locks and their (lack of) applicability to fine-grained synchronization

No comments:

Post a Comment