While I was reading through some C# 2.0 code that a friend of mine wrote, I noticed that he was finding some objects in a List using a foreach loop. As soon as I saw that, I thought to myself that I would probably have done that using FindAll with an anonymous delegate.
That got me thinking about all the different ways you can find things in a List in C#. I’ve recently upgraded to using Visual Studio 2008, so with the advent of C# 3.5 there are even more ways to do something like this. Which method is best is not very clear, so I thought it was time for some performance tests.
The Test
I decided that a nice and simple performance test would be to find all the numbers less than 10,000 in an array of 1,000,000 random integers. To even things out, I perform the same test 100 times for each method, and take the average time. I generated the set of random numbers once, and then used that same set in all tests.
Techniques
So far, I’ve thought of eight different ways to implement the performance test. There are probably more ways, but these seem to be a fairly sensible set:
- Use a for loop and index into the list.
- Use a foreach loop.
- ForEach function in List.
- FindAll function in List with an anonymous delegate.
- FindAll function in List with a lambda function.
- Count function in List with an anonymous delegate.
- Count function in List with a lambda function.
- Linq.
Results
I ran the tests on my laptop in the standard release config. I verified that all implementations returned the same number of items.
| Technique | Time(ms)< |
| For Loop | 8 |
| ForEach Loop | 6 |
| ForEach Function | 10 |
| FindAll Function Delegate | 11 |
| FindAll Function Lambda | 11 |
| Count Function Delegate | 34 |
| Count Function Lambda | 34 |
| Linq | 19 |
Well it turns out that my friend had indeed picked the best way to find things in an unsorted list. I was surprised that the for loop was so much slower than foreach, but then I took a look at the IL. The foreach implementation had one virtual function call to GetEnumerator at the top of the loop, and then used non-virtual function calls to get_Current on the enumerator inside the loop. By contrast, the for loop had virtual function calls to get_Item inside the loop.
Clearly, using delegates and lambda functions makes no difference. Looking at the IL in Reflector, they generated identical delegates. That’s enough for me to avoid delegates wherever possible, since the lambda functions were much easier to read.
I had heard about the relatively poor performance of Linq, but I was surprised that it was really three times slower than the best solution. There was more code to write than using FindAll with the lambda function, so it was no more brief either.
While I was looking though the list functions, I came across Count, so I thought I would include it here. I don’t know why you would ever use this function given how terribly it performed. Initially when I saw it, I thought that maybe it was used internally for Linq, but I don’t suppose it can be. I’d be interested to know what its purpose is.
I hope this was informative!
p.s. Charles just pointed me to this page explaining some of the reasons behind the current performance of Linq.
Linq Count() method is there because you can chain linq operators and you could do something like
int itemCount = colection.Take(10).Where( someLambda ).Skip(2).Count();
So, having a Count method that works on any IEnumerable is usefull for….well counting things in that enumerable.
Also Count has an overload that takes a Func that can be used to count elements that meet a certain criteria.
Most linq operators are deferred ( http://blogs.msdn.com/charlie/archive/2007/12/09/deferred-execution.aspx ) so having a Count method is useful because Linq results are not collections but enumerators that only execute when they are iterated over and that means the number of elements is unknown until the iteration completes, so that count can’t be exposed as a property.