Alternate Dictionary Lookup
08/08/2024
4 minutes
This blog post is based on .NET 9 Preview 6. Bits and pieces of the underlying runtime will change for the final release.
In .NET9 a new extension method on Dictionary type allows creating an alternate lookup type for the dictionary. This is particularly useful for dictionaries that have a string key, as the alternate lookup allows an alternate type to be used for lookups in the dictionary, for example ReadOnlySpan<char>.
Most sets and dictionaries (immutable, frozen, etc.) support this new API. However, not all dictionaries support the alternate lookup equally. Some only support certain types as alternates. Hence, there is a second extension method TryGetAlternateLookup, which does not throw when the requested alternate type is not supported.
How to lookup an alternate key?
In the early previews a comparer must be passed to the dictionary instance, that will be used later for the alternate lookups:
var _dictionary = new Dictionary<string, string>(StringComparer.Ordinal) { { "firstKey", "someValue" }, { "secondKey", "someOtherValue" } };
In the above case I choose StringComparer.Ordinal for regular case sensitive comparison.
Then the code can request the alternate lookup, for example to look up values based ReadOnlySpan<char> keys:
var alternate = _dictionary.GetAlternateLookup<string, string, ReadOnlySpan<char>>();
The type of alternate is Dictionary<TKey, TValue>.AlternateLookup<TAlternateKey>, which is an inner struct type of Dictionary<K,V>. The comparers used for alternate lookups are specialized, implementing a new interface, IAlternateEqualityComparer<in TAlternate, T>. These comparers support comparing two objects that are not necessarily the same type. This new interface also allows ref structs as the generic type parameters, allowing Span<T> and ReadOnlySpan<T> types used for the comparison.
As Span<T> and ReadOnlySpan<T> types become more ubiquitous many algorithms can benefit with the new APIs in high performance scenarios. For example, given a larger input string, a slice (ReadOnlySpan<char>) of this input can be used as a key for a dictionary lookup. That means avoiding possible allocations otherwise done by the substring operation.
When is it worth using it?
Creating an alternate lookup incurs a cost. This cost may change by the final release of .NET9. On my machine this is ~18ns. When the input is a Span<char> or ReadOnlySpan<char> a regular string lookup in a Dictionay<string, T> must call ToString() in the look up string key. In such cases a regular cost of a lookup is ~11ns, which means the alternate lookup worth creating when there are at least 2-3 keys to be looked up:
| Method | Mean | Error | StdDev | Gen0 | Allocated | |----------------------- |---------:|---------:|---------:|-------:|----------:| | RegularLookupByString | 11.82 ns | 0.232 ns | 0.206 ns | 0.0064 | 40 B | | RegularLookupBySpan | 13.81 ns | 0.272 ns | 0.280 ns | 0.0063 | 40 B | | AlternativeLookup | 30.98 ns | 0.306 ns | 0.256 ns | 0.0127 | 80 B | | AlternativeLookup3 | 28.52 ns | 0.575 ns | 0.538 ns | - | - | | RegularLookupByString3 | 33.36 ns | 0.570 ns | 0.533 ns | 0.0191 | 120 B |
The above table shows an early benchmark of this feature. The input is a string that contains segment to be used as a key for the dictionary lookup. Each implementation needs to create a slice/substring in the corresponding benchmark. The regular lookup by string (RegularLookupByString) input uses the Substring method for this and the benchmarks takes ~11ns. This also means a new string is allocated by the Substring operation, hence the 40 bytes allocated on the heap.
RegularLookupBySpan still looks up the key as a string, but instead of using Substring, it converts the input to a ReadOnlySpan<char>, slices it, and then calls ToString().
AlternativeLookup uses a slice of the input as a span for the lookup.
AlternativeLookup3 and RegularLookupByString3 repeat the lookup 3 times. AlternativeLookup3 creates an AlternateLookup only once and uses that for the 3 search operations. RegularLookupByString3 needs to call ToString() 3 times for each lookup (assuming each lookup key is going to be different).
Conclusion
The alternate lookup APIs provide an allocation free way to lookup keys in a dictionary with an alternative type. While the main usage is very likely to be looking up ReadOnlySpan<char> keys in a Dictionary<string, V> objects, the design is generic enough to support custom comparers as well, something that I might explore in a future blog post.
This post limited the investigation to Dictionary<K,V> types storing only a few items (dictionaries can use a different strategy to store items when key collisions are frequent). This early preview version of .NET shows that the alternate lookups for Dictionary provides a promising solution for allocation free searches with Span and ReadOnlySpan types. However, when the search keys match exactly the keys of the dictionary, using the alternate lookup is an overhead.