This short post looks at an implementation of a dictionary that is optimised for keys of generic types. It uses a 'trick' which gives it far better performance than that of a normal Dictionary<Type, TValue>.

Using dictionaries that are keyed by a Type is quite common and is often used in 'hot paths', so this optimised lookup could save you precious processing time!

I discovered this neat type via a Tweet from David Fowler, where he linked to the implementation, which is part of the Proto.Actor repo (for 'Ultra-fast, distributed, cross-platform actors').

We'll see what the trick is and how it works, and run some performance benchmarks for comparison.

What's the trick #

Let's first see the difference in how we use a traditional dictionary vs. how we use the optimised dictionary:

// traditional
Dictionary<Type, string> d1 = new();
d1.Add(typeof(int), "an int!");

// optimised
TypeDictionary<string, string> d2 = new();
d2.Add<int>("an int!");

As you can see, the optimised dictionary has no <TKey> on the class declaration:

public class TypeDictionary<TValue, TNamespace>

... but does have TKey on the Add method:

public void Add<TKey>(TValue value) {
    var id = TypeKey<TKey>.Id;
    _values[id] = value;
}

Notice the use of a static type named TypeKey<TKey>. That's defined as:

private static class TypeKey<TKey> {
    internal static readonly int Id = Interlocked.Increment(ref typeIndex);
}

When Add is called, a TypedKey<TKey> is used. If that specific variant (specific to TKey) doesn't yet exist, then it is created and the static property named Id is set with an incrementing value.

So, when we call Add<int>("an int!"), the Id (TypedKey<int>.Id) is 0.
If we then call Add<double>("a double!"), the Id (TypedKey<double>.Id) is 1.

So, we have two different instances of TypeKey in memory; one of type TypeKey<int> (with an Id of 0), and one of type TypeKey<double> (with an Id of 1).

Also note that TNamespace is used to create different TypedKey types per unique TypedDictionary<T1,T2>.

Here's the good bit: when we Get a value, there is no dictionary lookup needed. To find the value, we just use the index to get the value in an array, as opposed to hashcode based lookups of the traditional dictionary:

public TValue? Get<TKey>() {
    var id = TypeKey<TKey>.Id;
    return id >= _values.Length ? default : _values[id];
}

That is is why it's faster. But by how much...

How much faster is it? #

A lot!:

Yes, they're nanoseconds, but it's still FOUR times faster. And this type of lookup (or non-lookup now!) is often used in hot paths, so the savings could be substantial.

What have we seen? #

We've seen a neat way to speed up dictionary 'lookup' by using using traits of statics in generic types. Hats off to the team at ('protoactor-dotnet')[https://github.com/AsynkronIT/protoactor-dotnet]!

🙏🙏🙏

Since you've made it this far, sharing this article on your favorite social media network would be highly appreciated 💖! For feedback, please ping me on Twitter.

Leave a comment

Comments are moderated, so there may be a short delays before you see it.

Published 27 Aug 2021