The Importance of Being Immutable

18 Nov 2013

What good is immutability? If you've spent any time looking into functional programming you'll know that FP advocates can't stop talking about how great immutability is, but perhaps you haven't really seen it in action. I hope to demonstrate one way in which programming in a functional style can lead to lower latency in multi-threaded code.

Thread Safety

Now, I'm sure I'm going to sound like I'm just punting on this one, but the truth is that using immutability can create much lower latency programs than similar multi-threaded programs using imperative features. One of the things that I am tempted to do too often is the following:

public class Cache<TKey, TValue>
{
    private readonly IDictionary<TKey, TValue> _cache
        = new Dictionary<TKey, TValue>();
    
    public TValue Get(TKey key, Func<TValue> func)
    {
        TValue val;
        bool found;
        
        lock (_cache)
        {
            found = _cache.TryGetValue(key, out val);
        }
        
        if (!found)
        {
            val = func();
            
            lock (_cache)
            {
                _cache[key] = val;
            }
        }
        
        return val;
    }
}

This code is thread-safe but it has one major drawback because only one thread can be reading from the cache at a time. This may cause an immense amount of contention, slowing the application down. An alternative with less contention uses a reader/writer lock:

public class Cache<TKey, TValue>
{
    private readonly ReaderWriterLockSlim _lock
        = new ReaderWriterLockSlim(LockRecursionPolicy.NoRecursion);
    private readonly IDictionary<TKey, TValue> _cache
        = new Dictionary<TKey, TValue>();
    
    public TValue Get(TKey key, Func<TValue> func)
    {
        TValue val;
        
        _lock.EnterReadLock();
        var found = _cache.TryGetValue(key, out val);
        _lock.ExitReadLock();
        
        if (!found)
        {
            val = func();
            
            _lock.EnterWriteLock();
            _cache[key] = val;
            _lock.ExitWriteLock();
        }
        
        return val;
    }
}

This reader/writer lock allows any number of readers simultaneously as long as there are no writers. This works much better if you are getting a lot of cache hits. The premise is that most dictionaries will be thread safe to read from any number of times. The real trouble begins when a key is not found. A much more expensive lock has to be acquired that locks all readers out while the new key is inserted. This code may be fine for most use cases, but it's still missing out on what immutability can do to the code:

public class Cache<TKey, TValue>
{
    private readonly object _lock = new Object();
    private volatile IPersistentDictionary<TKey, TValue> _cache
        = new PersistentDictionary<TKey, TValue>();
    
    public TValue Get(TKey key, Func<TValue> func)
    {
        TValue val;
        var found = _cache.TryGetValue(key, out val);
        
        if (!found)
        {
            val = func();
            
            lock (_lock)
            {
                _cache = _cache.Add(key, val);
            }
        }
        
        return val;
    }
}

This example is not part of the standard library, so it may take some more explaining. The persistent dictionary is an interface I am using to show that the dictionary never changes, but we can create a new copy with a given key/value pair. I'm also taking advantage of the C# memory model that guarantees that a write to an object reference field will complete atomically, so we don't have to lock to set a single variable.

The result is somewhat subtle, but if you look at the code, you'll notice that I never have to lock if I get a cache hit (hopefully this is happening often). The net effect is that even when there are cache misses, a cache hit will be allowed to proceed, allowing your application to remain responsive.

There is still some low-hanging fruit in terms of double-checked locking to verify that the previous attempt did not already fill a slot, but I've applied similar optimizations to every incarnation of this cache, and I think it is apparent how one could see much lower latency in the immutable case.

Addendum

People on Reddit have kindly pointed out that this is less than optimal. A more efficient mechanism would work something like this:

public class Cache<TKey, TValue>
{
    private readonly object _lock = new Object();
    private volatile IPersistentDictionary<TKey, Lazy<TValue>> _cache
        = new PersistentDictionary<TKey, Lazy<TValue>>();
    
    public TValue Get(TKey key, Func<TValue> func)
    {
        Lazy<TValue> val;

        if (!_cache.TryGetValue(key, out val))
        {
            lock (_lock)
            {
                if (!_cache.TryGetValue(key, out val))
                {
                    val = new Lazy<TValue>(func);
                    _cache = _cache.Add(key, val);
                }
            }
        }
        
        return val.Value;
    }
}

Thanks, honorable denizens of Reddit!