Thread-safe LRU Dictionary in C#

Question

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?

Answer 1

I found three .NET implementations with a quick Googling:

• http://stackoverflow.com/questions/754233/is-it-there-any-lru-implementation-of-idictionary
• http://www.codeproject.com/Articles/23396/A-High-Performance-Multi-Threaded-LRU-Cache
• http://stackoverflow.com/questions/615648/how-can-i-make-my-simple-net-lru-cache-faster