LinkedList Always Slower than a List in C#?

I started using some LinkedList’s instead of Lists in some of my C# algorithms hoping to speed them up. However, I noticed that they just felt slower. Like any good developer, I figured that I should do due diligence and verify my feelings. So I decided to benchmark some simple loops. You can find the benchmark class here.

I thought that populating the collections with some random integers should be sufficient. I ran this code in Debug mode to avoid any compiler optimizations. Here is the code that I used:

var rand = new Random(Environment.TickCount);
var ll = new LinkedList<int>();
var list = new List<int>();
int count = 20000000;

BenchmarkTimer.Start("Linked List Insert");
for (int x = 0; x < count; ++x)
	ll.AddFirst(rand.Next(int.MaxValue));
BenchmarkTimer.StopAndOutput();

BenchmarkTimer.Start("List Insert");
for (int x = 0; x < count; ++x)
	list.Add(rand.Next(int.MaxValue));
BenchmarkTimer.StopAndOutput();

int y = 0;
BenchmarkTimer.Start("Linked List Iterate");
foreach (var i in ll)
	++y; //some atomic operation;
BenchmarkTimer.StopAndOutput();

int z = 0;
BenchmarkTimer.Start("List Iterate");
foreach (var i in list)
	++z; //some atomic operation;
BenchmarkTimer.StopAndOutput();

Here is the output:

Linked List Insert: 8959.808 ms
List Insert: 845.856 ms
Linked List Iterate: 203.632 ms
List Iterate: 125.312 ms

This result baffled me. A Linked List insert should be O(1) whereas as List Insert is Θ(1), O(n) (because of copy) if it needs to be resized. Both list iterations should be O(1) because of the enumerator. I looked at the disassembled output and it doesn’t shed much light on the situation.

Anyone else have any thoughts on why this is? Did I miss something glaringly obvious?

Are you a Git user? Let me help you make project management with Git simple. Checkout Gitpilot.

Read me blog on entrepreneurship: Techneur
Follow me on Twitter: @jprichardson

-JP

Three Ways to Sort a List of Objects with DateTime in C#

Here are three quick ways to sort a List of objects that have DateTime properties in C#.

Initial Code:

public class Person{
	public string Name;
	public DateTime Birthday;
}

var people = new List<Person>();
var p1 = new Person() { Name = "Leslie", Birthday = new DateTime(1983, 9, 4) };
var p2 = new Person() { Name = "Chris", Birthday = new DateTime(2001, 6, 19) };
var p3 = new Person() { Name = "JP", Birthday = new DateTime(1983, 4, 5) };

people.Add(p1); people.Add(p2); people.Add(p3);
people.ForEach(p => Console.WriteLine(p.Name));

You can see that the output is: “Leslie”, “Chris”, and then “JP”

Let’s start with the LINQ way:

var persons = from p in people
		    orderby p.Birthday
		    select p;
persons.ToList().ForEach(p => Console.WriteLine(p.Name));

You can see the correct output: “JP”, “Leslie”, and then “Chris”

Old fashion way using a Delegate:

people.Sort(delegate(Person ps1, Person ps2) { return DateTime.Compare(ps1.Birthday, ps2.Birthday); });
people.ForEach(p => Console.WriteLine(p.Name));

Cleaner way using a Lambda:

people.Sort((ps1, ps2) => DateTime.Compare(ps1.Birthday, ps2.Birthday));
people.ForEach(p => Console.WriteLine(p.Name));

Are you a Git user? Let me help you make project management with Git simple. Checkout Gitpilot.

Read me blog on entrepreneurship: Techneur
Follow me on Twitter: @jprichardson

-JP

C# yield

I’ve seen the “yield” keyword here and there… but I’ve never really cared to learn what it does. Until now. Actually, it’s my understanding that it’s more or less a convenience keyword like “var.”

In short, “yield” allows you to return an IEnumerable without creating a List.

Example: (old way)

IEnumerable<Car> FindBlueCars(){
	var blueCars = new List<Car>();
	foreach (var c in _allCars)
		if (c.IsBlue())
			blueCars.Add(c);
	return blueCars;
}

Example: (new way)

IEnumerable<Car> FindBlueCars(){
	foreach (var c in _allCars)
		if (c.IsBlue())
			yield return c;
}

Saves some typing. MSDN reference for yield.

Are you a Git user? Let me help you make project management with Git simple. Checkout Gitpilot.

Read me blog on entrepreneurship: Techneur
Follow me on Twitter: @jprichardson

-JP