8
\$\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\$

migrated from stackoverflow.com Oct 8 '12 at 15:06

This question came from our site for professional and enthusiast programmers.

  • \$\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 Oct 6 '12 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 Oct 6 '12 at 16:18
  • \$\begingroup\$ before you look at performance, look at correctness. i doubt for several threads you will have correct results \$\endgroup\$ – DarthVader Oct 6 '12 at 16:19
  • \$\begingroup\$ I'm starting with big locks to ensure correctness. How can two threads enter the lock? \$\endgroup\$ – Harry Mexican Oct 6 '12 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\$ – smartcaveman Oct 9 '12 at 13:34
2
\$\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, privacy policy and cookie policy

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