What data structure should I use for this caching strategy?

Question

I am working on a .NET 4.0 application, that performs a rather expensive calculation on two doubles returning a double. This calculation is performed for each one of several thousand items. These calculations are performed in a Task on a threadpool thread.

Some preliminary tests have shown that the same calculations are performed over and over again, so I would like to cache n results. When the cache is full, I would like to throw out the least-oftenrecently used item. (Edit: I realized least-often doesn't make sense, because when the cache is full and I would replace a result with a newly calculated one, that one would be least often used and immediately replaced the next time a new result is calculated and added to the cache)

In order to implement this, I was thinking of using a Dictionary<Input, double> (where Input would be a mini-class storing the two input double values) to store the inputs and the cached results. However, I would also need to keep track of when a result was used the last time. For this I think I would need a second collection storing the information I would need to remove a result from the dictonary when the cache was getting full. I am concerned that constantly keeping this list sorted would negatively impact performance.

Is there a better (i.e. more performant) way to do this, or maybe even a common data structure that I am unaware of? What kinds of things should I be profiling/measuring to determine the optimality of my solution?

Answer 1

If you wan to use a LRU eviction cache (Least Recently Used eviction), then probably a good combination of data structures to use is:

• Circular linked list (as a priority queue)
• Dictionary

This is why:

• The linked list has a O(1) insertion and removal time
• List nodes can be reused when the list is full and no extra allocations need to be performed.

This is how the basic algorithm should work:

The data structures

LinkedList<Node<KeyValuePair<Input,Double>>> list; Dictionary<Input,Node<KeyValuePair<Input,Double>>> dict;

1. Input is received
2. If the dictionary contains the key
   • return the value stored in the node and move the node to the beginning of the list.
3. If the dictionary does not contain the key
   • compute the value.
   • store the value in the last node of the list.
   • if the last node has a value, remove the previous key from the dictionary.
   • move the last node to first position.
   • store in the dictionary the (input, node) key value pair.

Some benefits of this approach are, reading and setting a dictionary value approaches O(1), inserting and removing a node in a linked list is O(1), which means the algorithm is approaching O(1) for reading and writing of values to the cache, and avoids memory allocations and block memory copying operations, making it stable from a memory point of view.

Answer 2

This seems like a lot of effort to go to for a single calculation given the processing power you have at your disposal in the average PC. Also, You'll still have the expense of the the first call to your calculation for each unique pair of values, so 100,000 unique value pairs will still cost you Time_n * 100,000 at a minimum. Consider that accessing values in your dictionary will likely become slower as the dictionary grows larger. Can you guarantee your dictionary access speed will compensate enough to provide a reasonable return against the speed of your calculation?

Regardless, it sounds as though you will probably need to consider finding a means to optimize your algorithm. For this you'll need a profiling tool, such as Redgate Ants in order see where the bottlenecks are, and to help you to determine if there are ways to reduce some of the overheads you might have relating to class instantiations, list traversals, database accesses, or whatever it is that is costing you so much time.

Answer 3

One thought is why only cache n results? Even if n is 300,000 , you would only use 7.2MB of memory (plus whatever extra for the table structure). That assumes three 64 bit doubles of course. You could simply apply memoization to the complex calcuation routine itself if you are not worried about running out of memory space.

Answer 4

The approach with the second collection is fine. It should be a priority queue which allows finding / deleting min values quickly and also changing (increasing) priorities within the queue (the latter part is the hard one, not supported by most simple prio queue implementations). The C5 library has such a collection, it is called IntervalHeap.

Or course, you can try to build your own collection, something like a SortedDictionary<int, List<InputCount>>. (InputCount must be class combining your Input data with your Count value)

Updating that collection when changing your count value can be implemented by removing and re-inserting an element.

Answer 5

As pointed out in Peter Smith's answer, the pattern you are trying to implement is called memoization. In C# it is pretty hard to implement memoization in a transparent way without side effects. Oliver Sturm's book in functional programming in C# gives a solution (the code is available for download, chapter 10).

In F# it would be much easier. Of course, it's a big decision to start using an other programming language, but it may be worth considering. Especially in complex calculations, it is bound to make more things easier to program than memoization.