Cache Function results
.net, c#, caching
Solution
Another name for this automatic caching of function results is memoization. For a public interface, consider something along these lines:
public Func<T,TResult> Memoize<T,TResult>(Func<T,TResult> f)
... and simply use polymorphism to store T's in a dictionary of object.
Extending the delegate range could be implemented via currying and partial function application. Something like this:
static Func<T1,Func<T2,TResult>> Curry(Func<T1,T2,TResult> f)
{
return x => y => f(x, y);
}
// more versions of Curry
Since `Curry` turns functions of multiple arguments into functions of single arguments (but that may return functions), the return values are eligible for memoization themselves.
Another way to do it would be to use reflection to inspect the delegate type, and store tuples in the dictionary rather than simply the argument type. A simplistic tuple would be simply an array wrapper whose hashcode and equality logic used deep comparisons and hashing.
Invalidation could be helped with weak references, but creating dictionaries with `WeakReference` keys is tricky - it's best done with the support of the runtime (WeakReference values is much easier). I believe there are some implementations out there.
Thread safety is easily done by locking on the internal dictionary for mutation events, but having a lock-free dictionary may improve performance in heavily concurrent scenarios. That dictionary would probably be even harder to create - there's an interesting presentation on one for Java here though.
Problem
For fun, I'm playing with a class to easily cache function results. The basic idea is that you can take any function you want — though you'd only want to use it for relatively expensive functions — and easily wrap it to use relatively inexpensive dictionary lookups for later runs with the same argument. There's really not much to it: ``` public class AutoCache<TKey, TValue> { public AutoCache(Func<TKey, TValue> FunctionToCache) { _StoredFunction = FunctionToCache; _CachedData = new Dictionary<TKey, TValue>(); } public TValue GetResult(TKey Key) { if (!_CachedData.ContainsKey(Key)) _CachedData.Add(Key, _StoredFunction(Key)); return _CachedData[Key]; } public void InvalidateKey(TKey Key) { _CachedData.Remove(Key); } public void InvalidateAll() { _CachedData.Clear(); } private Dictionary<TKey, TValue> _CachedData; private Func<TKey, TValue> _StoredFunction; } ``` Unfortunately, there are some additional restrictions that make this much less useful than it could be. There are also some features we could add and other considerations to the implementation. I'm looking for thoughts on ways this can be improved for any of the following points: - This requires a function that returns the same result for a given set of arguments (it must be stateless). Probably no way to change this. - It's limited to a very narrow delegate range. Could we expand it to easily work for any function that accepts at least one parameter and returns a value, perhaps by wrapping arguments in an anonymous type? Or would we need an additional implemenation for each Func delegate we wanted to support? If so, can we build an abstract class to make this easier? - It's not thread-safe. - No automatic invalidation. This makes it dangerous for garbage collection. You need to keep it around for a while for it to be useful, and that means you're not going to really ever discard old and potentially un-needed cache items. - Can we inherit from this to make the cache bi-directional for the case where the function has a single argument? As a point of reference, if I ever use this in real code the most likely place I envision it is as part of a business logic layer, where I use this code to wrap a method in the data access layer that just pulls data from a lookup table. In this case, the database trip would be expensive relative to the dictionary and there would almost always be exactly one 'key' value for the lookup, so it's a good match.