Immutable data structures and concurrency

Question

I'm trying to understand how using immutable data structures in concurrent programming can obviate the need for locking. I've read a few things on the web but haven't seen any concrete examples yet.

For example, let's say we have some code (C#) that uses lock(s) around a Dictionary< string, object> does this:

class Cache
{
    private readonly Dictionary<string, object> _cache = new Dictionary<string, object>();
    private readonly object _lock = new object();

    object Get(string key, Func<object> expensiveFn)
    {
        if (!_cache.ContainsKey("key"))
        {
            lock (_lock)
            {
                if (!_cache.ContainsKey("key"))
                    _cache["key"] = expensiveFn();
            }
        }
        return _cache["key"];
    }
}

How would that look if _cache was immutable? Would it be possible to remove the lock and also ensure expensiveFn isn't called more than once?

Answer 1

Short answer is that it doesn't, at least not completely.

Immutability only guarantees that another thread won't be able to modify the contents of your data structure while you are working with it. Once you have an instance, that instance can never be modified, so you will always be safe reading it. Any edits would require a copy of the instance to be made, but those copies wouldn't interfere directly with any instances already referenced.

There are still plenty of reasons why you would need locking and synchronization constructs in a multi-threaded application, even with immutable objects. They mostly deal with timing related problems, such as race conditions, or controlling thread flow so that activities happen at the right time. Immutable objects won't really do anything to help with these kinds of problems.

Immutability makes multi-threading easier, but it doesn't make it easy.

---

As far as your question about what an immutable dictionary would look like. I'd have to say that in most cases it doesn't really make much sense, in your example, to even use an immutable dictionary. Since it is being used as an "active" object that inherently changes as items are added and removed. Even in a language designed around immutability, like F#, there are mutable objects for this purpose. See this link for more details. The immutable versions can be found here.

Answer 2

The basic idea behind immutable data structures reducing (notice that I said "reducing," not "eliminating") the need for locking in concurrency is that every thread is working either on a local copy or against the immutable data structure so there's no need for locking (no thread can modify any other threads' data, just their own). Locking is only needed when several threads can modify the same mutable state at once because otherwise you have the possibility of "dirty reads" and other similar issues.