9
\$\begingroup\$

Can't seem to find one, so trying to build a very simple but fast implementation. Thought I would post on SO for review/feedback, and so that others can just copy/paste for their own use.

I'm using a Dictionary and LinkedList, with a non-granular lock. Basic benchmark included below:

public class LRUDictionary<TKey,TValue> : IDictionary<TKey,TValue>
{
    private Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>_dict= 
        new Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>>();

    private LinkedList<KeyValuePair<TKey, TValue>> _list = 
        new LinkedList<KeyValuePair<TKey, TValue>>();

    public int Max_Size { get; set; }

    public LRUDictionary(int maxsize)
    {
        Max_Size = maxsize;
    }

    public void Add(TKey key, TValue value)
    {
        lock (_dict)
        {
            LinkedListNode<KeyValuePair<TKey, TValue>> node;

            if (_dict.TryGetValue(key, out node))
            {
                _list.Remove(node);
                _list.AddFirst(node);
            }
            else
            {
                node = new LinkedListNode<KeyValuePair<TKey, TValue>>(
                new KeyValuePair<TKey, TValue>(key, value));

                 _dict.Add(key, node);
                _list.AddFirst(node);

            }

            if (_dict.Count > Max_Size)
            {
                var nodetoremove = _list.Last;
                if (nodetoremove != null)
                    Remove(nodetoremove.Value.Key);
            }
        }

    }

    public bool Remove(TKey key)
    {
        lock (_dict)
        {
            LinkedListNode<KeyValuePair<TKey, TValue>> removednode;
            if (_dict.TryGetValue(key, out removednode))
            {
                _dict.Remove(key);
                _list.Remove(removednode);
                return true;
            }

            else
                return false;
        }
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        LinkedListNode<KeyValuePair<TKey, TValue>> node;

        bool result = false;
        lock (_dict)
            result = _dict.TryGetValue(key, out node);

        if (node != null)
            value = node.Value.Value;
        else
            value = default(TValue);

        return result;
    }

  [rest of IDictionary not implemented yet]

  }

Benchmark:

class Program
{
    static Random rand = new Random();
    static void Main(string[] args)
    {
        var lruspace = 50;
        var setsize = 100;
        var iterations = 1000 * 1000;
        var lrucache = new LRUDictionary<int, int>(lruspace);
        var watch = new Stopwatch();

        watch.Start();

        Parallel.For(0, iterations, (i) =>
        {
            lrucache.Add(rand.Next(setsize), 0);
            lrucache.Add(rand.Next(setsize), 0);

            lrucache.Remove(rand.Next(setsize));
            lrucache.Add(rand.Next(setsize), 0);

            lrucache.Remove(rand.Next(setsize));
            lrucache.Remove(rand.Next(setsize));

            lrucache.Add(rand.Next(setsize), 0);
            lrucache.Remove(rand.Next(setsize));
            lrucache.Add(rand.Next(setsize), 0);
            lrucache.Add(rand.Next(setsize), 0);
            lrucache.Add(rand.Next(setsize), 0);
        });

        Console.WriteLine(watch.ElapsedMilliseconds);
        Console.ReadLine();

    }
}

Output:

2592ms

Is this the best way to go? Any obvious improvements?

\$\endgroup\$
11
  • \$\begingroup\$ You might want to take a look at C5 which is available on its Github repo where you can see its source \$\endgroup\$
    – Dharun
    Commented Oct 6, 2012 at 16:14
  • \$\begingroup\$ your lock sections are too big, also if the thread count goes up, two threads can enter lock at the same time. which breaks your correctness. \$\endgroup\$
    – DarthVader
    Commented Oct 6, 2012 at 16:18
  • \$\begingroup\$ before you look at performance, look at correctness. i doubt for several threads you will have correct results \$\endgroup\$
    – DarthVader
    Commented Oct 6, 2012 at 16:19
  • \$\begingroup\$ I'm starting with big locks to ensure correctness. How can two threads enter the lock? \$\endgroup\$
    – Harry Mexican
    Commented Oct 6, 2012 at 16:21
  • 1
    \$\begingroup\$ I found three .NET implementations with a quick Googling: - stackoverflow.com/questions/754233/… - codeproject.com/Articles/23396/… - stackoverflow.com/questions/615648/… \$\endgroup\$ Commented Oct 9, 2012 at 13:34

2 Answers 2

3
\$\begingroup\$

Whilst your code is thread safe, since you have a global lock protecting the dictionary (and the lock is relatively long lived), it will be a serious bottleneck under concurrent load. The principal scalability limit in concurrent applications is the exclusive resource lock.

The chart below shows throughput with an increasing degree of parallelism on a 16 core VM for concurrent LRU reads and writes. It compares an implementation of LRU that does not have a global lock, to an implementation fundamentally the same as your code (with a global lock).

enter image description here

In this test I set the concurrent dictionary concurrency level = number of threads. I believe the unusual dip at the beginning is caused by false sharing. It's old now, but gallery of processor cache effects has a nice description.

The implementation with better throughput is a thread safe pseudo LRU designed for concurrent workloads. Latency is very close to ConcurrentDictionary, ~10x faster than MemoryCache and hit rate is better than a conventional LRU algorithm (these are the other two factors that will determine performance). A full analysis provided in the github link below.

Usage of the ConcurrentLru looks like this:

int capacity = 666;
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

Below is the complete source code for the ClassicLRU tested above. It has shorter span locks and uses ConcurrentDictionary. It's not intended for production use (it may have bugs) - it's just to illustrate that even when taking narrow locks throughput is still bad under concurrent load.

public sealed class ClassicLru<K, V> : ICache<K, V>
{
    private readonly int capacity;
    private readonly ConcurrentDictionary<K, LinkedListNode<LruItem>> dictionary;
    private readonly LinkedList<LruItem> linkedList = new LinkedList<LruItem>();

    private long requestHitCount;
    private long requestTotalCount;

    public ClassicLru(int capacity)
        : this(Defaults.ConcurrencyLevel, capacity, EqualityComparer<K>.Default)
    { 
    }

    public ClassicLru(int concurrencyLevel, int capacity, IEqualityComparer<K> comparer)
    {
        if (capacity < 3)
        {
            throw new ArgumentOutOfRangeException("Capacity must be greater than or equal to 3.");
        }

        if (comparer == null)
        {
            throw new ArgumentNullException(nameof(comparer));
        }

        this.capacity = capacity;
        this.dictionary = new ConcurrentDictionary<K, LinkedListNode<LruItem>>(concurrencyLevel, this.capacity + 1, comparer);
    }

    public int Count => this.linkedList.Count;

    public double HitRatio => (double)requestHitCount / (double)requestTotalCount;

    ///<inheritdoc/>
    public bool TryGet(K key, out V value)
    {
        Interlocked.Increment(ref requestTotalCount);

        LinkedListNode<LruItem> node;
        if (dictionary.TryGetValue(key, out node))
        {
            LockAndMoveToEnd(node);
            Interlocked.Increment(ref requestHitCount);
            value = node.Value.Value;
            return true;
        }

        value = default(V);
        return false;
    }

    public V GetOrAdd(K key, Func<K, V> valueFactory)
    {
        if (this.TryGet(key, out var value))
        {
            return value;
        }

        var node = new LinkedListNode<LruItem>(new LruItem(key, valueFactory(key)));

        if (this.dictionary.TryAdd(key, node))
        {
            LinkedListNode<LruItem> first = null;

            lock (this.linkedList)
            {
                if (linkedList.Count >= capacity)
                {
                    first = linkedList.First;
                    linkedList.RemoveFirst();
                }

                linkedList.AddLast(node);
            }

            // Remove from the dictionary outside the lock. This means that the dictionary at this moment
            // contains an item that is not in the linked list. If another thread fetches this item, 
            // LockAndMoveToEnd will ignore it, since it is detached. This means we potentially 'lose' an 
            // item just as it was about to move to the back of the LRU list and be preserved. The next request
            // for the same key will be a miss. Dictionary and list are eventually consistent.
            // However, all operations inside the lock are extremely fast, so contention is minimized.
            if (first != null)
            {
                dictionary.TryRemove(first.Value.Key, out var removed);

                if (removed.Value.Value is IDisposable d)
                {
                    d.Dispose();
                }
            }

            return node.Value.Value;
        }

        return this.GetOrAdd(key, valueFactory);
    }

    public bool TryRemove(K key)
    {
        if (dictionary.TryRemove(key, out var node))
        {
            // If the node has already been removed from the list, ignore.
            // E.g. thread A reads x from the dictionary. Thread B adds a new item, removes x from 
            // the List & Dictionary. Now thread A will try to move x to the end of the list.
            if (node.List != null)
            {
                lock (this.linkedList)
                {
                    if (node.List != null)
                    {
                        linkedList.Remove(node);
                    }
                }
            }

            if (node.Value.Value is IDisposable d)
            {
                d.Dispose();
            }

            return true;
        }

        return false;
    }

    // Thead A reads x from the dictionary. Thread B adds a new item. Thread A moves x to the end. Thread B now removes the new first Node (removal is atomic on both data structures).
    private void LockAndMoveToEnd(LinkedListNode<LruItem> node)
    {
        // If the node has already been removed from the list, ignore.
        // E.g. thread A reads x from the dictionary. Thread B adds a new item, removes x from 
        // the List & Dictionary. Now thread A will try to move x to the end of the list.
        if (node.List == null)
        {
            return;
        }

        lock (this.linkedList)
        {
            if (node.List == null)
            {
                return;
            }

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

    private class LruItem
    {
        public LruItem(K k, V v)
        {
            Key = k;
            Value = v;
        }

        public K Key { get; }

        public V Value { get; }
    }
}
\$\endgroup\$
0
1
\$\begingroup\$

Another implementation is available here.

The benefit to the approach in the LunchTable.cs is that it does not aggregate an existing dictionary implementation, but rather is both the dictionary and linked list rolled into one class. Thread-safe and ready to go, see the discussion here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.