# Alternate Dictionary Lookup

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:

```csharp
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:

```csharp
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 struct`s 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.