. NET 9 中的 Alternate Lookup
. NET 9 中的 Alternate Lookup
. NET 9 中的 Alternate Lookup
Intro
在 .NET 9 中，为哈希表类引入了一种名为GetAlternateLookup<TKey, TValue, TAlternate>() 的新方法，包括Dictionary<TKey, TValue>、HashSet<T>、ConcurrentDictionary<TKey, TValue>、FrozenDictionary<TKey, TValue> 和FrozenSet<TKey, TValue>。
在哪种情况下，备用查找可以提高性能？
备用键的主要用例是当TKey 是字符串时。在这种情况下，字符串通常表示为ReadOnlySpan<char>。以前，要在哈希表中查找由ReadOnlySpan<char> 表示的键，必须使用ToString() 方法将其转换为字符串，这会导致字符串分配。这不是最佳选择。
Alternate Lookup
通过引入AlternateLookup<ReadOnlySpan<char>> 结构，我们可以直接使用ReadOnlySpan<char> 作为键，避免不必要的分配。
var dico = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase) {
{ "Paul", },
{ "John", },
{ "Jack", }
};
// .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> 是嵌套在Dictionary<TKey, TValue> 中的public readonly struct。它使用C# 13.0 新引入的泛型反约束功能allows ref struct 进行定义，这使TAlternateKey 成为诸如ReadOnlySpan<T> 之类的 ref struct。
public readonly struct AlternateLookup<TAlternateKey>
where TAlternateKey : notnull, allows ref struct
从 .NET 8 开始，扩展方法Split<T> 让我们获得一个SpanSplitEnumerator<T>，它也是一个 ref struct。
public static SpanSplitEnumerator<T> Split<T>(
this ReadOnlySpan<T> source, T separator)
Benchmarking Alternate Lookup
以下是使用ReadOnlySpan<char> 进行替代查找与使用字符串进行常规查找的基准测试结果。替代查找版本的性能有所提升，并且无需分配：所有数据操作都在栈上处理 — 太酷了！
| 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 |
benchmark 代码如下：
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))]
publicclassBenchmarks {
private Dictionary<string, int> _Dico = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase)
{ { "Paul", }, { "John", }, { "Jack", } };
conststring _Names = "jack ; paul;john ";
[Params(100, 1_000, 10_000)]
publicint 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 =;
for (int i = ; 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 = ;
for (int i = ; 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;
}
}
publicclassFastRunConfig : ManualConfig {
public FastRunConfig() {
AddJob(Job.Default
.WithIterationTime(TimeInterval.Second) // Time for each iteration in milliseconds
.WithLaunchCount() // Number of times the benchmark process is launched
.WithWarmupCount() // Number of warmup iterations
.WithIterationCount()); // Number of actual iterations
}
}
Alternate Lookup key 如何与StringComparer 一起工作？
在上面的代码示例中，我们使用了StringComparer.OrdinalIgnoreCase。如果我们反编译该类的 .NET 9 版本，我们可以看到比较器类实现了新的接口IAlternateEqualityComparer<in TAlternate, T>：
internal sealed class OrdinalIgnoreCaseComparer :
OrdinalComparer, IAlternateEqualityComparer<ReadOnlySpan<char>, string?>, ISerializable
接口定义如下：
namespace System.Collections.Generic {
publicinterfaceIAlternateEqualityComparer<inTAlternate, T>
whereTAlternate : allowsrefstruct
whereT : allowsrefstruct {
T Create(TAlternate alternate);
bool Equals(TAlternate alternate, T other);
int GetHashCode(TAlternate alternate);
}
}
因此，OrdinalIgnoreCaseComparer 实现提供了与ReadOnlySpan<char> 配合使用的Equals() 和GetHashCode() 方法。
AlternateLookup<T> 结构允许修改底层字典。它具有public bool TryAdd(TAlternateKey key, TValue value) 等方法。这些修改操作调用方法IAlternateEqualityComparer.Create() 从ReadOnlySpan<char> 获取字符串对象。这样，它们就可以从备用键在字典中插入新条目。
如果创建哈希表时提供的比较器未实现IAlternateEqualityComparer<in TAlternate, T>，则在调用方法GetAlternateLookup() 时会在运行时抛出异常。
构建我们自己的 alternate lookup
这是一个小示例程序，演示了所有内容如何协同工作。我们有一个以人员对象为索引的字典，每个人员都有一个用于索引的ID。这个例子展示了我们如何仅使用人员的ID进行查找，这在人员对象不可用时非常有用。 需要注意的是，Create() 实现无法通过其ID检索到人员对象，因此不应使用查找来修改字典。值得考虑的是添加一个GetAlternateReadOnlyLookup() 方法，以有效处理无法从其替代版本检索键的情况所带来的潜在好处。
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, },
{ paul, },
{ jack, }
};
Assert.IsTrue(dico[paul] == );
// 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] == );
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);
internalclassPersonComparer : IEqualityComparer<Person>, IAlternateEqualityComparer<Guid, Person> {
private PersonComparer() { }
internalstatic 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
thrownew NotImplementedException();
}
}
publicclassPerson {
public Person(string firstName, string lastName) {
FirstName = firstName;
LastName = lastName;
}
publicstring FirstName { get; }
publicstring LastName { get; }
public Guid Id { get; } = Guid.NewGuid();
}
internalstaticclassAssert {
internal static void IsTrue(bool value) { Debug.Assert(value); }
internal static void IsFalse(bool value) { Debug.Assert(!value); }
}
结论
使用 .NET 9，可以利用Span<T> 来提高性能的场景更多，避免堆分配并直接在堆栈上操作。这种方法不仅可以减少内存开销，还可以显著提高执行速度，使其成为高性能应用程序的必备工具。
腾讯云开发者
