In .NET 9, a new method called GetAlternateLookup<TKey, TValue, TAlternate>() has been introduced for hash tables classes, including Dictionary<TKey, TValue>, HashSet<T>, ConcurrentDictionary<TKey, TValue>, FrozenDictionary<TKey, TValue>, and FrozenSet<TKey, TValue>.
In which scenario can an alternate lookup improve performance?
The primary use case for an alternate key arises when TKey is a string. In such cases, strings are often represented as ReadOnlySpan<char>. Previously, to lookup a key represented by a ReadOnlySpan<char> in a hash table, it was necessary to convert it to a string using the ToString() method, which results in a string allocation. That is not optimal.
Alternate Lookup: Code Sample C# 13.0 .NET 9.0
With the introduction of the AlternateLookup<ReadOnlySpan<char>> struct, we can directly use ReadOnlySpan<char> as a key, avoiding unnecessary allocations.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
var dico = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase) { { "Paul", 11 }, { "John", 22 }, { "Jack", 33 } }; // .NET 9 : GetAlternateLookup() Dictionary<string, int>.AlternateLookup<ReadOnlySpan<char>> lookup = dico.GetAlternateLookup<ReadOnlySpan<char>>(); // https://learn.microsoft.com/en-us/dotnet/api/system.memoryextensions.split?view=net-8.0 string names = "jack ; paul;john "; MemoryExtensions.SpanSplitEnumerator<char> ranges = names.AsSpan().Split(';'); foreach (Range range in ranges) { ReadOnlySpan<char> key = names.AsSpan(range).Trim(); int val = lookup[key]; Console.WriteLine(val); } |
AlternateLookup<T>is apublic readonly structnested inDictionary<TKey, TValue>. It is defined using the new C# 13.0 generic anti-constraint featureallows ref structthat we explained in this post: C# 13 ref struct interfaces and the ‘allows ref struct’ generic anti-constraint. This enablesTAlternateKeyto be aref structsuch asReadOnlySpan<T>.
|
1 2 |
public readonly struct AlternateLookup<TAlternateKey> where TAlternateKey : notnull, allows ref struct |
- Since .NET 8 the extension method
Split<T>let’s obtain aSpanSplitEnumerator<T>which is also a ref struct.
|
1 2 |
public static SpanSplitEnumerator<T> Split<T>( this ReadOnlySpan<T> source, T separator) |
Benchmarking Alternate Lookup
Here is the result of benchmarking alternate lookup with ReadOnlySpan<char> versus regular lookup with string. The alternate lookup version delivers a performance boost and zero allocations: all data operations are handled on the stack—how cool!
|
1 2 3 4 5 6 7 8 |
| Method | Count | Mean | Allocated | |--------------------------------- |------ |-------------:|----------:| | AlternateLookup_WithReadOnlySpan | 100 | 9.477 us | - | | RegularLookup_WithString | 100 | 11.579 us | 9600 B | | AlternateLookup_WithReadOnlySpan | 1000 | 105.244 us | - | | RegularLookup_WithString | 1000 | 114.465 us | 96000 B | | AlternateLookup_WithReadOnlySpan | 10000 | 1,087.653 us | - | | RegularLookup_WithString | 10000 | 1,153.590 us | 960000 B | |
Here is the benchmark code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
using BenchmarkDotNet.Attributes; using BenchmarkDotNet.Configs; using BenchmarkDotNet.Jobs; using BenchmarkDotNet.Running; using Perfolizer.Horology; BenchmarkRunner.Run<Benchmarks>(); [MemoryDiagnoser] [HideColumns("StdDev", "Median", "Job", "RatioSD", "Error", "Gen0", "Alloc Ratio")] [Config(typeof(FastRunConfig))] public class Benchmarks { private Dictionary<string, int> _Dico = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase) { { "Paul", 11 }, { "John", 22 }, { "Jack", 33 } }; const string _Names = "jack ; paul;john "; [Params(100, 1_000, 10_000)] public int Count { get; set; } [Benchmark] public int AlternateLookup_WithReadOnlySpan() { Dictionary<string, int>.AlternateLookup<ReadOnlySpan<char>> lookup = _Dico.GetAlternateLookup<ReadOnlySpan<char>>(); MemoryExtensions.SpanSplitEnumerator<char> ranges = _Names.AsSpan().Split(';'); int sum =0; for (int i = 0; i < Count; i++) { foreach (Range range in ranges) { ReadOnlySpan<char> key = _Names.AsSpan(range).Trim(); int val = lookup[key]; // <--- lookup with ReadOnlySpan<char> key sum += val; } } return sum; } [Benchmark] public int RegularLookup_WithString() { MemoryExtensions.SpanSplitEnumerator<char> ranges = _Names.AsSpan().Split(';'); int sum = 0; for (int i = 0; i < Count; i++) { foreach (Range range in ranges) { string key = _Names.AsSpan(range).Trim().ToString(); // <--- .ToString() allocates a string int val = _Dico[key]; // <--- lookup with string key sum += val; } } return sum; } } public class FastRunConfig : ManualConfig { public FastRunConfig() { AddJob(Job.Default .WithIterationTime(TimeInterval.Second) // Time for each iteration in milliseconds .WithLaunchCount(1) // Number of times the benchmark process is launched .WithWarmupCount(1) // Number of warmup iterations .WithIterationCount(2)); // Number of actual iterations } } |
How does the alternate lookup key work with StringComparer?
In the code sample above we are using StringComparer.OrdinalIgnoreCase. If we decompile the .NET 9 version of this class we can see that the comparer class implements the new interface IAlternateEqualityComparer<in TAlternate, T>:
|
1 2 |
internal sealed class OrdinalIgnoreCaseComparer : OrdinalComparer, IAlternateEqualityComparer<ReadOnlySpan<char>, string?>, ISerializable |
This interface is defined this way:
|
1 2 3 4 5 6 7 8 9 |
namespace System.Collections.Generic { public interface IAlternateEqualityComparer<in TAlternate, T> where TAlternate : allows ref struct where T : allows ref struct { T Create(TAlternate alternate); bool Equals(TAlternate alternate, T other); int GetHashCode(TAlternate alternate); } } |
Therefore, the OrdinalIgnoreCaseComparer implementation provides the Equals() and GetHashCode() methods that work with ReadOnlySpan<char>.
The AlternateLookup<T> struct allows modification on the underlying dictionary. It has methods such as public bool TryAdd(TAlternateKey key, TValue value). These modify-operations call the method IAlternateEqualityComparer.Create() to obtain a string object from a ReadOnlySpan<char>. This way they can insert a new entry in the dictionary from an alternate key.
If the comparer provided when creating the hash table doesn’t implement IAlternateEqualityComparer<in TAlternate, T> an exception is thrown at runtime when calling the method GetAlternateLookup().
Building our own alternate lookup
It’s important to note that the Create() implementation cannot retrieve a person’s object from its ID, so the lookup should not be used to modify the dictionary. It’s worth considering the potential benefits of adding a GetAlternateReadOnlyLookup() method to effectively handle such scenarios where a key cannot be retrieved from its alternate version.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
using System.Diagnostics; var paul = new Person("Paul", "Due"); var john = new Person("John", "Foo"); var jack = new Person("Jack", "Bar"); var dico = new Dictionary<Person, int>(PersonComparer.Instance) { { john, 11 }, { paul, 22 }, { jack, 33 } }; Assert.IsTrue(dico[paul] == 22); // Suppose now we have access to person's id but not to person's object. // We can still search within dico var paulId = paul.Id; Dictionary<Person, int>.AlternateLookup<Guid> lookup = dico.GetAlternateLookup<Guid>(); Assert.IsTrue(lookup[paulId] == 22); Assert.IsFalse(lookup.ContainsKey(Guid.NewGuid())); // Cannot modify dico through lookup // because IAlternateEqualityComparer.Create() impl throws an exception // bool b = lookup.TryAdd(Guid.NewGuid(), 44); internal class PersonComparer : IEqualityComparer<Person>, IAlternateEqualityComparer<Guid, Person> { private PersonComparer() { } internal static PersonComparer Instance { get; } = new PersonComparer(); // IEqualityComparer<Person> impl public bool Equals(Person? x, Person? y) { return x != null && y != null && x.Id == y.Id; } public int GetHashCode(Person person) { return person.Id.GetHashCode(); } // IAlternateEqualityComparer<Guid, Person> impl public bool Equals(Guid id, Person person) { return id == person.Id; } public int GetHashCode(Guid id) { return id.GetHashCode(); } public Person Create(Guid id) { // In this sample, don't try to retrieve a Person object from its id throw new NotImplementedException(); } } public class Person { public Person(string firstName, string lastName) { FirstName = firstName; LastName = lastName; } public string FirstName { get; } public string LastName { get; } public Guid Id { get; } = Guid.NewGuid(); } internal static class Assert { internal static void IsTrue(bool value) { Debug.Assert(value); } internal static void IsFalse(bool value) { Debug.Assert(!value); } } |
Conclusion
With .NET 9, there are even more scenarios where Span<T> can be leveraged to enhance performance by avoiding heap allocations and operating directly on the stack. This approach not only reduces memory overhead but also significantly improves execution speed, making it an essential tool for high-performance applications.