Over a million developers have joined DZone.

Enumerator Structs: Optimizing for the Common Case

·

I read a couple of posts by Simon Cooper where he explains in great details why mutable structs are bad, and how the BCL’s enumerator structs (e.g. LinkedList<T>.Enumerator) are prime candidates for this anti-pattern. He dissects a really nasty bug where declaring a value type field as readonly effects unexpected copy semantics if the value type is modified. The following code enters an infinite loop (which prints 0 indefinitely):

class EnumeratorWrapper
{
private readonly LinkedList<int>.Enumerator _enumerator;
private readonly LinkedList<int> _list;

public EnumeratorWrapper()
{
_list = new LinkedList<int>(Enumerable.Range(0,5));
_enumerator = _list.GetEnumerator();

PrintAll();
}

private void PrintAll()
{
while (_enumerator.MoveNext())
{
Console.WriteLine(_enumerator.Current);
}
}
}

The reason is that if you declare the field readonly, the MoveNext call will be called on a copy of the field’s value, to prevent it from being modified. Admittedly, this seems like enough of a reason to ban mutable value types altogether, and the enumerator structs in particular.

So why bother with a value type? As the matter of fact, why bother exposing the type that implements the IEnumerator<T> interface, and not declare it a private class and return only the interface? In other words, what’s the difference between the following two approaches?

class MyCollection : IEnumerable<int>
{
public IEnumerator<int> GetEnumerator()
{
return new MyPrivateEnumerator();
}

private class MyPrivateEnumerator : IEnumerator<int>
{
//Implementation omitted
}
}
class MyOtherCollection : IEnumerable<int>
{
public MyEnumerator GetEnumerator()
{
return new MyEnumerator();
}

IEnumerator<int> IEnumerable<int>.GetEnumerator()
{
return GetEnumerator();
}

public struct MyEnumerator : IEnumerator<int>
{
}
}

Well, as I (and many others) have written elsewhere, calling a method through an interface reference is more expensive than calling it directly. The primary motivation behind publicly exposing the enumerator type is that clients of the collection class can use it directly, without going through an interface reference.

Fortunately, the foreach statement uses duck typing to perform the enumeration on the collection—and the foreach statement is really the common case of using any enumerator at all. This means that in the following fragment, the public MyOtherCollection.GetEnumerator method is called, and the generated code uses the enumerator struct directly, and not through an interface reference:

MyOtherCollection collection = new MyOtherCollection();
foreach (int i in collection)
{
Console.WriteLine(i);
}

Roughly equivalent to:

var enumerator = collection.GetEnumerator();
while (enumerator.MoveNext())
{
int i = enumerator.Current;
Console.WriteLine(i);
}

That’s why there are no method calls through an interface here—the “var” is MyOtherCollection.MyEnumerator and not IEnumerator<int>! Moreover—and this is the critical point—if the enumerator implementation were to go through the same hoops of implementing the interface explicitly and at the same time providing public methods that do the same thing, then the MoveNext and get_Current method calls would also be direct calls (not through an interface reference), and therefore could be inlined. Obviously, the only chance of ever achieving performance with a foreach block over a collection that is comparable to that of a built-in array is if the collection accessors are inlined. And it’s very simple, indeed:

public struct MyEnumerator : IEnumerator<int>
{
public bool MoveNext()
{
//Actual implementation here
}

bool IEnumerator.MoveNext()
{
return MoveNext();
}

void IEnumerator.Reset()
{
throw new NotImplementedException();
}

public int Current
{
get { /* Actual implementation here */ }
}

object IEnumerator.Current
{
get { return Current; }
}
}

Now, if the caller is working with a variable of type MyEnumerator, they would access the critical methods directly, without an interface call, allowing for inlining to take place (not to mention that the integer will not be boxed when returning from the get_Current call). Still, if someone insists on using an interface to perform the enumeration, we implement our part of the contract using explicit interface implementation.

Finally, why bother with the value types? The probable reason is to avoid object allocations. Allocating a value type and returning it is significantly cheaper than allocating a heap object and reclaiming it later. Although this is not the critical performance improvement here (the explicit implementation trick is the crucial part), it’s still worthwhile.

Is it worthwhile, though, to introduce a mutable value type, which is a big no-no by all accounts, for this performance gain? I think it is. If the enumerator type were commonly used on its own, I wouldn’t agree—but this particular enumerator type is used, 99.99% of the time, in a foreach statement, where the developer is not exposed at all to its existence.

I think that implementing a mutable value type that’s invisible in the vast majority of development scenarios and that provides a non-negligible performance gain is an acceptable compromise.

Topics:

Published at DZone with permission of Sasha Goldshtein, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}