Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

5 Answers 5

up vote 10 down vote accepted

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 not 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.

share|improve this answer
    
Good points, the best idea so far, IMHO. I implemented a cache based on this today and will have to profile and see how well it performs tomorrow. –  PersonalNexus Feb 22 '12 at 17:06

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.

share|improve this answer

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.

share|improve this answer

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 Timen * 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.

share|improve this answer
    
Unfortunately, for the time being the calculation algorithm cannot be changed, as it's a third-party library that uses some advanced math which is naturally CPU intensive. If at a later time that will be reworked, I will definitely check out the profiling tools suggested. Furthermore, the calculation will be performer quite often, sometimes with identical inputs, so preliminary profiling has shown a clear benefit even with a very naive caching strategy. –  PersonalNexus Feb 22 '12 at 14:13

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.

share|improve this answer
    
There won't be just one cache, but one per "item" that I am analyzing, and there can be several hundred-thousand of these items. –  PersonalNexus Feb 22 '12 at 6:46
    
In what way does it matter which 'Item' the input comes from? are there side effects? –  jk. Feb 22 '12 at 9:51
    
@jk. Different items will produce very different inputs to the calculation. Since this means that there will be little overlap, I don't think keeping them in a single cache makes sense. Furthermore, different items could live in different threads, so in order to avoid shared state, I would like to keep the caches separate. –  PersonalNexus Feb 22 '12 at 14:19
    
@PersonalNexus I take this to imply there are more then 2 parameters involved in the calculation? Elsewise, you still basically have f(x, y) = do some stuff. Plus shared state seems like it would help performance rather than hinder? –  Peter Smith Feb 22 '12 at 15:03
    
@PeterSmith The two parameters are the main inputs. There are others, but they rarely change. If they do, I would throw the entire cache away. By "shared state" I meant a shared cache for all or a group of items. Since this would need to be locked or synchronized some other way, it would hinder performance. More on the performance implications of shared state. –  PersonalNexus Feb 22 '12 at 17:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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