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

Question

在优化网站时，我尝试使用 Benchmark.Net 对代码进行基准测试。但我惊讶地发现一些基准测试代码使用的内存多了 40,000 倍。经过太多的基准测试后，我发现内存分配是由于对 SortedList<int, int> 进行 foreach 造成的。

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;
        }
    }
}

即使循环中没有 TryGetValue()，在 SortedList 上使用 foreach() 的基准方法使用的内存也比其他方法多 40,000 倍。

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

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

Answer 1

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

正如 Hans Passant 指出的，4.8 中 SortedList<> 中的 Enumerator 是一个类。但我已经看过了，.NET 6 中的 Enumerator 已更改为 struct，并且根据 git 至少自 2016 年以来一直是一个 struct。但它仍然分配在堆上。

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

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

GetEnumerator()在SortedList<>：

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

GetEnumerator()在Dictionary<>：

public Enumerator GetEnumerator()

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

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