4

It's been established that the compiler can do duck typing to remove some overhead when iterating over a List or an Array (see Duck typing in the C# compiler), as those types implement their IEnumerator as a stack-allocated struct.

Is this the case even when the type is generic, but constrained to implement IEnumerable?

To give more specifity, could option B run with less overhead than A?

A:

public static IEnumerable<T> Flatten<T>(this IEnumerable<IEnumerable<T>> collection)
{
    foreach (var subCollection in collection)
        foreach (var element in subCollection)
            yield return element;
}

B:

public static IEnumerable<T> Flatten<TList, T>(this TList collection)
    where TList : IEnumerable<IEnumerable<T>>
{
    foreach (var subCollection in collection)
        foreach (var element in subCollection)
            yield return element;
}

2 Answers 2

6

No, basically. The only use for "B" is when the TList itself is actually a struct; the IL can then use "constrained call" to call the original GetEnumerator() without any part having to box the original struct TList value.

But: once you've called GetEnumerator(), you're back into IEnumerator<T> land, and it will not use the custom iterator.

All of which is mostly moot in this case, because iterator blocks are also fairly "allocatey". So... if avoiding boxing the TList is your concern, you are presumably obsessive about allocations: in which case you wouldn't write the iterator block this way, either.

1

As the other answer has indicated, the method that gets called in the TList version will always be IEnumerable<T>.GetEnumerator, even if it is hidden in TList and another GetEnumerator is visible. Therefore, even if TList happens to be List<T>, version B cannot take advantage of List<T>.Enumerator GetEnumerator() and the enumerator structure will be boxed inside the call to IEnumerator<T> IEnumerable<T>.GetEnumerator().

We can upgrade IEnumerable in a backward compatible way as follows:

interface IEnumerable<out T, out TEnumerator> : IEnumerable<T>
  where TEnumerator : IEnumerator<T>
{
  new TEnumerator GetEnumerator();
}

// In an imagined upgrade, the compiler should transform the iterator block
// to return IEnumerable<T, IEnumerator<T>>, allowing this to chain.
static IEnumerable<T> Flatten<T, TOuterEnumerator, TInnerEnumerator>
  (this IEnumerable<IEnumerable<T, TInnerEnumerator>, TOuterEnumerator> collection)
  // C# compiler needs to be reminded of these constraints,
  // or foreach will not compile.
  where TOuterEnumerator : IEnumerator<IEnumerable<T, TInnerEnumerator>>
  where TInnerEnumerator : IEnumerator<T>
{
  foreach (var subcoll in collection)
    foreach (var elem in subcoll)
      yield return elem;
}

IEnumerable<T, IEnumerator<T>> will be the new self of IEnumerable<T>, just like how IEnumerable<object> is the new self of IEnumerable. In this imagined upgrade, List<T> should implement IEnumerable<T, List<T>.Enumerator>.

The compiler will expand foreach to use TOuterEnumerator and TInnerEnumerator as the static types of the enumerators, so no boxing will happen if they happen to be structures.

Note that the compiler will always choose IEnumerator<...>.MoveNext and IEnumerator<...>.Current, even if the enumerator types hide them and have another visible version. This is the different from a non-generic method, which will choose the visible version, be it IEnumerator<...> or the specific types.

This does not cause a correctness problem for any sane enumerator (in fact, I don't know any enumerator implementing IEnumerator<...> explicitly). This also should not cause performance issues, because the compiler will constrain the call using the knowledge of the static types of the enumerators. So if the enumerators are sealed class or structure, the interface (virtual) call goes away and is replaced by direct instance call.


Shameless self-advertising: I have a blog entry on this.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.