CODEWITHSUNDEEP
c#performancetemplatesgenericslinked-list
BigBug
BigBug

Reputation: 6290

Insertion Speed in LinkedList

While performance testing, I noticed something interesting.

I noticed that the very first insertion into a LinkedList(C# Generics) is extremely slower than any other insertion done at the head of the list. I simply used the C# template LinkedList and used AddFirst() for each insertion into the LinkedList. Why is the very first insertion the slowest?

First Five Insertion Results:

First insertion into list: 0.0152 milliseconds

Second insertion into list(at head): 0.0006 milliseconds

Third insertion into list(at head): 0.0003 milliseconds

Fourth insertion into list(at head): 0.0006 milliseconds

Fifth insertion into list(at head): 0.0006 milliseconds

Performance Testing Code:

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

Upvotes: 0

Views: 275

Answers (1)

Jon Skeet
Jon Skeet

Reputation: 1500625

Timing a single operation is very dangerous - the slightest stutter can make a huge difference in results. Additionally, it's not clear that you've done anything with LinkedList<T> before this code, which means you'd be timing the JITting of AddFirst and possibly even whole other types involved.

Timing just the first insert is rather difficult as once you've done it, you can't easily repeat it. However, you can time "insert and remove" repeatedly, as this code does:

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

My results:

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

This is what I'd expect, as depending on the internal representation there's very slightly more work to do in terms of hooking up the "previous head" when adding and removing to an already-populated list.

My guess is you're seeing JIT time, but really your code doesn't really time accurately enough to be useful, IMO.

Upvotes: 3

Related Questions