.NET9 实现排序算法（MergeSortTest 和 QuickSortTest）性能测试

在 .NET 9 平台下，我们对两种经典的排序算法 MergeSortTest（归并排序）和 QuickSortTest（快速排序）进行了性能基准测试（Benchmark），以评估它们在不同数据规模下的执行效率、内存分配及垃圾回收行为。

测试使用了 BenchmarkDotNet 工具，确保结果具有高度可重复性和统计意义。

• Datadog.Trace.BenchmarkDotNet

🧪 测试环境

• 运行时（Runtime）：.NET 9.0.6 (X64 RyuJIT AVX2)
• 操作系统：Windows 11 24H2（开发预览版）
• SDK 版本：.NET SDK 9.0.301
• 测试工具：BenchmarkDotNet v0.15.2
• 测试参数：
  • 数据量 N = 100, 1000, 10000（分别模拟小、中、大数据集）

项目准备

创建项目

使用 .net cli 创建控制台项目，执行如下命令：

dotnet new console -n SortTestcd SortTest# 安装 nuget 包 Datadog.Trace.BenchmarkDotNetdotnet add package Datadog.Trace.BenchmarkDotNet

控制台项目 SortTest.csproj 信息如下：

<Project Sdk=\"Microsoft.NET.Sdk\"> <PropertyGroup> <OutputType>Exe</OutputType> <TargetFramework>net9.0</TargetFramework> <ImplicitUsings>enable</ImplicitUsings> <Nullable>enable</Nullable> <PublishAot>true</PublishAot> <InvariantGlobalization>true</InvariantGlobalization> </PropertyGroup> <ItemGroup> <PackageReference Include=\"Datadog.Trace.BenchmarkDotNet\" Version=\"2.61.0\" /> </ItemGroup></Project>

排序算法实现

• 归并排序

// =============================// 排序算法实现：归并排序// =============================namespace SortTest;public class MergeSort{ public static void Sort(int[] array) { if (array.Length <= 1) return; int mid = array.Length / 2; int[] left = array[..mid]; int[] right = array[mid..]; Sort(left); Sort(right); Merge(array, left, right); } private static void Merge(int[] result, int[] left, int[] right) { int i = 0, j = 0, k = 0; while (i < left.Length && j < right.Length) { if (left[i] <= right[j]) result[k++] = left[i++]; else result[k++] = right[j++]; } while (i < left.Length) result[k++] = left[i++]; while (j < right.Length) result[k++] = right[j++]; }}

• 快速排序

// =============================// 排序算法实现：快速排序// =============================namespace SortTest;public class QuickSort{ public static void Sort(int[] array, int low, int high) { if (low < high) { int pivotIndex = Partition(array, low, high); Sort(array, low, pivotIndex - 1); Sort(array, pivotIndex + 1, high); } } private static int Partition(int[] array, int low, int high) { int pivot = array[high]; int i = low - 1; for (int j = low; j < high; j++) { if (array[j] <= pivot) { i++; Swap(array, i, j); } } Swap(array, i + 1, high); return i + 1; } private static void Swap(int[] array, int i, int j) { if (i != j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } }}

添加测试基准

• Benchmark 测试类

// =============================// Benchmark 测试类// =============================using BenchmarkDotNet.Attributes;using Datadog.Trace.BenchmarkDotNet;namespace SortTest;[DatadogDiagnoser][MemoryDiagnoser]public class SortingBenchmark{ private int[] data = []; [Params(100, 1000, 10000)] // 不同数据规模 public int N; [GlobalSetup] public void Setup() { var random = new Random(42); // 固定种子以保证重复性 data = Enumerable.Range(0, N).Select(_ => random.Next(0, N)).ToArray(); } [Benchmark] public void MergeSortTest() { var copy = (int[])data.Clone(); MergeSort.Sort(copy); } [Benchmark] public void QuickSortTest() { var copy = (int[])data.Clone(); QuickSort.Sort(copy, 0, copy.Length - 1); }}

使用基准测试

在 Program.cs 添加如下代码：

using BenchmarkDotNet.Configs;using BenchmarkDotNet.Running;using Datadog.Trace.BenchmarkDotNet;namespace SortTest;internal class Program{ static void Main(string[] args) { Console.WriteLine(\"Hello, SortingBenchmark!\"); var config = DefaultConfig.Instance .WithDatadog(); BenchmarkRunner.Run<SortingBenchmark>(config); }}

启动项目基准测试，使用 pwsh 执行如下命令：

dotnet run -c Release

下面这些文本信息是使用 BenchmarkDotNet 工具对两种排序算法（MergeSortTest 和 QuickSortTest）进行性能测试后生成的报告。

---

BenchmarkDotNet v0.15.2, Windows 11 (10.0.26100.4484/24H2/2024Update/HudsonValley)Unknown processor.NET SDK 9.0.301 [Host] : .NET 9.0.6 (9.0.625.26613), X64 AOT AVX2 DefaultJob : .NET 9.0.6 (9.0.625.26613), X64 RyuJIT AVX2

Method N Mean Error StdDev Gen0 Gen1 Allocated MergeSortTest 100 4.508 μs 0.0857 μs 0.1863 μs 5.3635 - 8424 B QuickSortTest 100 1.249 μs 0.0248 μs 0.0331 μs 0.2689 - 424 B MergeSortTest 1000 79.005 μs 1.5793 μs 2.1083 μs 61.4014 - 96328 B QuickSortTest 1000 39.192 μs 0.6847 μs 0.6404 μs 2.5024 - 4024 B MergeSortTest 10000 1,073.318 μs 20.7670 μs 26.2637 μs 539.0625 128.9063 1112040 B QuickSortTest 10000 600.722 μs 7.9013 μs 6.5980 μs 24.4141 - 40024 B

---

以下是关键内容的通俗解释：

📊 测试目标

对两种排序算法在不同数据量下的性能进行对比分析，包括：

• 执行时间（Mean）
• 内存分配（Allocated）
• 垃圾回收情况（Gen0, Gen1）

测试分别在以下数据规模下运行：

• N = 100
• N = 1000
• N = 10000

---

🧪 性能对比结果

方法 数据量 (N) 平均耗时 内存分配 GC 次数 (Gen0) MergeSortTest 100 4.508 μs 8424 B 5.3635 QuickSortTest 100 1.249 μs 424 B 0.2689 MergeSortTest 1000 79.005 μs 96328 B 61.4014 QuickSortTest 1000 39.192 μs 4024 B 2.5024 MergeSortTest 10000 1073.318 μs 1112040 B 539.0625 QuickSortTest 10000 600.722 μs 40024 B 24.4141

✅ 结论：

• QuickSortTest 的平均耗时和内存占用都明显低于 MergeSortTest
• 随着数据量增加，两者的差距也越来越大
• QuickSortTest 在性能和资源消耗方面更优

---

⚠️ 警告与提示

📌 多峰分布警告（Multimodal Distribution）

• MergeSortTest 的部分测试结果显示为多峰分布（mValue = 3.23），说明其运行时间波动较大，可能受外部因素影响。

📌 异常值（Outliers）

• 报告中指出某些测试存在异常值并已被剔除：
  • MergeSortTest: 移除了 4 个异常值
  • QuickSortTest: 不同数据规模下检测到多个异常值并移除

---

📋 统计指标含义简述

指标名 含义解释 Mean 平均执行时间 Error 置信区间的一半（99.9% 置信度） StdDev 标准差，反映数据波动程度 Gen0 / Gen1 垃圾回收次数（代数0/1） Allocated 单次操作分配的内存大小 Median 中位数，排除极端值后的中间值 Min / Max 最小值和最大值

---

🖼️ 直方图（Histogram）

每组测试后都有一个简单的直方图，用字符 @ 表示不同时间段内执行次数的分布，帮助可视化执行时间的集中趋势。

---

📈 小结

• QuickSortTest 在所有测试中表现更优
  • 更快的执行速度
  • 更少的内存分配
  • 更低的垃圾回收压力
• MergeSortTest 性能较差且波动较大
  • 特别是在大数据量（N=10000）时表现不佳
  • 存在较多异常值，稳定性不如 QuickSort

---

如果你希望进一步优化 MergeSort 或想了解为何它表现不佳，可以结合代码逻辑、递归深度、内存使用等因素进行深入分析。