插入速度在LinkedList

Question

在进行性能测试时，我注意到一些有趣的事情。

我注意到第一次插入到LinkedList(c#泛型)中比在列表开头插入任何其他插入都要慢得多。我只是简单地使用c#模板LinkedList，并在每次插入到LinkedList时使用AddFirst()。为什么第一次插入是最慢的?

---

前五插入结果:

第一次插入列表:0.0152毫秒

第二次插入列表:0.0006毫秒

第三次插入到list(at head): 0.0003毫秒

第4次插入到list(at head): 0.0006毫秒

第五次插入到list(at head): 0.0006毫秒

性能测试代码:

        using (StreamReader readText = new StreamReader("MillionNumbers.txt"))
        {
            String line;
            Int32 counter = 0; 
            while ((line = readText.ReadLine()) != null)
            {
                watchTime.Start();
                theList.AddFirst(line);
                watchTime.Stop();
                Double time = watchTime.Elapsed.TotalMilliseconds;
                totalTime = totalTime + time; 
                Console.WriteLine(time);
                watchTime.Reset();
                ++counter; 
            }
            Console.WriteLine(totalTime);
            Console.WriteLine(counter);
            Console.WriteLine(totalTime / counter); 
        }

Answer 1

对单个操作进行计时是非常危险的——最轻微的停顿可能会导致结果的巨大差异。此外，不清楚在此代码之前您是否对LinkedList<T>做了任何操作，这意味着您将对AddFirst的jit进行计时，甚至可能涉及到整个其他类型。

对第一次插入计时是相当困难的，因为一旦完成了，就不容易重复。但是，您可以重复地计时"插入和删除"，就像下面的代码所做的那样:

using System;
using System.Collections.Generic;
using System.Diagnostics;
class Program
{
    public static void Main(string[] args)
    {
        // Make sure we've JITted the LinkedList code
        new LinkedList<string>().AddFirst("ignored");
        LinkedList<string> list = new LinkedList<string>();        
        TimeInsert(list);
        list.AddFirst("x");
        TimeInsert(list);
        list.AddFirst("x");
        TimeInsert(list);
        list.AddFirst("x");        
    }
    const int Iterations = 100000000;
    static void TimeInsert(LinkedList<string> list)
    {
        GC.Collect();
        GC.WaitForPendingFinalizers();
        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < Iterations; i++)
        {
            list.AddFirst("item");
            list.RemoveFirst();
        }
        sw.Stop();
        Console.WriteLine("Initial size: {0}; Ticks: {1}",
                           list.Count, sw.ElapsedTicks);
    }
}

我结果:

Initial size: 0; Ticks: 5589583
Initial size: 1; Ticks: 8137963
Initial size: 2; Ticks: 8399579

这是我所期望的，因为根据内部表示，在向已经填充的列表添加和删除时，在连接"前一个头"方面要做的工作稍微多一点。

我猜你看到的是JIT时间，但实际上你的代码没有真正精确到足够有用，在我看来