Memoization and Caching

One thing that is useful in any kind of programming is having a look-up table so that you don’t have to spend expensive calls to fetch the same data that you just had recently, since fetching the data and passing it around via parameters often gets ugly. A better way is to use a cache – store values we’ve fetched recently and reuse them. So, a naïve approach would be to store the data off in a simple Dictionary. This might work for awhile, but you soon realize as Raymond Chen says, “Every cache has a cache policy, whether you know it or not.” In the case of a Dictionary, the policy is unbounded – an unbounded cache is a synonym for ‘memory leak’.

To this end, one of the things that comes with ReactiveXaml is a class called MemoizingMRUCache. As its name implies, it is a most recently used cache – we’ll throw away items whose keys haven’t been requested in awhile; we’ll keep a fixed limit of items in the cache, unlike other approaches involving WeakReference that keep references to items only if they’re used on some other thread at the time. Since most desktop / Silverlight applications aren’t so massively multithreaded as a web application, using a WeakReference approach means we’ll just get constant cache misses.

Using MemoizingMRUCache

Really when it comes down to it, you can just think of MemoizingMRUCache as just a proxy for a function – when you call Get, it’s going to invoke the function you provided in the constructor. One thing that’s important to understand with this class, is that your function must be a function in the mathematical sense – i.e. the return value for a given parameter must always be identical. Another thing to remember is that this class is not implicitly thread-safe – unlike QueuedAsyncMRUCache, if you use it from multiple threads, you have to protect it via a lock just like a Dictionary or a List.

Here’s a motivating sample:

Maintaining an on-disk cache

MemoizingMRUCache also has a feature that comes in handy in certain scenarios: when a memoized value is evicted from the cache because it hasn’t been used in awhile, you can have a function be executed with that value. This means that MemoizingMRUCache can be used to maintain on-disk caches – your Key could be a website URL, and the Value will be a path to the temporary file. Your OnRelease function will delete the file on the disk since it’s no longer in-use.

Some other useful functions

• TryGet – Attempt to fetch a value from the cache only
• Invalidate – Forget a cached key if we’ve remembered it and call its release function
• InvalidateAll – Forget all the cached keys and start from scratch