为何LinkedList与List操作基准测试结果存在异常？

问题情况 #

我在对LinkedList和List的插入操作做基准测试，理论上LinkedList的插入操作都是O(1)时间复杂度，但测试中出现了两个不符合预期的异常：

• 样本量为100时，LinkedList的中间插入操作耗时出现明显峰值（3854 ticks）
• 样本量为100000时，List的前置插入操作耗时大幅飙升（272081 ticks）
  多次运行测试都出现同样情况，就算为每个操作、每个样本量单独创建Stopwatch，结果还是不符合预期的时间复杂度规律。

测试代码 #

void ListInsertionComparison()
{
    for (var i = 100; i <= 1000000; i*=10)
    {
        var stopwatch = new Stopwatch();

        var random = new Random(12345);
        var localList = new List<int>();
        var localLinkedList = new LinkedList<int>();
        var middleNode = new LinkedListNode<int>(5);

        for (var j = 0; j < i; j++)
        {
            localList.Add(j);
            var temp = localLinkedList.AddLast(j);
            if (j == i / 2)
                middleNode = temp;
        }

        stopwatch.Reset();
        stopwatch.Start();
        localList.Insert(0,1);
        stopwatch.Stop();
        Console.WriteLine($"List Prepend: {i} {stopwatch.ElapsedTicks}");

        stopwatch.Reset();
        stopwatch.Start();
        localLinkedList.AddFirst(1);
        stopwatch.Stop();
        Console.WriteLine($"LinkedList Prepend: {i} {stopwatch.ElapsedTicks}");

        stopwatch.Reset();
        stopwatch.Start();
        localList.Insert(localList.Count/2, 1);
        stopwatch.Stop();
        Console.WriteLine($"List Insert: {i} {stopwatch.ElapsedTicks}");

        stopwatch.Reset();
        stopwatch.Start();
        localLinkedList.AddBefore(middleNode, 1);
        stopwatch.Stop();
        Console.WriteLine($"LinkedList Insert: {i} {stopwatch.ElapsedTicks}");
    }
}

测试输出结果 #

List Prepend: 100 160
LinkedList Prepend: 100 16
List Insert: 100 24
LinkedList Insert: 100 3854
List Prepend: 1000 7
LinkedList Prepend: 1000 2
List Insert: 1000 7
LinkedList Insert: 1000 11
List Prepend: 10000 12
LinkedList Prepend: 10000 2
List Insert: 10000 10
LinkedList Insert: 10000 2
List Prepend: 100000 272081
LinkedList Prepend: 100000 4
List Insert: 100000 575
LinkedList Insert: 100000 57
List Prepend: 1000000 8929
LinkedList Prepend: 1000000 6
List Insert: 1000000 3652
LinkedList Insert: 1000000 15

异常原因分析 #

1. LinkedList样本量100时的插入峰值 #

这是首次JIT编译导致的。第一次执行AddBefore方法时，.NET运行时需要把该方法的IL代码编译成机器码，这个编译过程的额外耗时被计入了首次测试的tick数。后续测试时方法已经完成编译，耗时就回归到正常的O(1)水平了。

2. List样本量100000时的前置插入峰值 #

List底层是数组，前置插入需要把所有元素向后移动一位，时间复杂度是O(n)。这个量级下的峰值主要是：

• 移动100000个元素的操作本身就会产生可观耗时，只是小样本量时不明显；
• 可能叠加了内存页缓存未命中的情况，或者刚好触发了垃圾回收，进一步拉高了耗时。

测试优化建议 #

• 预热代码：正式测试前先完整跑一遍所有操作，触发JIT编译，避免首次编译的干扰；
• 多次取平均：每个操作重复执行几十上百次，取平均耗时，减少单次测试的偶然波动；
• 隔离测试：把前置插入、中间插入等操作分开测试，避免不同操作之间的状态影响。

内容的提问来源于stack exchange，提问作者Daar