OK. Lets just revise the query we had in the previous post. I’m going to change it so that is finds enumerators that are also value types;
from f in Directory.GetFiles (
Path.Combine (
Environment.GetFolderPath (System.Environment.SpecialFolder.ProgramFilesX86),
@"Reference Assemblies\Microsoft\Framework\.NETFramework\v4.0"),
"*.dll")
where !f.ToLowerInvariant().Contains ("thunk")
where !f.ToLowerInvariant().Contains ("wrapper")
select Assembly.LoadFrom (f) into a
from t in a.GetExportedTypes()
where t.IsValueType && typeof(IEnumerator).IsAssignableFrom (t)
select new { a.GetName().Name, t.FullName }
Running the query in LINQPad will yield the following results.
It would seem like a CRAZY! thing to do given that an enumerator, is by its very nature, mutable… I’ll try to reason why this might be beneficial; then we will look at why it sucks.
Possible Reasoning
I can think of two possible reasons why they might have chosen to do this.
1. It could be considered a “feature” in that if you ever wanted to remember or save the current state of a collection’s enumerator, you could just copy it to another field. I’m going to rule this out, the behaviour isn’t consistent with other enumerators (arrays, non-generic collections and then later, iterator blocks).
2. Another possibility is performance. Perhaps the BCL team were looking to avoid the heap allocation caused by calling GetEnumerator.
It would seem like a “micro optimisation”; does that tiny heap allocation really cause an issue? I’m going to look at a popular design pattern that I think might expose the problem they were trying to solve.
The Composite Design Pattern
Consider a C# implementation of the Composite pattern;
// Composite design pattern
class Node
{
public readonly ArrayList Children = new ArrayList();
public void Recurse()
{
foreach(Node child in Children)
{
child.Recurse();
}
}
}
Now lets consider a simple usage (1000 nodes with 1000 children).
var root = new Node();
for (int i = 0; i < 1000; i++)
{
var child = new Node();
for (int j = 0; j < 1000; j++)
{
child.Children.Add(new Node());
}
root.Children.Add(child);
}
var before = GC.CollectionCount(0);
root.Recurse();
var after = GC.CollectionCount(0);
Console.WriteLine("Collection Count: " + (after - before));
OUTPUT
That’s right 7 GCs just to recurse our composite tree structure! Yikes!
If we change from ArrayList to List<object>, you can see the difference.
Is this a realistic scenario? Can anyone think of a LARGE instance of the composite design pattern present in many of today’s .NET applications? I’ll give you a clue, it starts with W… and ends in PF.
WPF & Silverlight are text book implementations of the composite design pattern; can you imagine how many times the tree is traversed in this manner? Can you imagine how deep the tree is for a complex user interface? In my mind, this is a good theory for explaining why, at the very least the “presentation core” enumerators have been implemented in this manner. I think most developers would have implemented a composite design pattern using List<T> at some stage or another.
Possible Problems
So is it likely that someone would trip over this optimisation? Lets start with the obvious ones before moving to hell.
List<int>.Enumerator e1 = new List<int>{1,2,3,4,5}.GetEnumerator();
List<int>.Enumerator e2 = e1;
e1.MoveNext();
Console.WriteLine(e1.Current);
Console.WriteLine(e2.Current);
This will output 1 & 0. The team probably decided to take this hit, after all any normal person would write this.
IEnumerator<int> e1 = new List<int>{1,2,3,4,5}.GetEnumerator();
IEnumerator<int> e2 = e1;
e1.MoveNext();
Console.WriteLine(e1.Current);
Console.WriteLine(e2.Current);
This causes the value type to be boxed, meaning the “copy by value” semantics disappear and we get two references to the same enumerator, giving us the expected output of 1 & 1. But wait a second, most developers in .NET 3.5 / C# 3.0 will write this;
var e1 = new List<int>{1,2,3,4,5}.GetEnumerator();
var e2 = e1;
e1.MoveNext();
Console.WriteLine(e1.Current);
Console.WriteLine(e2.Current);
Uh oh! GetEnumerator returns List<int>.Enumerator meaning the inferred type is the value type, we’re back to square one!
I guess you could argue, well at least the problem is localised to this statement; it isn’t like people are passing these around from one method to another.
Oh wait, but what about the interference of generic type parameters! This is heavily leveraged by technologies like LINQ & Rx (NOTE: This is how I came up with my recent pop quiz!).
Consider the following;
public class Wrapper<T> where T : IEnumerator
{
private readonly T enumerator;
public Wrapper(T enumerator)
{
this.enumerator = enumerator;
}
public object Current
{
get { return enumerator.Current; }
}
public bool MoveNext()
{
return enumerator.MoveNext();
}
}
Impromptu Pop Quiz
I don’t want to box the enumerator… we only have one storage location.
private readonly T enumerator;
Will this wrapper work for enumerators that are value types?
Here is a complete program for you to play with.
using System;
using System.Collections.Generic;
using System.Collections;
namespace ConsoleApplication30
{
class Program
{
private static void Main()
{
var w = Wrapper.Create(new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }.GetEnumerator());
w.MoveNext();
Console.WriteLine("Expected value: 1");
Console.WriteLine("Actual value: " + w.Current);
}
}
public static class Wrapper
{
public static Wrapper<T> Create<T>(T enumerator)
where T : IEnumerator
{
return new Wrapper<T>(enumerator);
}
}
public class Wrapper<T> where T : IEnumerator
{
private readonly T enumerator;
public Wrapper(T enumerator)
{
this.enumerator = enumerator;
}
public object Current
{
get { return enumerator.Current; }
}
public bool MoveNext()
{
return enumerator.MoveNext();
}
}
}
Look forward to your replies!
