Building a Cache Key quickly

Question

I am using a custom cache implementation in a Web Api 2 application. This cache stores hundreds of thousands of items and can be read from up to 10,000 times in a single API request.

On profiling, I have found that the actual building of each items' cache key is significantly affecting overall performance.

Result from .NET profiling:

Sampling Profiler

Cache key details:

I am building a the items' key by hashing a string. E.g:

MySystem.MyProject.MyNamespace.MyClass.SomeMethod(44,6948)

This gets hashed into something like this, which is then used in the caching framework as the key (this is not longer used - refer to EDIT 3):

1bbbfeae-b143-77f2-8381-5ee11f5b9c0c

Obviously I need to ensure uniqueness on each key, but I can't seem to find a way to improve the performance here without introducing possible duplication.

The key builder:

public class CacheKeyBuilder
{
    private MethodInterceptionArgs methodArguments;

    public CacheKeyBuilder(MethodInterceptionArgs input)
    {
        methodArguments = input;
    }

    // No longer used - refer to EDIT 3
    public UInt64 GetHashedKey()
    {
        return Hash(GetFriendlyKey());
    }

    public string GetFriendlyKey()
    {
        if (methodArguments.Arguments.OfType<IList>().Any())
        {
            throw new ArgumentOutOfRangeException("Cannot create a keys from IList types");
        }

        var type = methodArguments.Binding.GetType();

        var key = String.Format("{0}.{1}.{2}{3}{4}",
            type.Namespace,
            type.DeclaringType.Name,
            methodArguments.Method.Name,
            type.UnderlyingSystemType.GenericTypeArguments.Select(x => x.Name).ToList().JoinItems("<", ">", ","),
            methodArguments.Arguments.Where(x => x != null).Select(x => x.ToString()).ToList().JoinItems("(", ")", ",")
        );

        return key;
    }

    // No longer used - refer to EDIT 3
    private UInt64 Hash(string key)
    {
        UInt64 hashedValue = 3074457345618258791ul;

        for (int i = 0; i < key.Length; i++)
        {
            hashedValue += key[i];
            hashedValue *= 3074457345618258799ul;
        }

        return hashedValue;
    }
}

Considerations:

The key needs namespace, full type name, generics and all the property values to ensure uniqueness.
String.Format() essentially implements a StringBuilder, so this should be the most efficient way of building strings.
I got the hashing from this post (Knuth hash?), which is faster than my own previous implementations.

Can anyone spot any evident performance improvements that can be made?

EDIT:

Another consideration, based on David and Patryk's comments, is that I cannot hard code the "type" string. The performance improvements need to be backwards compatible. I have to work with reflection.

EDIT 2:

Sorry, the hash methods are meant to return UInt64. Code fixed.

EDIT 3:

Storing the hashed key vs the friendly key has made no difference in performance. Thus, I am moving to the only using GetFriendly(). Thanks usr.

Your `Hash` function returns a string. If you're going to use a string as they key, then just use the original unhashed string: `MySystem.MyProject.MyNamespace.MyClass.SomeMethod(44,6948)`. That said, I think your bottleneck is probably in `GetFriendlyKey()`. I can't see your profiling screenshot. Would hard-coded strings with parameters appended help any? — David Crowell, Oct 08 '14 at 14:27
Oh, and 10,000 lookups in one API call tells me you need some kind of context storage to minimize that. Caching should mostly be _between_ calls. — David Crowell, Oct 08 '14 at 14:28
@DavidCrowell: What do you mean "Caching should mostly be between calls."? Perhaps I wasn't clear, but this is application-level caching, not web/http caching. — Dave New, Oct 08 '14 at 14:38
If you're recalling a cached value 10,000 times in one API call, you'd be better off storing that value in a variable for the duration of the call. `HttpContext.Current` comes to mind. If you need it in a different call (different or same client), then, yes, retrieving from cache is the answer. Either way, your caching mechanism is too slow - probably due to reflection. — David Crowell, Oct 08 '14 at 14:44
@DavidCrowell: I wasn't clear then - apologies. I am not calling the same item 10,000 items. It is that there could be 10,000 different items retrieved. — Dave New, Oct 08 '14 at 14:47
Edited post - Unfortunately I cannot use the "hard coded" string idea. I have to work with reflection. — Dave New, Oct 08 '14 at 14:48
Why does the result of Hash not match the format you gave as an example (a Guid)? — usr, Oct 08 '14 at 14:49
My other questions remain open. Does the hash have to be a UInt64, for example? — usr, Oct 08 '14 at 14:57
I can't understand how it's supposed to work. The method invocation signature is rebuilt as string, hashed, and used as key ... but what's the value ? — Alex, Oct 08 '14 at 15:04
@usr: No, it doesn't need to be UInt64. In fact, I have just tried without the hashing, and the performance is the same (even as a string). My guess is that it is rehashed anyway. Post edited. — Dave New, Oct 08 '14 at 15:07

score 2 · Accepted Answer · answered Oct 08 '14 at 15:04

It looks like your using PostSharp. Their own example for caching generates the method name as a string at compile time.

It seems you could get the fully-qualified type name at the same time. This would allow the expensive reflection only to occur at compile time.

public override void CompileTimeInitialize(MethodBase method, AspectInfo aspectInfo)
{
    _methodName = method.Name;
    _typeName = method.Binding.GetType().Namespace...  ..Name; // etc
}

I would also try the StringBuilder.Append() vs string.Format() and see if there's a peformance difference.

Fantastic. This makes a significant difference. – Dave New Oct 08 '14 at 17:55 — Dave New, Oct 08 '14 at 17:55

Building a Cache Key quickly

1 Answers1