LINQ vs Loop - A performance test

I just installed Visual Studio 2008 beta 2 to see what the future holds for C#. The addition of LINQ has brought a variety of query keywords to the language. "Anything" can be queried; SQL databases (naturally), XML documents, and regular collections. Custom queryable objects can also be created by implementing IQueryable. Sadly, like every abstraction, these goodies all come at a cost. The question is how much?

I decided to create a simple test to see how much of a performance hit LINQ is. The simple test I deviced finds the numbers in an array that are less than 10.

	public void LinqTest()
	{
	const int SIZE = 10000, RUNS = 1000;
	int[] ints = new int[SIZE];
	for (int i = 0; i < SIZE; i++)
	ints[i] = i;
	DateTime start = DateTime.Now;
	for (int t = 0; t < RUNS; ++t)
	{
	int[] less = (from int i in ints
	where i < 10
	select i).ToArray();
	}
	TimeSpan spent = DateTime.Now - start;
	Trace.WriteLine(string.Format("LINQ: {0}, avg. {1}",
	spent, new TimeSpan(spent.Ticks / RUNS)));
	DateTime start2 = DateTime.Now;
	for (int t = 0; t < RUNS; ++t)
	{
	var l = new List();
	foreach (var i in ints)
	if (i < 10)
	l.Add(i);
	int[] less2 = l.ToArray();
	}
	TimeSpan spent2 = DateTime.Now - start2;
	Trace.WriteLine(string.Format("Loop: {0}, avg. {1}",
	spent2, new TimeSpan(spent2.Ticks / RUNS)));
	}

view raw LinqTest.cs hosted with ❤ by GitHub

Initially, I assumed the performance impact would not be too large, since its equivalent is the straightforward imperative loop, which should not be too hard for a compiler to deduce given static typing and a single collection to iterate across. Or?

    LINQ: 00:00:04.1052060, avg. 00:00:00.0041052
    Loop: 00:00:00.0790965, avg. 00:00:00.0000790

As you can see, the performance impact is huge. LINQ performs 50 times worse than the traditional loop! This seems rather wild at first glance, but the explanation is this: The keywords introduced by LINQ are syntactic sugar for method invocations to a set of generic routines for iterating across collections and filtering through lambda expressions. Naturally, this will not perform as good as a traditional imperative loop, and less optimization is possible.

Having seen the performance impact, I am still of the view that LINQ is a great step towards a more declarative world for developers. Instead of saying "take these numbers, iterate over all of them, and insert them into this list if they are less then ten", which is an informal description of a classical imperative loop, you can now say "from these numbers, give me those that are less than ten". The difference may be subtle, but the latter is in my opinion far more declarative and easy to read.

This may very well be the next big thing, but it comes at a cost. So far, my advice is to create simple performance tests for the cases where you consider adopting LINQ, to spot possible pitfalls as early as possible.