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]!
dictionary performance optimisation dotnet open-source🙏🙏🙏
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 Bluesky! 🦋
Leave a comment
Comments are moderated, so there may be a short delays before you see it.
Published