为什么SortedList上的foreach()与Dictionary相比内存如此昂贵

Question

在优化网站时，我尝试使用benchmark对代码进行基准测试。网但我惊讶地发现，一些基准代码使用的内存是原来的40000倍。在进行了太多的基准测试之后，我发现内存分配是因为在SortedList<int，int>。

using BenchmarkDotNet.Attributes;
namespace NetCollectionsBenchmarks
{
[MemoryDiagnoser]
public class CollectionsBenchmarks
{
private Dictionary<int, int> DictionaryData = new();
private SortedList<int, int> SortedListData = new();
private Dictionary<int, int> DictionaryCheck = new();
private SortedList<int, int> SortedListCheck = new();
[GlobalSetup]
public void Setup()
{
for (int x = 0; x < 15; x++)
this.DictionaryData.Add(x, x);
this.SortedListData = new SortedList<int, int>(this.DictionaryData);
this.DictionaryCheck = new Dictionary<int, int>(this.DictionaryData);
this.SortedListCheck = new SortedList<int, int>(this.DictionaryData);
}
[Benchmark(Baseline = true)]
public long ForLoopDictionaryBenchmark()
{
var count = 0L;
var res = 0L;
for (int x = 0; x < 1_000_000; x++)
{
for (int i = 0; i < 15; i++)
{
if (this.DictionaryCheck.TryGetValue(x, out var value) || value < x)
res += value;
count++;
}
}
return res;
}
[Benchmark]
public long ForLoopSortedListBenchmark()
{
var res = 0L;
for (int x = 0; x < 1_000_000; x++)
{
for (int i = 0; i < 15; i++)
{
if (this.SortedListCheck.TryGetValue(x, out var value) || value < x)
res += value;
}
}
return res;
}
[Benchmark]
public long ForeachDictionaryBenchmark()
{
var res = 0L;
for (int x = 0; x < 1_000_000; x++)
{
foreach (var needle in this.DictionaryData)
{
if (this.DictionaryCheck.TryGetValue(needle.Key, out var value) || value < needle.Value)
res += value;
}
}
return res;
}
[Benchmark]
public long ForeachSortedListBenchmark()
{
var res = 0L;
for (int x = 0; x < 1_000_000; x++)
{
foreach (var needle in this.SortedListData)
{
if (this.SortedListCheck.TryGetValue(needle.Key, out var value) || value < needle.Value)
res += value;
}
}
return res;
}
[Benchmark]
public long ForeachNoTryGetValueDictionaryBenchmark()
{
var res = 0L;
for (int x = 0; x < 1_000_000; x++)
{
foreach (var needle in this.DictionaryData)
{
}
}
return res;
}
[Benchmark]
public long ForeachNoTryGetValueSortedListBenchmark()
{
var res = 0L;
for (int x = 0; x < 1_000_000; x++)
{
foreach (var needle in this.SortedListData)
{
}
}
return res;
}
}
}

在SortedList上使用foreach()的基准测试方法使用的内存是其他方法的40000倍，即使循环中没有TryGetValue()。

为什么SortedList在循环其枚举器时内存如此昂贵？

基准测试已经在中进行了测试。NET 6.0和。NET 7.0，结果相同。

Answer 1

由于似乎没有人知道这个问题的答案，我继续调查，试图找到原因。

正如Hans-Passant所指出的，SortedList<gt；4.8是一个班。但我已经看过了，还有里面的枚举器。NET 6已更改为struct，根据git的说法，它至少从2016年起就是一个struct。但它仍然是在堆上分配的。

由于SortedList<>Enumerator自2016年以来一直是一个结构，因此该代码不可能不包含在中。NET 6(或.NET 7)。但可以肯定的是，我从git存储库中创建了自己的Dictionary<>和SortedList<>副本。结果还是一样。

当我准备更改类中的代码以找出产生差异的原因时，我发现了发散代码。在两个班中都是GetEnumerator()。

SortedList<>:中的GetEnumerator()

public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()

Dictionary<>:中的GetEnumerator()

public Enumerator GetEnumerator()

由于接口装箱，返回类型IEnumerator<KeyValuePair<TKey, TValue>>使枚举器在堆上分配。将返回类型更改为Enumerator删除了Benchmark报告的所有额外分配。NET。

关于Hans Passant的第二个注释，关于它是廉价的第0代内存。可能是这样，但在我所做的基准测试中，GetEnumerator()的当前实现所花费的时间是返回类型为Enumerator的实现的两倍。我所做的基准测试与我目前运行的生产代码非常接近。