Why Do Bcl Collections Use Struct Enumerators, Not Classes

Why do BCL Collections use struct enumerators, not classes?

Indeed, it is for performance reasons. The BCL team did a lot of research on this point before deciding to go with what you rightly call out as a suspicious and dangerous practice: the use of a mutable value type.

You ask why this doesn't cause boxing. It's because the C# compiler does not generate code to box stuff to IEnumerable or IEnumerator in a foreach loop if it can avoid it!

When we see

foreach(X x in c)

the first thing we do is check to see if c has a method called GetEnumerator. If it does, then we check to see whether the type it returns has method MoveNext and property current. If it does, then the foreach loop is generated entirely using direct calls to those methods and properties. Only if "the pattern" cannot be matched do we fall back to looking for the interfaces.

This has two desirable effects.

First, if the collection is, say, a collection of ints, but was written before generic types were invented, then it does not take the boxing penalty of boxing the value of Current to object and then unboxing it to int. If Current is a property that returns an int, we just use it.

Second, if the enumerator is a value type then it does not box the enumerator to IEnumerator.

Like I said, the BCL team did a lot of research on this and discovered that the vast majority of the time, the penalty of allocating and deallocating the enumerator was large enough that it was worth making it a value type, even though doing so can cause some crazy bugs.

For example, consider this:

struct MyHandle : IDisposable { ... }
...
using (MyHandle h = whatever)
{
    h = somethingElse;
}

You would quite rightly expect the attempt to mutate h to fail, and indeed it does. The compiler detects that you are trying to change the value of something that has a pending disposal, and that doing so might cause the object that needs to be disposed to actually not be disposed.

Now suppose you had:

struct MyHandle : IDisposable { ... }
...
using (MyHandle h = whatever)
{
    h.Mutate();
}

What happens here? You might reasonably expect that the compiler would do what it does if h were a readonly field: make a copy, and mutate the copy in order to ensure that the method does not throw away stuff in the value that needs to be disposed.

However, that conflicts with our intuition about what ought to happen here:

using (Enumerator enumtor = whatever)
{
    ...
    enumtor.MoveNext();
    ...
}

We expect that doing a MoveNext inside a using block will move the enumerator to the next one regardless of whether it is a struct or a ref type.

Unfortunately, the C# compiler today has a bug. If you are in this situation we choose which strategy to follow inconsistently. The behaviour today is:

• if the value-typed variable being mutated via a method is a normal local then it is mutated normally

• but if it is a hoisted local (because it's a closed-over variable of an anonymous function or in an iterator block) then the local is actually generated as a read-only field, and the gear that ensures that mutations happen on a copy takes over.

Unfortunately the spec provides little guidance on this matter. Clearly something is broken because we're doing it inconsistently, but what the right thing to do is not at all clear.

Why have Enumerator struct and EnumeratorImpl class?

Are there any other reasons?

None come to mind. You seem to have accurately described the purposes of this rather odd implementation of the sequence pattern.

I hasten to add: Roslyn is an unusual .NET application in its complexity, in its performance requirements, and in the number of objects that it generates. A compiler that analyzes programs with thousands of files, millions of lines and tens of millions of characters while the user is typing has to do some pretty unusual things to ensure that it does not overwhelm the garbage collector. Roslyn therefore uses pooling strategies, uses mutable value types, and other out-of-the-mainstream practices to help achieve these performance goals. I do not recommend taking on the expense and difficulty associated with these practices unless you have empirical evidence identifying a serious performance problem that these practices mitigate. Just because this code was written by the C# compiler team does not mean that this is the gold standard for how you should be writing your mainstream business objects.

Enumerator Implementation: Use struct or class?

Like this others, I would choose a class. Mutable structs are nasty. (And as Jared suggests, I'd use an iterator block. Hand-coding an enumerator is fiddly to get right.)

See this thread for an example of the list enumerator being a mutable struct causing problems...

Why do C# Arrays use a reference type for Enumeration, but ListT uses a mutable struct?

From what I've read, a design decision was made for certain Collections's Enumerator Types to be mutable structs instead of reference types for performance reasons.

Good question.

First off, you are correct. Though in general, mutable value types are a bad code smell, in this case they are justified:

• The mutation is almost entirely concealed from the user.
• It is highly unlikely that anyone is going to use the enumerator in a confusing manner.
• The use of a mutable value type actually does solve a realistic performance problem in an extremely common scenario.

I am wondering if anyone knows why Array's generic iterator was implemented as a reference type when so many other performance critical collections used mutable structs instead.

Because if you're the sort of person who is concerned about the performance of enumerating an array then why are you using an enumerator in the first place? It's an array for heaven's sake; just write a for loop that iterates over its indicies like a normal person and never allocate the enumerator. (Or a foreach loop; the C# compiler will rewrite the foreach loop into the equivalent for loop if it knows that the loop collection is an array.)

The only reason why you'd obtain an enumerator from an array in the first place is if you are passing it to a method that takes an IEnumerator<T>, in which case if the enumerator is a struct then you're going to be boxing it anyway. Why take on the expense of making the value type and then boxing it? Just make it a reference type to begin with.

When should I separately implement IEnumeratorT?

The answer to your first question is: when a yield return doesn't meet your needs.

The answer to your second question is: these heavily used types have performance requirements that are unusually strict, so the enumerators are custom built. I've written some articles on this recently; see:

http://ericlippert.com/2014/05/21/enumerator-advance/

http://ericlippert.com/2014/06/04/enumerator-bounds/

Instantiation of List with Enumerator

It is something quite useless and wrong...

The first question should be what is the List<T>.Enumerator... It is a support class of List<T> that implements the IEnumerator<T> interface (the interface used for enumerating a collection, used for example by the foreach). For performance reasons it is a struct instead of being a class. Being a struct is has a predefined public parameterless constructor (the one you are using). It has even an internal constructor with one parameter (List<T> list) that sets some necessary internal fields (the most important is a reference to the List<> that created it). This constructor is used by List<>.GetEnumerator().

Now, if you do what you wrote, you will create an "incomplete" Enumerator. The item.Current will "work" (returning a default(T)) but if you try to do a item.MoveNext() you'll get a NullReferenceException. If you want an IEnumerator for an "empty" collection, it would be better to do:

var item = Enumerable.Empty<int>().GetEnumerator();

For the reason why List<T>.Enumerator is public instead of being private or internal... It is a little more complex. List<T> implements IEnumerable<T> and IEnumerable, so it must have at least two methods with these signatures:

IEnumerator<T> IEnumerable<T>.GetEnumerator()

and

IEnumerator IEnumerable.GetEnumerator()

but for performance reasons it implements them as explicit implementation (so hiding them), and implements a third method:

public Enumerator GetEnumerator()

that returns a struct Enumerator... now, thanks to how foreach works, this third public method will be the one used by foreach. Why this? Because a struct used through one of its interfaces (IEnumerator<T> or IEnumerator in this case) is boxed (something that slows it a little)... but if the struct is used directly (through its public Enumerator GetEnumerator()) method, there is no boxing and the performance is a little better... Microsoft programmers gave their 110% on List<> performances :-)

Enumerator for SortedDictionary.ValueCollection behaviour differs from other Enumerators

I believe that the answer to this is that the SortedDictionary value enumerator is a struct (of type System.Collections.Generic.SortedDictionary<string,int>.ValueCollection.Enumerator).

What's happening is that the struct is being copied each time it is passed to the Print() method, thus the method is always working with a copy of the original enumerator - and this causes things to work strangely.

The following program demonstrates this:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Example();
    }

    public static void Example()
    {
        var sorted = new SortedDictionary<string, int>
        {
            {"1", 1 },
            {"3", 3 },
            {"0", 0 },
            {"2", 2 },
            {"4", 4 }
        };

        var fromValues1 = sorted.Values.GetEnumerator();
        // fromValue1 type is struct System.Collections.Generic.SortedDictionary<string,int>.ValueCollection.Enumerator
        fromValues1.MoveNext();

        while (printNextValue(fromValues1)) // Prints 0 once for each value in the dictionary.
            ;

        Console.WriteLine("-----------------");

        IEnumerator<int> fromValues2 = sorted.Values.GetEnumerator();
        // fromValues2 type is boxed struct System.Collections.Generic.SortedDictionary<string,int>.ValueCollection.Enumerator
        fromValues2.MoveNext();

        while (printNextValue(fromValues2)) // Prints each value in the dictionary.
            ;
    }

    static bool printNextValue(IEnumerator<int> enumerator)
    {
        Console.WriteLine(enumerator.Current);
        return enumerator.MoveNext();
    }
}

The first loop outputs all zeros, while the second outputs the correct values.

The only difference between the two loops in this example is that the first iterator is declared as:

var fromValues1 = sorted.Values.GetEnumerator();

And the second one is declared as:

IEnumerator<int> fromValues2 = sorted.Values.GetEnumerator();.

The first declaration will result in fromValues1 being a struct, while the second is a boxed struct.

Because the struct is boxed, it means that it is NOT copied when it is passed to printNextValue(), which means that printNextValue() will be working with the original enumerator rather than a copy of it.

However, this does NOT explain why the loop terminates! If the original enumerator position was being copied each time printNextValue() was called, then the loop would never terminate since the position of the original enumerator would never be updated.

This leads me to believe that some complexity in the implementation of SortedDictionary.Enumerator means that when the struct is copied, some of its data is copied, but some of it isn't.

(Looking at the source code, I suspect this is due to the enumerator implementation's Current being a value type that gets copied, but the MoveNext() seems to manipulate a stack which - being a reference type - is shared between all the copies of the enumerator. However, the code is a bit too complex for me to analyse in my currently limited time...)

---

Related Topics