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

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

Answer 2

Unless you're sure Delegate's implementation of GetHashCode is deterministic and doesn't result in any collisions I wouldn't trust it.

Here's two ideas. First, store the results of the delegates within a Predicate/List dictionary, using the predicate as the key, and then store the entire dictionary of results under a single key in the cache. Bad thing is that you lose all your cached results if the cache item is lost.

An alternative would be to create an extension method for Predicate, GetKey(), that uses an object/string dictionary to store and retrieve all keys for all Predicates. You index into the dictionary with the delegate and return its key, creating one if you don't find it. This way you're assured that you are getting the correct key per delegate and there aren't any collisions. A naiive one would be type name + Guid.

Answer 3

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 4

The same instance of an object will always return the same hashcode (requirement of GetHashCode() in .Net). If your predicates are inside a static list and you are not redefining them each time, I can't see a problem in using them as keys.

Answer 5

Keeping the cached results in a Dictionary<Predicate<Foo>,List<Foo>> is awkward for me because I want the ASP.NET cache to handle expiry for me rather than caching all results forever, but it's otherwise a good solution. I think I'll end up going with Will's Dictionary<Predicate<Foo>,string> to cache a string that I can use in the ASP.NET cache key.

Some initial tests suggest that delegate equality does the "right thing" as others have said, but Delegate.GetHashCode is pathologically unhelpful. Reflector reveals

public override int GetHashCode()
{
    return base.GetType().GetHashCode();
}

So any Predicate<Foo> returns the same result.

My remaining issue was how equality works for anonymous delegates. What does "same method called on the same target" mean then? It seems that as long as the delegate was defined in the same place, references are equal. Delegates with the same body defined in different places are not.

static Predicate<int> Test()
{
    Predicate<int> test = delegate(int i) { return false; };
    return test;
}

static void Main()
{
    Predicate<int> test1 = Test();
    Predicate<int> test2 = Test();
    Console.WriteLine(test1.Equals( test2 )); // True

    test1 = delegate(int i) { return false; };
    test2 = delegate(int i) { return false; };
    Console.WriteLine(test1.Equals( test2 )); // False
}

This should be OK for my needs. Calls with the predefined predicates will be cached. Multiple calls to one method that calls FindAll with an anonymous method should get cached results. Two methods calling FindAll with apparently the same anonymous method won't share cached results, but this should be fairly rare.