List<T>.ForEach vs foreach(...)

A thread came up yesterday on the C# newsgroup about when to use the "normal" foreach and when to use List<T>.ForEach (assuming, of course, that one is dealing with a List<T> in the first place). Obviously there are readability issues, but we ended up focusing on performance. (Isn't that telling in its own right? How often is the iteration part rather than the body going to dominate and be a significant bottleneck? Anyway, I digress.)

So, I wrote a small benchmark, and Patrick asked me to blog about it. I've refactored the test I posted on the newsgroup and added a couple more tests as suggested by Willy Denoyette. The source code is a little bit unwieldy (and frankly tedious) to include in this blog post - download it if you're interested.

The test basically creates a list of strings, each being "x". Each test case iterates through the list a fixed number of times, keeping a running total of the lengths of strings it sees. The result is checked and the time taken is reported. This is what the individual tests do:

  • LanguageForEach just uses foreach (string x in list) in the obvious way.
  • NewDelegateEachTime uses an anonymous method as the parameter to List.ForEach<T>, where that method captures a different variable each "outer" iteration. That means a new delegate has to be created each time.
  • CachedDelegate creates a single delegate and uses that for all calls to List<T>.ForEach.
  • LanguageForEachWithCopy1 copies the list to an array each "outer" iteration, and then uses foreach over that array.
  • LanguageForEachWithCopy2 copies the list to an array once at the start of the test, and then uses foreach over that array.

Here are the results, with a few different test cases (all doing the same amount of work overall). I shall attempt to tabulate them a bit better when I get some time :) 

Test parameters: Size=10000000; Iterations=100
Test 00:00:11.8251914: LanguageForEach
Test 00:00:05.3463387: NewDelegateEachTime
Test 00:00:05.3238162: CachedDelegate
Test 00:00:22.1342570: LanguageForEachWithCopy1
Test 00:00:03.7493164: LanguageForEachWithCopy2


Test parameters: Size=1000000; Iterations=1000
Test 00:00:11.8163135: LanguageForEach
Test 00:00:05.3392333: NewDelegateEachTime
Test 00:00:05.3334596: CachedDelegate
Test 00:00:26.9471681: LanguageForEachWithCopy1
Test 00:00:03.5251209: LanguageForEachWithCopy2


Test parameters: Size=100000; Iterations=10000
Test 00:00:11.6576344: LanguageForEach
Test 00:00:05.2225531: NewDelegateEachTime
Test 00:00:05.2066938: CachedDelegate
Test 00:00:16.2563401: LanguageForEachWithCopy1
Test 00:00:03.0949064: LanguageForEachWithCopy2


Test parameters: Size=100; Iterations=10000000
Test 00:00:12.2547105: LanguageForEach
Test 00:00:04.9791093: NewDelegateEachTime
Test 00:00:04.6191521: CachedDelegate
Test 00:00:06.0731525: LanguageForEachWithCopy1
Test 00:00:02.8182444: LanguageForEachWithCopy2

The LanguageForEachWithCopy1 results surprised me, as I'd really expected the performance to go up as the number of iterations went up. It seems it's cheaper to copy a short list many times than a long list a few times...

Published Fri, Jan 20 2006 8:49 by skeet
Filed under:

Comments

# re: List&lt;T&gt;.ForEach vs foreach(...)

Well, I am really suprised that there is such a huge difference between LanguageForEach and NewDelegateEachTime. What is more using delegate seems to be much faster. Do you see any explanation?

Friday, January 20, 2006 11:10 AM by Pawel Pabich

# re: List&lt;T&gt;.ForEach vs foreach(...)

I believe that the explaination for the ForEach() being faster is that the former doesn't do as much checking at each iteration and only results in one method call, whereas foreach checks for stuff like concurrent modifcation and out of bounds and has to call the Enumerator's MoveNext() and get_Current() at each iteration.

Friday, January 20, 2006 2:45 PM by Leif Wickland

# Foreach iterations

Tuesday, January 24, 2006 10:13 AM by The Angry Coder

# re: List&lt;T&gt;.ForEach vs foreach(...)

Great post, John.

I got curious, and so I added a test using a traditional for() loop.

On my machine, built in Release configuration, and running outside of the debugger, using a straight for() loop was faster than every method except for LanguageForEachWithCopy2, which was eerily fast.

Here's the code:
static int LanguageFor(List<string> list)
{
int sum = 0;

for (int i = 0; i < Iterations; i++)
{
for (int index = 0; index < list.Count; index++)
{
sum += list[index].Length;
}
}
return sum;
}

Monday, January 30, 2006 11:57 AM by J.Marsch

# What's up?

Tuesday, February 21, 2006 11:41 AM by A little something...

# Why the same value for every string?

Why using the same value for every string in list?
I think it leads to some hidden CPU optimization.
Also it's far from a real-world scenario.

If every string in the list is different we have a fairly different result:

Random randomGenerator = new Random(DateTime.Now.Millisecond);

for (int i = 0; i < Size; i++)
{
list.Add(randomGenerator.NextDouble().ToString());
}

Most of the differences are more leveled.

Test parameters: Size=100000; Iterations=10000
Test 00:00:18.5486500: LanguageForEach
Test 00:00:15.4419635: NewDelegateEachTime
Test 00:00:15.1783838: CachedDelegate
Test 00:00:43.2335005: LanguageForEachWithCopy1
Test 00:00:13.9626502: LanguageForEachWithCopy2
Test 00:00:13.3392666: LanguageFor



And it's not a matter of string length, since

for (int i = 0; i < Size; i++)
{
list.Add("0,38160862465464");
}

(same string lenght of my previous code) leads to the same results as your string with 1 char.

What do you think?

(I have tried to post it via google groups but something didn't work).

Thursday, March 02, 2006 6:04 AM by Julius

# re: List&lt;T&gt;.ForEach vs foreach(...)

I don't believe it's a hidden optimisation - I suspect it's the natural result of cache sizing. Willy Denoyette certainly saw very different results depending on whether the CPU's L2 cache was able to hold everything or not.

I'm just guessing here though...

Jon

Thursday, March 02, 2006 8:22 AM by skeet

# re: List&lt;T&gt;.ForEach vs foreach(...)

Yeah, that could be it.

A real pity we can't upgrade it ;-)

BTW thanks for all your great contributions!

Thursday, March 02, 2006 1:54 PM by Julius

# re: List&amp;amp;lt;T&amp;amp;gt;ForEach() と匿名メソッド

re: List&amp;amp;lt;T&amp;amp;gt;ForEach() と匿名メソッド

Monday, May 22, 2006 11:26 PM by 囚人のジレンマな日々

# about the access of generic List

I think these test are fair enough.

But can anybody say is there any faster searching than Binary search in Generic List. Or any method in Array(which does not even feature binary search). Can anybody say???

Wednesday, March 21, 2007 5:00 AM by John cena

# re: List<T>.ForEach vs foreach(...)

I've found another interesting thing.

for (int i = 0; i < list.Count; i++)

{

  ...

}

is about 30% slower (I've tested it on Celeron M 1.6GHz 1MB L2) than

int count = list.Count;

for (int i = 0; i < count; i++)

{

  ...

}

Monday, April 09, 2007 3:42 AM by xsan

# re: List<T>.ForEach vs foreach(...)

The performance difference in the for loop is a given since the evaluation is performed in each iteration.

Still, the differences for the foreach performance is a bit interesting, though not too alarming. The more readable code is it surely is going to sacrifice some performance. (Otherwise we'd still be happily writing in mythical man-years with Turbo Assembler.)

Good to know when I need to perform operations against very large collections.

Tuesday, April 10, 2007 5:39 PM by Sokak

# re: List<T>.ForEach vs foreach(...)

xsan, are you sure you were running with a Release build andnot from the IDE?

Sokak, actually, the evaluation is *not* done for every iteration.  The JIT compiler is smarter than you might think and makes optimizations that can remove bounds checking and any computation necessary for the evaluation of the 'Count' or 'Length' property.  You can actually *slow down* your code by trying to outsmart the JIT compiler by doing your own loop-hoisting.

Tuesday, April 10, 2007 10:34 PM by DaveBlack

# A quoi sert List<T>.ForEach ?

Vous êtes vous déjà demandé à quoi servait la méthode ForEach de List&lt;T&gt; ? Personnellement, je

Monday, October 22, 2007 6:10 AM by Code is poetry

# re: List<T>.ForEach vs foreach(...)

My opinion:

1- If there's a lot of computation being done inside the block, the choice might not be that relevant.

2- List<T>.ForEach is still quite readable.

3- List<T>.ForEach allows you to skip to the next iteration of the loop (continue) by doing a return from the delegate. On the other hand, it doesn't allow you to break out of your loop easily. Perhaps you can throw and catch an exception.

David

Monday, November 17, 2008 10:07 AM by David