Performance differences... so dramatic?

Question

Just now I read some posts about List<T> vs LinkedList<T>, so I decided to benchmark some structures myself. I benchmarked Stack<T>, Queue<T>, List<T> and LinkedList<T> by adding data and removing data to/from the front/end. Here's the benchmark result:

               Pushing to Stack...  Time used:      7067 ticks               Poping from Stack...  Time used:      2508 ticks                 Enqueue to Queue...  Time used:      7509 ticks              Dequeue from Queue...  Time used:      2973 ticks      Insert to List at the front...  Time used:   5211897 ticks RemoveAt from List at the front...  Time used:   5198380 ticks           Add to List at the end...  Time used:      5691 ticks   RemoveAt from List at the end...  Time used:      3484 ticks           AddFirst to LinkedList...  Time used:     14057 ticks     RemoveFirst from LinkedList...  Time used:      5132 ticks            AddLast to LinkedList...  Time used:      9294 ticks      RemoveLast from LinkedList...  Time used:      4414 ticks 

Code:

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics;  namespace Benchmarking {     static class Collections     {         public static void run()         {             Random rand = new Random();             Stopwatch sw = new Stopwatch();             Stack<int> stack = new Stack<int>();             Queue<int> queue = new Queue<int>();             List<int> list1 = new List<int>();             List<int> list2 = new List<int>();             LinkedList<int> linkedlist1 = new LinkedList<int>();             LinkedList<int> linkedlist2 = new LinkedList<int>();             int dummy;               sw.Reset();             Console.Write("{0,40}", "Pushing to Stack...");             sw.Start();             for (int i = 0; i < 100000; i++)             {                 stack.Push(rand.Next());             }             sw.Stop();             Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);             sw.Reset();             Console.Write("{0,40}", "Poping from Stack...");             sw.Start();             for (int i = 0; i < 100000; i++)             {                 dummy = stack.Pop();                 dummy++;             }             sw.Stop();             Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);               sw.Reset();             Console.Write("{0,40}", "Enqueue to Queue...");             sw.Start();             for (int i = 0; i < 100000; i++)             {                 queue.Enqueue(rand.Next());             }             sw.Stop();             Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);             sw.Reset();             Console.Write("{0,40}", "Dequeue from Queue...");             sw.Start();             for (int i = 0; i < 100000; i++)             {                 dummy = queue.Dequeue();                 dummy++;             }             sw.Stop();             Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);               sw.Reset();             Console.Write("{0,40}", "Insert to List at the front...");             sw.Start();             for (int i = 0; i < 100000; i++)             {                 list1.Insert(0, rand.Next());             }             sw.Stop();             Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);             sw.Reset();             Console.Write("{0,40}", "RemoveAt from List at the front...");             sw.Start();             for (int i = 0; i < 100000; i++)             {                 dummy = list1[0];                 list1.RemoveAt(0);                 dummy++;             }             sw.Stop();             Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);               sw.Reset();             Console.Write("{0,40}", "Add to List at the end...");             sw.Start();             for (int i = 0; i < 100000; i++)             {                 list2.Add(rand.Next());             }             sw.Stop();             Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);             sw.Reset();             Console.Write("{0,40}", "RemoveAt from List at the end...");             sw.Start();             for (int i = 0; i < 100000; i++)             {                 dummy = list2[list2.Count - 1];                 list2.RemoveAt(list2.Count - 1);                 dummy++;             }             sw.Stop();             Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);               sw.Reset();             Console.Write("{0,40}", "AddFirst to LinkedList...");             sw.Start();             for (int i = 0; i < 100000; i++)             {                 linkedlist1.AddFirst(rand.Next());             }             sw.Stop();             Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);             sw.Reset();             Console.Write("{0,40}", "RemoveFirst from LinkedList...");             sw.Start();             for (int i = 0; i < 100000; i++)             {                 dummy = linkedlist1.First.Value;                 linkedlist1.RemoveFirst();                 dummy++;             }             sw.Stop();             Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);               sw.Reset();             Console.Write("{0,40}", "AddLast to LinkedList...");             sw.Start();             for (int i = 0; i < 100000; i++)             {                 linkedlist2.AddLast(rand.Next());             }             sw.Stop();             Console.WriteLine("  Time used: {0,9} ticks", sw.ElapsedTicks);             sw.Reset();             Console.Write("{0,40}", "RemoveLast from LinkedList...");             sw.Start();             for (int i = 0; i < 100000; i++)             {                 dummy = linkedlist2.Last.Value;                 linkedlist2.RemoveLast();                 dummy++;             }             sw.Stop();             Console.WriteLine("  Time used: {0,9} ticks\n", sw.ElapsedTicks);         }     } } 

The differences are so dramatic!

As you can see, the performance of Stack<T> and Queue<T> are fast and comparable, that's expected.

For List<T>, using the front and the end has so much differences! And to my surprise, performance of adding/removing from the end is actually comparable to the performance of Stack<T>.

For LinkedList<T>, manipulating with the front is fast (-er than List<T>), but for the end, it is incredibly slow for removing manipulating with the end is too.

---

So... can any experts account on:

1. the similarity in performance of using Stack<T> and the end of List<T>,
2. the differences in using the front and the end of List<T>, and
3. the reason that using the end of LinkedList<T> is so slow (not applicable as that is a coding error due to the use of Linq's Last(), thanks to CodesInChaos)?

I think I know why List<T> doesn't handle the front so well... because List<T>needs to move the whole list back and fro when doing that. Correct me if I am wrong.

P.S. My System.Diagnostics.Stopwatch.Frequency is 2435947, and the program is targeted to .NET 4 Client Profile and compiled with C# 4.0, on Windows 7 Visual Studio 2010.

Answer 1

Concerning 1:

Stack<T>'s and List<T>'s performance being similar isn't surprising. I'd expect both of them to use arrays with a doubling strategy. This leads to amortized constant-time additions.

You can use List<T> everywhere you can use Stack<T>, but it leads to less expressive code.

Concerning 2:

I think I know why List<T> doesn't handle the front so well... because List<T> needs to move the whole list back and fro when doing that.

That's correct. Inserting/removing elements at the beginning is expensive because it moves all elements. Getting or replacing elements at the beginning on the other hand is cheap.

Concerning 3:

Your slow LinkedList<T>.RemoveLast value is a mistake in your benchmarking code.

Removing or getting the last item of a doubly linked list is cheap. In the case of LinkedList<T> that means that RemoveLast and Last are cheap.

But you weren't using the Last property, but LINQ's extension method Last(). On collections that don't implement IList<T> it iterates the whole list, giving it O(n) runtime.