Reducing contention in thread-safe LruCache

Question

I was looking for a in-memory cache class, but couldn't find any in the .Net Core framework; luckily I found one already implemented here.

I made some minor modifications to it and tried to make it thread safe. I believe I succeeded; but boy, did I do a sloppy job? Just throwing locks around and whatnot.

I'd like to reduce thread contention and improve its performance. I considered using the ReadWriterLockSlim* class; one instances for the private dict and one for the private linked list.

Can someone help me improve the performance of this class?

For reference, at any given time there may be up to 40 threads hammering down this cache.

I can't provide a real and concise usage example of this class right now; and I have not yet measured the following numbers, but I expect that most 4/5 cache accesses will result in a hit, and 1/5 in a miss followed by an add.

An actual, yet codeless, example of usage of this class is to store the fitness of (immutable) individuals in a genetic algorithm. Since the individuals are immutable, their fitnesses stay the same as long as they live; thus I can compute it once and cache the result.

The most up-to-date version of the code can be found in my own answer; since I received such great feedback and couldn't choose a single answer as the answer, I decided to compile the suggestions, and post the resulting code, in a single new answer. This way I'm able to share the final result with the community, acknowledge the help and still keep the question / answers valid.

I won't accept my answer as "the answer" because I don't want to fragsteal.

namespace Minotaur.Collections {
using System;
using System.Collections.Generic;

/// <remarks>
/// This class is based on the following inplementation https://stackoverflow.com/a/3719378/1642116
/// </remarks>
public sealed class LruCache<K, V> {
    private readonly int _capacity;
    private readonly Dictionary<K, LinkedListNode<LRUCacheEntry<K, V>>> _cacheMap;
    private readonly LinkedList<LRUCacheEntry<K, V>> _lruList = new LinkedList<LRUCacheEntry<K, V>>();
    private readonly object _lock = new object();

    /// <remarks>
    /// Providing the value 0 to <paramref name="capacity"/>
    /// effectively disables the cache.
    /// </remarks>
    public LruCache(int capacity) {
        if (capacity < 0)
            throw new ArgumentOutOfRangeException(nameof(capacity) + " must be >= 0");

        this._capacity = capacity;
        this._cacheMap = new Dictionary<K, LinkedListNode<LRUCacheEntry<K, V>>>(capacity: capacity);
    }

    /// <remarks>
    /// This method is thread-safe.
    /// </remarks>
    public void Add(K key, V value) {
        if (key == null)
            throw new ArgumentNullException(nameof(key));

        lock (_lock) {
            if (_capacity == 0)
                return;

            if (_cacheMap.Count >= _capacity)
                RemoveLastRecentlyUsed();

            var cacheItem = new LRUCacheEntry<K, V>(key, value);
            var node = new LinkedListNode<LRUCacheEntry<K, V>>(cacheItem);
            _lruList.AddLast(node);
            _cacheMap.Add(key, node);
        }
    }

    /// <remarks>
    /// This method is thread-safe.
    /// </remarks>
    public bool TryGet(K key, out V value) {
        if (key == null)
            throw new ArgumentNullException(nameof(key));

        lock (_lock) {
            var isCached = _cacheMap.TryGetValue(key, out var node);

            if (!isCached) {
                value = default;
                return false;
            }

            // Updating the last recently used thingy
            _lruList.Remove(node);
            _lruList.AddLast(node);

            value = node.Value.Value;
            return true;
        }
    }

    private void RemoveLastRecentlyUsed() {
        // Remove from lru list
        var node = _lruList.First;
        _lruList.RemoveFirst();

        // Remove from cache
        _cacheMap.Remove(node.Value.Key);
    }

    private sealed class LRUCacheEntry<KeyType, ValueType> {
        public readonly KeyType Key;
        public readonly ValueType Value;

        public LRUCacheEntry(KeyType k, ValueType v) {
            Key = k;
            Value = v;
        }
    }
}

}

*then I remembered I don't really know how to use it correctly and would probably end up increasing contention...

Answer 1

..but I expect that most 4/5 cache accesses will result in a hit, and 1/5 in a miss followed by an add.

You are not exposing your sync root _lock, meaning this class isn't thread-safe for consumers. The only meaningful way to use your class is as follows:

if (!cache.TryGet(key, out var value))
{
    // watch out! one of the other threads may already have added the same value
    cache.Add(key, valueGenerator());
}

This would be a better approach:

lock (cache.SyncRoot) 
{
    if (!cache.TryGet(key, out var value))
    {
        cache.Add(key, valueGenerator());
    }
}

Even better would be to provide a GetOrAdd method:

var cachedResultRetrieved = cache.GetOrAdd(key, out var value, valueGenerator);

You may also argue whether using a global lock is the most efficient way of handling thread-safety here. I believe using ConcurrentDictionary would solve most threading issues. The only atomic operation I see is this one:

_lruList.Remove(node);
_lruList.AddLast(node);

This would still require some locking mechanism. I don't think it's that important that both the cache and the lrulist are updated in the same lock. It's not crucial that the exact oldest item gets deleted.

Answer 2

This is a neat little implementation. It's nice that LruCacheEntry is a private inner class. It does indeed look to be thread-safe in its current state.

---

When calling Add, if the key is already present, then a new node is added to LruList before the code crashes because the key is already present in the dictionary. This means you could end up with an ever growing LruList, which would be bad.

You should probably check if key is already present and decide what to do after that... you might want to replace the value, or do nothing, or... (consult dfhwze's answer)

---

Generally type-parmeters follow the pattern TName in .NET: in you case I would expect TKey and TValue. Whatever you do, you should be consistent between classes, but you'd be better off just removing <KeyType, ValueType>, since LRUCacheEntry already knows about K and V. LRUCacheEntry should be LruCacheEntry to be consistent with LruCache and the .NET naming conventions.

---

I would attach an else to if (!isCached) so that the control flow is clearer and the static checker can tell you when you accidently comment out return false.

---

I'm always glad to see inline documentation of the public (and private) API, but the comments here are really not very helpful.

Some of your comments could generally be better:

• Spelling error: "inplementation"

• "Thingy" is a tad vague

• It is not documented that null is an invalid key

• There is nothing explaining that it is a Least-Recently User eviction policy (Lru wouldn't cut it for me)

• I'd probably want a comment attached to the private method indicating the lock must be taken. An assert would be even better:

  Debug.Assert(Monitor.IsEntered(_lock));
  

---

As Henrik Hansen says, you can't really avoid a mutex with this implementation, but you may be able to reduce the amount of stuff that is inside the lock.

One possible option could be to use a ConcurrentDictionary, as dfhwze has suggested: when you try to get a value, you ask the dictionary. If it finds it, then you take the lock and update the linked list (you don't take a lock if it isn't present, and you hold the lock for less time): you need to check your node is still in the inked list, because it might been removed before you took the lock, because it may have been replaced already.

When adding, you perform a check (as mentioned above), and if a change needs to be made, you again take the lock, perform the check again, and perform the add (update the list and dictionary) inside the lock if you need to. All this effort may or may not reduce the time spent in the lock, and so the amount of contention.

Unless you use a linked-list designed for concurrent use, I don't think you are going to be able to avoid a mutex when modifying _lruList without fundamentally changing how the cache works.

Answer 3

/// <remarks>
/// Providing the value 0 to <paramref name="capacity"/>
/// effectively disables the cache.
/// </remarks>

_capacity is a private readonly field. I can't think of a situation where to instantiate an cache object with an immutable capacity set to 0 - hence useless, but you may have some idea with that?

---

  lock (_lock)
  {
    if (_capacity == 0)
      return;

As a consequence of the immutable _capacity initialized to 0, the above check doesn't have to be protected by the _lock because the cache will never change.

---

Because there is "heavy" manipulation of the cache in both Add(...) and TryGet(...), I don't see any benefits of trying to use a reader/writer lock, so I would keep the use of lock() here. But other reviewers may have a more detailed view on that.

---

You could consider to implement IEnumerable<T> or another iterator mechanism in order to make it possible to view the entire content of the cache.

Answer 4

Cosmetics

You can simplify your code by removing the generic arguments from LRUCacheEntry. Since it's a nested class it can use its parent class' types without redefining them. You could also make it a readonly struct and save a couple of instances.

private readonly struct LRUCacheEntry
{
    public readonly TKey Key;
    public readonly TValue Value;

    public LRUCacheEntry(TKey k, TValue v)
    {
        Key = k;
        Value = v;
    }

    public static implicit operator TValue(LRUCacheEntry entry) => entry.Value;
}

If you add to it an implicit operator to TValue, you can simplify this weird looking line

value = node.Value.Value;

to

 value = node.Value;

RemoveLastRecentlyUsed

      if (_cacheMap.Count >= _capacity)
          RemoveLastRecentlyUsed();

I find you should move the if to RemoveLastRecentlyUsed and let it handle everthing about its job of removing items. Currently the logic is two places.

Disabling the cache

You should give the 0 a name like CacheDisabled but creating another class doing nothing would be much better than then tricking this one into something unnatural.

At least you should expose the Capacity or another property like bool Enabled so that the user can see what kind of cache he is using. Might also be useful for debugging. Otherwise you need to look into its private state.

Answer 5

Since I couldn't choose a single answer as the answer, I decided to compilte all the suggestions and comments made and show how the final class(es) looks. It still doesn't use ReaderWriterLockSlim, but the code is far cleaner and contains one or two less bugs. Maybe the final results can be used by others :) thanks to everyone for the feedback, I love this community.

Initial implementation by Martin, from StackOverflow.

Notable changes, in no specific order:

• Exposed SyncRoot [dfhwze]
• Add AddOrCreate method [dfhwze]
• Fixed issue in method `Add(...) [VisualMelon]
• Improved naming of typ-parameters (T -> TKey, V -> TValue) [VisualMelon]
• Added safety measures / documentation code in private methods, e.g. Debug.Assert(Monitor.IsEntered(_lock)) [VisualMelon]
• Added else to if statements [VisualMelon]
• Improved documentation and fixed typos [VisualMelon]
• Created NullCache class and ICache interface [Henrik Hansen]
• Moved "should remove item logic" to method RemoveLeastRecentlyUsedIfNecessary method [3chb0t]
• Sexified of the code by removing generic arguments from LruCacheEntry [3chb0t]

Final results, LruCache.cs:

namespace Minotaur.Collections {
    using System;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.Threading;

    /// <summary>
    /// This class is in-memory, thread-safe cache.
    /// The evicition policy is the Least Recently Used (LRU),
    /// see https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU).
    /// </summary>
    /// <remarks>
    /// This class is based on the following implementation https://stackoverflow.com/a/3719378/1642116
    /// </remarks>
    public sealed class LruCache<TKey, TValue>: ICache<TKey, TValue> {
        private readonly int _capacity;
        private readonly Dictionary<TKey, LinkedListNode<LruCacheEntry>> _cacheMap;
        private readonly LinkedList<LruCacheEntry> _lruList = new LinkedList<LruCacheEntry>();
        public readonly object SyncRoot = new object();

        /// <summary>
        /// The constructor of the class.
        /// <paramref name="capacity"/> must be >= 0.
        /// If you want to disable the caching of the system,
        /// consindering using the NullCache class.
        /// </summary>
        public LruCache(int capacity) {
            if (capacity <= 0)
                throw new ArgumentOutOfRangeException(nameof(capacity) + " must be > 0");

            this._capacity = capacity;
            this._cacheMap = new Dictionary<TKey, LinkedListNode<LruCacheEntry>>(capacity: capacity);
        }

        /// <summary>
        /// Adds the pair (<paramref name="key"/>, <paramref name="value"/>)
        /// to the cache.
        /// If the key is already in the cache, an exception is thrown.
        /// <remarks>
        /// This method is thread-safe.
        /// </remarks>
        public void Add(TKey key, TValue value) {
            if (key == null)
                throw new ArgumentNullException(nameof(key));

            // We are doing as much work as we can outside of the lock
            var cacheItem = new LruCacheEntry(key, value);
            var lruNode = new LinkedListNode<LruCacheEntry>(cacheItem);

            lock (SyncRoot) {
                if (!_cacheMap.ContainsKey(key)) {
                    _cacheMap.Add(key: key, value: lruNode);
                    RemoveLeastRecentlyUsedIfNecessary();
                } else {
                    throw new InvalidOperationException("The value is already in the cache.");
                }
            }
        }

        /// <summary>
        /// Tries to get the value associated with <paramref name="key"/>.
        /// 
        /// If the key is stored in the cache,
        /// <paramref name="value"/> is set to the value associated with it,
        /// the key's "least recently used" data is updated,
        /// and the method returns true.
        /// 
        /// If the key is not stored in the cache,
        /// <paramref name="value"/> is set to default
        /// and the method returns false.
        /// </summary>
        /// <remarks>
        /// This method is thread-safe.
        /// </remarks>
        public bool TryGet(TKey key, out TValue value) {
            if (key == null)
                throw new ArgumentNullException(nameof(key));

            lock (SyncRoot) {
                var isCached = _cacheMap.TryGetValue(key, out var lruNode);

                if (!isCached) {
                    value = default;
                    return false;
                } else {
                    UpdateUsage(lruNode);
                    value = lruNode.Value.Value;
                    return true;
                }
            }
        }

        /// <summary>
        /// Tries to get the value associated with <paramref name="key"/>.
        /// If the value is not stored in the cache,
        /// the function <paramref name="valueCreator"/> 
        /// is called and the result is stored in the cache.
        /// </summary>
        /// <remarks>
        /// This method is thread-safe.
        /// </remarks>
        public TValue GetOrCreate(TKey key, Func<TValue> valueCreator) {
            if (key == null)
                throw new ArgumentNullException(nameof(key));
            if (valueCreator is null)
                throw new ArgumentNullException(nameof(valueCreator));

            // We take the lock for a long time,
            // but we must ensure that the entire operation is atomic.
            // Maybe using System.Threading.ReaderWriterLockSlim and some
            // black magic we could reduce contention, but aint that 
            // high level of a wizard

            lock (SyncRoot) {
                var isCached = _cacheMap.TryGetValue(key: key, value: out var lruNode);
                if (isCached) {
                    UpdateUsage(lruNode);
                    return lruNode.Value.Value;
                }

                // I wish this could be called outside the lock :(
                var value = valueCreator();

                var cacheEntry = new LruCacheEntry(
                    key: key,
                    valeu: value);

                lruNode = new LinkedListNode<LruCacheEntry>(cacheEntry);

                _cacheMap.Add(key: key, value: lruNode);
                RemoveLeastRecentlyUsedIfNecessary();

                return value;
            }
        }

        private void UpdateUsage(LinkedListNode<LruCacheEntry> node) {
            Debug.Assert(Monitor.IsEntered(SyncRoot));

            _lruList.Remove(node);
            _lruList.AddLast(node);
        }

        private void RemoveLeastRecentlyUsedIfNecessary() {
            Debug.Assert(Monitor.IsEntered(SyncRoot));

            if (_cacheMap.Count < _capacity)
                return;

            var node = _lruList.First;
            _lruList.RemoveFirst();
            _cacheMap.Remove(node.Value.Key);
        }

        private sealed class LruCacheEntry {
            public readonly TKey Key;
            public readonly TValue Value;

            public LruCacheEntry(TKey key, TValue valeu) {
                Key = key;
                Value = valeu;
            }
        }
    }
}

NullCache.cs

namespace Minotaur.Collections {
    using System;

    /// <summary>
    /// This class is used to effectively disable caching
    /// in place where a ICache can be used.
    /// </summary>
    public sealed class NullCache<TKey, TValue>: ICache<TKey, TValue> {

        /// <summary>
        /// Does nothing.
        /// </summary>
        /// <remarks>
        /// <paramref name="key"/> still can't be null.
        /// </remarks>
        public void Add(TKey key, TValue value) {
            if (key == null)
                throw new ArgumentNullException(nameof(key));
        }

        /// <summary>
        /// Always assigns default do <paramref name="value"/> and returns false.
        /// </summary>
        /// <remarks>
        /// <paramref name="key"/> still can't be null.
        /// </remarks>
        public bool TryGet(TKey key, out TValue value) {
            if (key == null)
                throw new ArgumentNullException(nameof(key));

            value = default;
            return false;
        }

        /// <summary>
        /// Invokes <paramref name="valueCreator"/> and returns its output.
        /// </summary>
        /// <remarks>
        /// Neither <paramref name="key"/> nor <paramref name="valueCreator"/> can be
        /// null.
        /// </remarks>
        public TValue GetOrCreate(TKey key, Func<TValue> valueCreator) {
            if (key == null)
                throw new ArgumentNullException(nameof(key));
            if (valueCreator is null)
                throw new ArgumentNullException(nameof(valueCreator));

            return valueCreator();
        }
    }
}

ICache.cs

namespace Minotaur.Collections {
    using System;

    public interface ICache<TKey, TValue> {
        void Add(TKey key, TValue value);
        bool TryGet(TKey key, out TValue value);
        TValue GetOrCreate(TKey key, Func<TValue> valueCreator);
    }
}