Why are these LinkedList's and List's operation benchmarks off?

Question

I'm trying to do a simple benchmark comparing a few operations on a LinkedList and a List. The LinkedList operations are all supposed to be O(1), yet I'm getting a significant spike when doing a LinkedList insert at sample size 100. Also, the List has a big spike when doing the prepend at sample size of 100,000. Is it that the Stopwatch is just unreliable at such low tick values and spikes every now and then? I've ran this several times now, and always getting these flukes.

I've also tried creating a new Stopwatch for each of the operations, for each sample size, but not getting the expected time complexities either.

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

If you want to run benchmarks I recommend using [Benchmark.Net](https://www.nuget.org/packages/BenchmarkDotNet) rather than trying to write your own — stuartd, Jan 15 '23 at 00:18

score 2 · Answer 1 · edited Jan 23 '23 at 11:26

First of all use proper benchmarking tools/techniques. For example Benchmark.Net, mentioned in the comments. I highly suspect that this will "solve" at least part of your question.

Is it that the Stopwatch is just unreliable at such low tick values and spikes every now and then?

It is not Stopwatch. Or not just Stopwatch (if I remember correctly it has some problems in context of microbenchmarking).

The LinkedList operations are all supposed to be O(1), yet I'm getting a significant spike when doing a LinkedList insert at sample size 100.

Which does not prove in any way that LinkedList is not O(1). Potentially the "spike" is affected by how .NET works. Note that there is another correlation - the "100 case" seems to be the first invocation of the method in your application - so the invocation time can be affected by the JIT.

Also, the List has a big spike when doing the prepend at sample size of 100,000.

This one is harder to explain. If it is consistent one - my guess would be that either you have hit the sweet point when adding one element triggers the need to resize it and/or GC happens (though GC should not be consistent). To mitigate that try to create list of needed size beforehand:

var localList = new List<int>(i + 2);

Again - use appropriate library, they should handle warm up (so JIT is no the factor, because it can actually recompile method several times) and at least partially mitigate the GC (you can also try with GC.Collect),

Why are these LinkedList's and List's operation benchmarks off?

1 Answers1