Is it there any LRU implementation of IDictionary?

Question

I would like to implement a simple in-memory LRU cache system and I was thinking about a solution based on an IDictionary implementation which could handle an hashed LRU mechanism. Coming from java, I have experiences with LinkedHashMap, which works fine for what I need: I can't find anywhere a similar solution for .NET.

Has anyone developed it or has anyone had experiences like this?

Answer 1

This a very simple and fast implementation we developed for a web site we own.

We tried to improve the code as much as possible, while keeping it thread safe. I think the code is very simple and clear, but if you need some explanation or a guide related to how to use it, don't hesitate to ask.

namespace LRUCache
{
    public class LRUCache<K,V>
    {
        private int capacity;
        private Dictionary<K, LinkedListNode<LRUCacheItem<K, V>>> cacheMap = new Dictionary<K, LinkedListNode<LRUCacheItem<K, V>>>();
        private LinkedList<LRUCacheItem<K, V>> lruList = new LinkedList<LRUCacheItem<K, V>>();

        public LRUCache(int capacity)
        {
            this.capacity = capacity;
        }

        [MethodImpl(MethodImplOptions.Synchronized)]
        public V get(K key)
        {
            LinkedListNode<LRUCacheItem<K, V>> node;
            if (cacheMap.TryGetValue(key, out node))
            {
                V value = node.Value.value;
                lruList.Remove(node);
                lruList.AddLast(node);
                return value;
            }
            return default(V);
        }

        [MethodImpl(MethodImplOptions.Synchronized)]
        public void add(K key, V val)
        {
            if (cacheMap.TryGetValue(key, out var existingNode))
            {
                lruList.Remove(existingNode);
            }
            else if (cacheMap.Count >= capacity)
            {
                RemoveFirst();
            }

            LRUCacheItem<K, V> cacheItem = new LRUCacheItem<K, V>(key, val);
            LinkedListNode<LRUCacheItem<K, V>> node = new LinkedListNode<LRUCacheItem<K, V>>(cacheItem);
            lruList.AddLast(node);
            // cacheMap.Add(key, node); - here's bug if try to add already existing value
            cacheMap[key] = node;
        }

        private void RemoveFirst()
        {
            // Remove from LRUPriority
            LinkedListNode<LRUCacheItem<K,V>> node = lruList.First;
            lruList.RemoveFirst();

            // Remove from cache
            cacheMap.Remove(node.Value.key);
        }
    }

    class LRUCacheItem<K,V>
    {
        public LRUCacheItem(K k, V v)
        {
            key = k;
            value = v;
        }
        public K key;
        public V value;
    }
}

Answer 2

There is nothing in the base class libraries that does this.

On the free side, maybe something like C5's HashedLinkedList would work.

If you're willing to pay, maybe check out this C# toolkit. It contains an implementation.

Answer 3

I've recently released a class called LurchTable to address the need for a C# variant of the LinkedHashMap. A brief discussion of the LurchTable can be found here.

Basic features:

• Linked Concurrent Dictionary by Insertion, Modification, or Access
• Dictionary/ConcurrentDictionary interface support
• Peek/TryDequeue/Dequeue access to 'oldest' entry
• Allows hard-limit on items enforced at insertion
• Exposes events for add, update, and remove

Source Code: http://csharptest.net/browse/src/Library/Collections/LurchTable.cs

GitHub: https://github.com/csharptest/CSharpTest.Net.Collections

HTML Help: http://help.csharptest.net/

PM> Install-Package CSharpTest.Net.Collections

Answer 4

The LRUCache answer with sample code above (by Martin) uses MethodImplOptions.Synchronized, which is equivalent to putting lock(this) around each method call. Whilst correct, this global lock will significantly reduce throughput under concurrent load.

To solve this I implemented a thread safe pseudo LRU designed for concurrent workloads. Performance is very close to ConcurrentDictionary, ~10x faster than MemoryCache and hit rate is better than a conventional LRU. Full analysis provided in the GitHub link below.

Usage looks like this:

int capacity = 500;
var lru = new ConcurrentLru<int, SomeItem>(capacity);

var value = lru.GetOrAdd(1, (k) => new SomeItem(k));

GitHub: https://github.com/bitfaster/BitFaster.Caching

Install-Package BitFaster.Caching

Answer 5

This takes Martin's code with Mr T's suggestions and makes it Stylecop friendly. Oh, it also allows for disposal of values as they cycle out of the cache.

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

    /// <summary>
    /// A least-recently-used cache stored like a dictionary.
    /// </summary>
    /// <typeparam name="TKey">
    /// The type of the key to the cached item
    /// </typeparam>
    /// <typeparam name="TValue">
    /// The type of the cached item.
    /// </typeparam>
    /// <remarks>
    /// Derived from https://stackoverflow.com/a/3719378/240845
    /// </remarks>
    public class LruCache<TKey, TValue>
    {
        private readonly Dictionary<TKey, LinkedListNode<LruCacheItem>> cacheMap =
            new Dictionary<TKey, LinkedListNode<LruCacheItem>>();

        private readonly LinkedList<LruCacheItem> lruList =
            new LinkedList<LruCacheItem>();

        private readonly Action<TValue> dispose;

        /// <summary>
        /// Initializes a new instance of the <see cref="LruCache{TKey, TValue}"/>
        /// class.
        /// </summary>
        /// <param name="capacity">
        /// Maximum number of elements to cache.
        /// </param>
        /// <param name="dispose">
        /// When elements cycle out of the cache, disposes them. May be null.
        /// </param>
        public LruCache(int capacity, Action<TValue> dispose = null)
        {
            this.Capacity = capacity;
            this.dispose = dispose;
        }

        /// <summary>
        /// Gets the capacity of the cache.
        /// </summary>
        public int Capacity { get; }

        /// <summary>Gets the value associated with the specified key.</summary>
        /// <param name="key">
        /// The key of the value to get.
        /// </param>
        /// <param name="value">
        /// When this method returns, contains the value associated with the specified
        /// key, if the key is found; otherwise, the default value for the type of the 
        /// <paramref name="value" /> parameter. This parameter is passed
        /// uninitialized.
        /// </param>
        /// <returns>
        /// true if the <see cref="T:System.Collections.Generic.Dictionary`2" /> 
        /// contains an element with the specified key; otherwise, false.
        /// </returns>
        public bool TryGetValue(TKey key, out TValue value)
        {
            lock (this.cacheMap)
            {
                LinkedListNode<LruCacheItem> node;
                if (this.cacheMap.TryGetValue(key, out node))
                {
                    value = node.Value.Value;
                    this.lruList.Remove(node);
                    this.lruList.AddLast(node);
                    return true;
                }

                value = default(TValue);
                return false;
            }
        }

        /// <summary>
        /// Looks for a value for the matching <paramref name="key"/>. If not found, 
        /// calls <paramref name="valueGenerator"/> to retrieve the value and add it to
        /// the cache.
        /// </summary>
        /// <param name="key">
        /// The key of the value to look up.
        /// </param>
        /// <param name="valueGenerator">
        /// Generates a value if one isn't found.
        /// </param>
        /// <returns>
        /// The requested value.
        /// </returns>
        public TValue Get(TKey key, Func<TValue> valueGenerator)
        {
            lock (this.cacheMap)
            {
                LinkedListNode<LruCacheItem> node;
                TValue value;
                if (this.cacheMap.TryGetValue(key, out node))
                {
                    value = node.Value.Value;
                    this.lruList.Remove(node);
                    this.lruList.AddLast(node);
                }
                else
                {
                    value = valueGenerator();
                    if (this.cacheMap.Count >= this.Capacity)
                    {
                        this.RemoveFirst();
                    }

                    LruCacheItem cacheItem = new LruCacheItem(key, value);
                    node = new LinkedListNode<LruCacheItem>(cacheItem);
                    this.lruList.AddLast(node);
                    this.cacheMap.Add(key, node);
                }

                return value;
            }
        }

        /// <summary>
        /// Adds the specified key and value to the dictionary.
        /// </summary>
        /// <param name="key">
        /// The key of the element to add.
        /// </param>
        /// <param name="value">
        /// The value of the element to add. The value can be null for reference types.
        /// </param>
        public void Add(TKey key, TValue value)
        {
            lock (this.cacheMap)
            {
                if (this.cacheMap.Count >= this.Capacity)
                {
                    this.RemoveFirst();
                }

                LruCacheItem cacheItem = new LruCacheItem(key, value);
                LinkedListNode<LruCacheItem> node = 
                    new LinkedListNode<LruCacheItem>(cacheItem);
                this.lruList.AddLast(node);
                this.cacheMap.Add(key, node);
            }
        }

        private void RemoveFirst()
        {
            // Remove from LRUPriority
            LinkedListNode<LruCacheItem> node = this.lruList.First;
            this.lruList.RemoveFirst();

            // Remove from cache
            this.cacheMap.Remove(node.Value.Key);

            // dispose
            this.dispose?.Invoke(node.Value.Value);
        }

        private class LruCacheItem
        {
            public LruCacheItem(TKey k, TValue v)
            {
                this.Key = k;
                this.Value = v;
            }

            public TKey Key { get; }

            public TValue Value { get; }
        }
    }
}

Answer 6

Found you answer while googling, also found this:

http://code.google.com/p/csharp-lru-cache/

csharp-lru-cache: LRU cache collection class library

This is a collection class that functions as a least-recently-used cache. It implements ICollection<T>, but also exposes three other members:

• Capacity, the maximum number of items the cache can contain. Once the collection is at capacity, adding a new item to the cache will cause the least recently used item to be discarded. If the Capacity is set to 0 at construction, the cache will not automatically discard items.
• Oldest, the oldest (i.e. least recently used) item in the collection.
• DiscardingOldestItem, an event raised when the cache is about to discard its oldest item. This is an extremely simple implementation. While its Add and Remove methods are thread-safe, it shouldn't be used in heavy multithreading environments because the entire collection is locked during those methods.

Answer 7

The Caching Application Block of EntLib has an LRU scavenging option out of the box and can be in memory. It might be a bit heavyweight for what you want tho.

Answer 8

I like Lawrence's implementation. Hashtable + LinkedList is a good solution.

Regarding threading, I would not lock this with[MethodImpl(MethodImplOptions.Synchronized)], but rather use ReaderWriterLockSlim or spin lock (since contention usually fast) instead.

In the Get function I would check if it's already the 1st item first, rather than always removing and adding. This gives you the possibility to keep that within a reader lock that is not blocking other readers.

Answer 9

I don't believe so. I've certainly seen hand-rolled ones implemented several times in various unrelated projects (which more or less confirms this. If there was one, surely at least one of the projects would have used it).

It's pretty simple to implement, and usually gets done by creating a class which contains both a Dictionary and a List.

The keys go in the list (in-order) and the items go in the dictionary.
When you Add a new item to the collection, the function checks the length of the list, pulls out the last Key (if it's too long) and then evicts the key and value from the dictionary to match. Not much more to it really

Answer 10

I just accidently found now LruCache.cs in aws-sdk-net: https://github.com/aws/aws-sdk-net/blob/master/sdk/src/Core/Amazon.Runtime/Internal/Util/LruCache.cs

Answer 11

Here is a modern implementation of a LRUCache<TKey, TValue> collection, for .NET 6 and later. The main feature is the method GetOrAdd. This method either returns an existing value, or invokes the valueFactory and returns a new value. Each time a new value is added, the boundedCapacity policy is enforced by evicting the least recently used value from the collection. The valueFactory is invoked lazily, so that multiple concurrent GetOrAdd calls for the same key receive the same value.

public class LRUCache<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
{
    private readonly Dictionary<TKey, LinkedListNode<Entry>> _dictionary;
    private readonly LinkedList<Entry> _linkedList;
    private readonly int _boundedCapacity;

    private readonly record struct Entry(TKey Key, Lazy<TValue> Lazy);

    public LRUCache(int boundedCapacity, IEqualityComparer<TKey> comparer = default)
    {
        if (boundedCapacity < 0)
            throw new ArgumentOutOfRangeException(nameof(boundedCapacity));
        _dictionary = new(boundedCapacity + 1, comparer);
        _linkedList = new();
        _boundedCapacity = boundedCapacity;
    }

    private object SyncRoot => _dictionary;
    public int Count { get { lock (SyncRoot) return _dictionary.Count; } }

    public TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory)
    {
        ArgumentNullException.ThrowIfNull(valueFactory);
        Lazy<TValue> lazy;
        lock (SyncRoot)
        {
            ref LinkedListNode<Entry> refNode = ref CollectionsMarshal
                .GetValueRefOrAddDefault(_dictionary, key, out bool exists);
            if (exists)
            {
                lazy = refNode.Value.Lazy;
                if (!ReferenceEquals(refNode, _linkedList.Last))
                {
                    _linkedList.Remove(refNode);
                    _linkedList.AddLast(refNode);
                }
            }
            else
            {
                lazy = new(() => valueFactory(key));
                refNode = new(new Entry(key, lazy));
                _linkedList.AddLast(refNode);
                if (_dictionary.Count > _boundedCapacity)
                {
                    bool removed = _dictionary.Remove(_linkedList.First.Value.Key);
                    Debug.Assert(removed);
                    _linkedList.RemoveFirst();
                }
            }
            Debug.Assert(_dictionary.Count == _linkedList.Count);
        }
        return lazy.Value;
    }

    public void Clear()
    {
        lock (SyncRoot)
        {
            _dictionary.Clear();
            _linkedList.Clear();
        }
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        lock (SyncRoot)
        {
            return _linkedList
                .ToArray()
                .Select((Entry e) => KeyValuePair.Create(e.Key, e.Lazy.Value))
                .AsEnumerable()
                .GetEnumerator();
        }
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

Usage example:

LRUCache<string, object> cache = new(30);
object value = cache.GetOrAdd("SomeKey", key => GetObject(key));

The advanced API CollectionsMarshal.GetValueRefOrAddDefault is used so that the key is hashed only once per GetOrAdd call.

In case the valueFactory fails, the behavior of the Lazy<T> class is to cache permanently the exception. This behavior might not be suitable for a caching system, so you may want to substitute the Lazy<T> with the simple LazyWithRetry<T> implementation that I have posted here.

In case you would like to use an asynchronous valueFactory, there are AsyncLazy<T> implementations in this question.

The LRUCache<TKey, TValue> class is thread-safe.

Answer 12

If it's an asp.net app you can use the cache class[1] but you'll be competing for space with other cached stuff, which may be what you want or may not be.

[1] http://msdn.microsoft.com/en-us/library/system.web.caching.cache.aspx

Answer 13

There is OrderedDictionary

using System.Collections.Specialized;

You can remove a element by key and (re)insert it on the end of the order. When you need memory remove the first element in the order.

This shows how, but its a trifle slower:

https://leetcode.com/problems/lru-cache/solutions/1065496/c-two-implementationsordered-dictionary-linkedlist-and-their-comparison-with-explanation/