LFU Cache in C#?

Question

Is there a ready made LFU Cache available in C#?

Answer 1

There is no such set in the framework as of .NET 3.5. Ayende has created a Least Recently Used set. It may be a good start (code).

Answer 2

You could check out MS "Velocity". I'm not sure what savaging strategies they offer, but it might be worth a look. Also, you can extend the strategies that the Caching Application Block offers.

Answer 3

• Java has tons of LFU cache implementations which should be easy to port to C#, for example see: http://faq.javaranch.com/view?CachingStrategies

• This commercial .NET library does LFU http://www.kellermansoftware.com/pc-38-2-net-caching-library.aspx

• This other commercial .NET library does LFU as well: http://www.sharedcache.com/cms/

I am sure there are others.

Here is a basic LFU implementation with aging for C# I just knocked up, its not perfect but is a good starting point: Note: this implementation is not thread safe.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LFU {

    class LFUCache<TKey,TValue> {

        Dictionary<TKey, LinkedListNode<CacheNode>> cache = new Dictionary<TKey, LinkedListNode<CacheNode>>();
        LinkedList<CacheNode> lfuList = new LinkedList<CacheNode>();

        class CacheNode {
            public TKey Key { get; set; }
            public TValue Data { get; set; }
            public int UseCount { get; set; }
        } 

        int size;
        int age = 0;
        int agePolicy;

        public LFUCache(int size) : this(size, 1000) {
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="size"></param>
        /// <param name="agePolicy">after this number of gets the cache will take 1 off all UseCounts, forcing old stuff to expire.</param>
        public LFUCache(int size, int agePolicy) {
            this.agePolicy = 1000;
            this.size = size;
        }

        public void Add(TKey key, TValue val) {
            TValue existing;
            if (!TryGet(key, out existing)) {
                var node = new CacheNode() {Key = key, Data = val, UseCount = 1};
                if (lfuList.Count == size) {
                    cache.Remove(lfuList.First.Value.Key);
                    lfuList.RemoveFirst();
                }

                var insertionPoint = Nodes.LastOrDefault(n => n.Value.UseCount < 2);

                LinkedListNode<CacheNode> inserted; 

                if (insertionPoint == null) {
                    inserted = lfuList.AddFirst(node);
                } else {
                    inserted = lfuList.AddAfter(insertionPoint, node);
                }
                cache[key] = inserted;
            }
        }

        IEnumerable<LinkedListNode<CacheNode>> Nodes {
            get {
                var node = lfuList.First;
                while (node != null) {
                    yield return node;
                    node = node.Next;
                }
            }
        }

        IEnumerable<LinkedListNode<CacheNode>> IterateFrom(LinkedListNode<CacheNode> node) {
            while (node != null) {
                yield return node;
                node = node.Next;
            }
        }

        public TValue GetOrDefault(TKey key) {
            TValue val;
            TryGet(key, out val);
            return val;
        }

        public bool TryGet(TKey key, out TValue val) {

            age++;
            if (age > agePolicy) {
                age = 0;
                foreach (var node in cache.Values) {
                    var v = node.Value;
                    v.UseCount--;
                }
            }

            LinkedListNode<CacheNode> data;
            bool success = false;

            if (cache.TryGetValue(key, out data)) {
                var cacheNode = data.Value;
                val = cacheNode.Data;
                cacheNode.UseCount++;

                var insertionPoint = IterateFrom(data).Last(n => n.Value.UseCount <=  cacheNode.UseCount);

                if (insertionPoint != data) {
                    lfuList.Remove(data);
                    lfuList.AddAfter(insertionPoint, data);
                }

            } else {
                val = default(TValue);
            }

            return success;
        }
    }

    class Program {


        public static void Assert(bool condition, string message) {
            if (!condition) {
                Console.WriteLine("Assert failed : " + message);
                throw new ApplicationException("Test Failed"); 
            }
        }

        public static void RunAllTests(Program prog){
            foreach (var method in prog.GetType().GetMethods()) {
                if (method.Name.StartsWith("Test")) {
                    try {
                        method.Invoke(prog, null);
                        Console.WriteLine("Test Passed: " + method.Name);
                    } catch (Exception) {
                        Console.WriteLine("Test Failed : " + method.Name);
                    }

                }
            }
        }

        public void TestItemShouldBeThereOnceInserted() {
            var cache = new LFUCache<string, int>(3);

            cache.Add("a", 1);
            cache.Add("b", 2);
            cache.Add("c", 3);
            cache.Add("d", 4); 

            Assert(cache.GetOrDefault("a") == 0, "should get 0");
            Assert(cache.GetOrDefault("b") == 2, "should get 2");
            Assert(cache.GetOrDefault("c") == 3, "should get 3");
            Assert(cache.GetOrDefault("d") == 4, "should get 4");
        }

        public void TestLFUShouldWorkAsExpected() {

            var cache = new LFUCache<string, int>(3);

            cache.Add("a", 1);
            cache.Add("b", 2);
            cache.Add("c", 3);

            cache.GetOrDefault("a");
            cache.GetOrDefault("a");
            cache.GetOrDefault("b");

            cache.Add("d", 4);
            cache.Add("e", 5);


            Assert(cache.GetOrDefault("a") == 1, "should get 1");
            Assert(cache.GetOrDefault("b") == 2, "should get 0");
            Assert(cache.GetOrDefault("c") == 0, "should get 0");
            Assert(cache.GetOrDefault("d") == 0, "should get 4");
            Assert(cache.GetOrDefault("e") == 5, "should get 5");

        } 


        static void Main(string[] args) {
            RunAllTests(new Program());
            Console.ReadKey();
        }


    }
}