Caching delegate results

Question

I have a C# method which accepts a Predicate<Foo> and returns a list of matching items...

public static List<Foo> FindAll( Predicate<Foo> filter )
{
    ...
}

The filter will often be one of a common set...

public static class FooPredicates
{
    public static readonly Predicate<Foo> IsEligible = ( foo => ...)
    ...
}

...but may be an anonymous delegate.

I'd now like to have this method cache its results in the ASP.NET cache, so repeated calls with the same delegate just return the cached result. For this, I need to create a cache key from the delegate. Will Delegate.GetHashCode() produce sensible results for this purpose? Is there some other member of Delegate that I should look at? Would you do this another way entirely?

Answer 1

To perform your caching task, you can follow the other suggestions and create a Dictionary<Predicate<Foo>,List<Foo>> (static for global, or member field otherwise) that caches the results. Before actually executing the Predicate<Foo>, you would need to check if the result already exists in the dictionary.

The general name for this deterministic function caching is called Memoization - and its awesome :)

Ever since C# 3.0 added lambda's and the swag of Func/Action delegates, adding Memoization to C# is quite easy.

Wes Dyer has a great post that brings the concept to C# with some great examples.

If you want me to show you how to do this, let me know...otherwise, Wes' post should be adequate.

In answer to your query about delegate hash codes. If two delegates are the same, d1.GetHashCode() should equal d2.GetHashCode(), but I'm not 100% about this. You can check this quickly by giving Memoization a go, and adding a WriteLine into your FindAll method. If this ends up not being true, another option is to use Linq.Expression<Predicate<Foo>> as a parameter. If the expressions are not closures, then expressions that do the same thing should be equal.

Let me know how this goes, I'm interested to know the answer about delegate.Equals.

Answer 2

Delegate equality looks at each invocation in the invocation list, testing for equality of method to be invoked, and target of method.

The method is a simple piece of the cache key, but the target of the method (the instance to call it on - assuming an instance method) could be impossible to cache in a serializable way. In particular, for anonymous functions which capture state, it will be an instance of a nested class created to capture that state.

If this is all in memory, just keeping the delegate itself as the hash key will be okay - although it may mean that some objects which clients would expect to be garbage collected hang around. If you need to serialize this to a database, it gets hairier.

Could you make your method accept a cache key (e.g. a string) as well? (That's assuming an in memory cache is inadequate.)