TechEd Eilat 2008: Keynote and Brainteasers
This TechEd's keynote featured .NET brainteasers, an idea originally conceived by Amir Shevat. The idea is interrupting the keynote once in a while, to ask a short technical question. The answer seems obvious at first, but there's always a catch. Following today's keynote, here are the two brainteasers I presented and the explanations.
Brainteaser #1
What does the following code output in the Release build? (Note the emphasis.)
using System.Threading;
static void Main(string[] args)
{
Timer t = new Timer(
delegate { Console.WriteLine(
DateTime.Now.ToString()); },
null, 0, 100);
Console.ReadLine();
}
The possible answers were:
- Does nothing because the local variable is garbage collected;
- Displays the current date indefinitely until the user presses Enter;
- Displays the current date for a limited number of times;
- Crashes because the timer's finalizer gets called.
The correct answer is #3, which is pretty shocking for most developers. During the session I've shown the above code (with a slight modification) run in the debug build and in the release build. In debug, it proceeds to run indefinitely; in release, it stops after a certain number of times.
Why, you ask? Well, the timer stops at the first garbage collection that occurs in the application. So first things first - why would a GC occur?
In the delegate registered to the timer we have a memory allocation in the DateTime.Now.ToString() call (which might seem invisible to the trained manager developer's eyes). This memory allocation (sooner or later) causes a GC.
Now, why is the timer local variable being collected? It seems like the main method is still using it... But in fact, it isn't. As soon as we get to the Console.ReadLine() line, the local variable is no longer an active root which is considered by the GC when building the object graph. It makes sense, too, because we want to reclaim memory as soon as it is not referenced by our application, and once we get to the Console.ReadLine(), the timer is indeed not referenced by our application. (For a deeper explanation of GC roots and the subtleties of the .NET garbage collector, you can refer to Jeffrey Richter's excellent CLR via C# book, or my course at Sela titled .NET Performance.)
Brainteaser #2
Which is the faster way to iterate over a random-access collection (such as List<T> or an array) - "for" or "foreach"?
The possible answers were:
- Always "for" because "foreach" creates an enumerator object, and it's garbage;
- Always "foreach", because the enumerator can pre-fetch elements from the collection before they are being accessed;
- "for" for most collections, but the same performance for arrays because of compiler optimizations;
- "foreach" for most collections, but the same performance for arrays because of compiler optimizations.
The correct answer is again #3, which is again quite unexpected. This is a really fundamental issue, which questions our understanding of the .NET platform. So why is "for" faster for a collection like a List<T>, and why is the performance identical for arrays?
Let's start with the easy part. The C# compiler emits semantically identical IL whether you use "for" or "foreach" to iterate an array. Two copies of identical code will give you the same performance footprint. So that's great, and makes perfect sense.
However, for a List<T> or any other random-access collection you might come up with, the code generation is a little bit different. Let's take a look at the conceptual steps we should go through when iterating over a List<T> using "for" and "foreach".
Starting with "for":
List<int> list = new List<int>();
int sum = 0;
for (int i = 0; i < list.Count; ++i)
{
sum += list[i]; //sum += list.get_Item(i)
}
So if we look at the list[i] line, we see that there's an underlying method call to access the element. Let's take a look at "foreach":
List<int> list = new List<int>();
int sum = 0;
var enumerator = list.GetEnumerator();
while (enumerator.MoveNext())
{
sum += enumerator.Current; //sum += enumerator.get_Current()
}
This time, we have two method calls for each iteration - that's the implementation of .NET enumerators.
I can already hear your objections - the single most important optimization the JIT compiler can offer us is method inlining. But in this particular case, we don't benefit from inlining! Why not? This could be a brainteaser of its own, but I'll kindly give the answer away. The implementation of IEnumerable and IEnumerator on the List<T> class is not explicitly virtual (you won't see the virtual keyword), but it is implicitly virtual because the methods are part of an interface. And since the methods are virtual and are part of an interface, they can't be inlined, so we can't get performance equal to a built-in array. Furthermore, it's clear that "foreach" is slower because it incurs two method calls as opposed to "for" which incurs a single method call.
This was a brief summary of the brainteasers at today's keynote. I hope you enjoyed it, I sure did, and I am looking forward to future TechEd keynotes where this idea could be expanded to an even better format. A great thank you goes to Microsoft Israel for making this fantastic event possible!