How to implement C# foreach optimization in IL

Question

In this answer and this GitHub issue (top item) there is a description of foreach optimization used by C# compiler.

Basically, instead of allocating IEnumerable<T>, the generated code calls GetEnumerator() and then MoveNext() on the returned object, always using a direct call and therefore avoiding boxing and virtual calls.

Is it possible to write the same logic in intermediary language? I am quite a beginner with IL, however am familiar with the Unsafe package and the way it works. I wonder if it is possible to write an unsafe method in IL that accepts some object and calls it methods and properties directly?

(Also, could someone kindly give a link to the line in the Roslyn repo where this foreach optimization happens? The repo is so big and complex, I am lost there so far.)

Update:

Here is a method template

[MethodImpl(MethodImplOptions.AggressiveInlining)]
[ILSub(@"
    .. IL code here to be replaced by ilasm.exe
    .. Is there a way to do the same without boxing and virtual calls?
    ")]
public T CallIEnumerableMoveNextViaIL<T>(IEnumerable<T> enumerable)
{
    // I know that the `enumerable` returns an enumerator that is a struct, but its type could be custom
    // Next two calls are virtual via an interface, and enumerator is boxed
    var enumerator = enumerable.GetEnumerator();
    enumerator.MoveNext();
    return enumerator.Current;
}

And here IL for that method:

IL_0000: ldarg.1
IL_0001: callvirt instance class [mscorlib]System.Collections.Generic.IEnumerator`1<!0> class [mscorlib]System.Collections.Generic.IEnumerable`1<!!T>::GetEnumerator()
IL_0006: dup
IL_0007: callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()
IL_000c: pop
IL_000d: callvirt instance !0 class [mscorlib]System.Collections.Generic.IEnumerator`1<!!T>::get_Current()
IL_0012: ret

From the comments it looks like it is impossible to call the methods such as get_Current() without knowing the type.

An interesting question. Though I am not sure how you imagine an unsafe CIL method that uses a value type-returning *GetEnumerator*. You could either call the method via a pointer, but you'll still need to know the type it returns for the CLR to work with the returned value on the stack. *Reflection.Emit* is a better friend. — IS4, Feb 15 '17 at 14:48
@IllidanS4 I want to call such a method when I am sure that an input object implements that contract, and the question is it possible to call a method on object of a custom type by name using IL? Instead of Reflection.Emit I could write a method in IL and use ilasm.exe, so that I could call the generated method directly (not via a delegate). — V.B., Feb 15 '17 at 14:56
No, you cannot call a method by name in CIL. After CIL compilation, all method bindings are resolved to the specific method tokens, not names. CIL uses no contracts, you have to specify everything you use. In theory, you *could* represent such call with a generic method, if you pass the type returned from *GetEnumerator* as a generic type argument and use it as the return type, but I doubt that would even compile. CLR needs to know the size of the returned type when you call such a method. — IS4, Feb 15 '17 at 15:03
You're confusing two things: *unsafe* code is code in C# that produces *unverifiable* IL. The distinction is important because there exists verifiable IL that can't be produced by translating C#. In particular, it's possible to generate verifiable IL that uses a `call` instruction where the C# compiler would not -- in the process you might end up with a different method, but the code itself remains verifiable. Also, assuming that you know better than the combined forces of the C# compiler and the jitter is usually unwarranted. — Jeroen Mostert, Feb 15 '17 at 15:06
You say "allocating", but most of the IEnumerable implementations are structs, so there is no allocation going on there. Also if you are using generics you can avoid boxing/unboxing. — Andrey, Feb 15 '17 at 15:10
@Andrey When I use, e.g. `IEnumerable`, not `List`, the enumerator is boxed and `foreach` optimization doesn't apply. I updated my question with a concrete example. — V.B., Feb 15 '17 at 15:13
Here is code which lowers a `foreach` into the equivalent loop: https://github.com/dotnet/roslyn/blob/614299ff83da9959fa07131c6d0ffbc58873b6ae/src/Compilers/CSharp/Portable/Lowering/LocalRewriter/LocalRewriter_ForEachStatement.cs — Jacob Krall, Feb 15 '17 at 15:19
"I know that the `enumerable` returns an enumerator that is a struct, but its type could be custom" That is a different case to the one C# optimises for. It **does** know the exact type. Indeed, it's not even so much that C# optimises for it as that the normal C# behaviour is to look for `GetEnumerator()` on whatever type it is `foreach`ing and then look for `MoveNext()` and `Current` on whatever type is the result (`foreach` does not actually care about the `IEnumerable` interface). That naturally gives the most strongly typed implementation possible. — Jon Hanna, Feb 15 '17 at 15:29
@JonHanna well, negative answer is also a good answer! So there is no way to achieve the same result even with some unverifiable IL? — V.B., Feb 15 '17 at 15:42
The "same result" **is** IL (and verifiable too). The directly equivalent is that instead of the C# compiler going "oh, the type to use here is (e.g.) `List.Enumerator`" then **you** go "oh, the type to use here is `List.Enumerator`". To have it actually handled by the IL itself is like having it actually handled by the C# itself, which would be more akin to how e.g. some linq methods examine the type of an `IEnumerable` and pick a path optimised for that type. — Jon Hanna, Feb 15 '17 at 16:17
@V.B. I don't see any boxing in your example, am I missing something? — Andrey, Feb 15 '17 at 16:21
@Andrey when you use `List` as `IEnumerable`, the result of `GetEnumerator()` is boxed to `IEnumerator`. It is not directly in the example. — V.B., Feb 15 '17 at 16:28
@Andrey just because how .NET works - an interface does not reveal its underlying type. — V.B., Feb 16 '17 at 02:32

score 5 · Accepted Answer · answered Feb 15 '17 at 15:56

Let's have a couple of examples of how foreach gets compiled.
First, on a regular IEnumerator-returning GetEnumerator:

public class A : IEnumerable
{
    public IEnumerator GetEnumerator()
    {
        throw new NotImplementedException();
    }
}

foreach(object o in new A())
{

}

  .locals init (class [mscorlib]System.Collections.IEnumerator V_0,
           class [mscorlib]System.IDisposable V_1)
  IL_0000:  newobj     instance void Testing.Program/A::.ctor()
  IL_0005:  call       instance class [mscorlib]System.Collections.IEnumerator Testing.Program/A::GetEnumerator()
  IL_000a:  stloc.0
  .try
  {
    IL_000b:  br.s       IL_0014
    IL_000d:  ldloc.0
    IL_000e:  callvirt   instance object [mscorlib]System.Collections.IEnumerator::get_Current()
    IL_0013:  pop
    IL_0014:  ldloc.0
    IL_0015:  callvirt   instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()
    IL_001a:  brtrue.s   IL_000d
    IL_001c:  leave.s    IL_002f
  }  // end .try
  finally
  {
    IL_001e:  ldloc.0
    IL_001f:  isinst     [mscorlib]System.IDisposable
    IL_0024:  stloc.1
    IL_0025:  ldloc.1
    IL_0026:  brfalse.s  IL_002e
    IL_0028:  ldloc.1
    IL_0029:  callvirt   instance void [mscorlib]System.IDisposable::Dispose()
    IL_002e:  endfinally
  }  // end handler

Nothing wondrous here, just calling the methods on IEnumerator. Notice that it also implements IDisposable, hence it uses its pattern.

Next, let's have a value type-returning GetEnumerator:

public class B
{
    public BE GetEnumerator()
    {
        return new BE();
    }

    public struct BE
    {
        public object Current {
            get {
                throw new NotImplementedException();
            }
        }

        public bool MoveNext()
        {
            throw new NotImplementedException();
        }

        public void Reset()
        {
            throw new NotImplementedException();
        }
    }
}

  .locals init (class [mscorlib]System.Collections.IEnumerator V_0,
           class [mscorlib]System.IDisposable V_1,
           valuetype Testing.Program/B/BE V_2,
           object[] V_3,
           int32 V_4)
  IL_002f:  newobj     instance void Testing.Program/B::.ctor()
  IL_0034:  call       instance valuetype Testing.Program/B/BE Testing.Program/B::GetEnumerator()
  IL_0039:  stloc.2
  IL_003a:  br.s       IL_0044
  IL_003c:  ldloca.s   V_2
  IL_003e:  call       instance object Testing.Program/B/BE::get_Current()
  IL_0043:  pop
  IL_0044:  ldloca.s   V_2
  IL_0046:  call       instance bool Testing.Program/B/BE::MoveNext()
  IL_004b:  brtrue.s   IL_003c

Notice that nothing here has to implement IEnumerable/IEnumerator interfaces. This method is sometimes called duck-typing. This implementation internally stores the enumerator in a variable and then calls the methods on its address (ldloca). One value type copying happens here, when the enumerator is returned from GetEnumerator.

A third example is almost a completely different thing, foreach on an array:

foreach(object o in new object[0])
{

}

  .locals init (class [mscorlib]System.Collections.IEnumerator V_0,
           class [mscorlib]System.IDisposable V_1,
           valuetype Testing.Program/B/BE V_2,
           object[] V_3,
           int32 V_4)  IL_004d:  ldc.i4.0
  IL_004e:  newarr     [mscorlib]System.Object
  IL_0053:  stloc.3
  IL_0054:  ldc.i4.0
  IL_0055:  stloc.s    V_4
  IL_0057:  br.s       IL_0064
  IL_0059:  ldloc.3
  IL_005a:  ldloc.s    V_4
  IL_005c:  ldelem.ref
  IL_005d:  pop
  IL_005e:  ldloc.s    V_4
  IL_0060:  ldc.i4.1
  IL_0061:  add
  IL_0062:  stloc.s    V_4
  IL_0064:  ldloc.s    V_4
  IL_0066:  ldloc.3
  IL_0067:  ldlen
  IL_0068:  conv.i4
  IL_0069:  blt.s      IL_0059

This uses no GetEnumerator, and simply traverses the array in the old-fashioned index way (higher performance).

You cannot use this exact optimization in CIL, because CIL has no duck-typing; you have to write all the signatures and method calls yourself.

However, if you need to have this optimization for any type, and you can modify the types you want to use, you can use generic interfaces in a code similar to this:

public class B : IStructEnumerable<object, BE>
{
    public BE GetEnumerator()
    {
        return new BE();
    }
}

public struct BE : IStructEnumerator<object>
{
    public object Current {
        get {
            throw new NotImplementedException();
        }
    }

    public bool MoveNext()
    {
        throw new NotImplementedException();
    }

    public void Reset()
    {
        throw new NotImplementedException();
    }
}

public interface IStructEnumerable<TItem, TEnumerator> where TEnumerator : struct, IStructEnumerator<TItem>
{
    TEnumerator GetEnumerator();
}

public interface IStructEnumerator<TItem>
{
    TItem Current {get;}
    bool MoveNext();
    void Reset();
}

public static void TestEnumerator<TEnumerable, TEnumerator>(TEnumerable b) where TEnumerable : IStructEnumerable<object, TEnumerator> where TEnumerator : struct, IStructEnumerator<object>
{
    foreach(object obj in b)
    {

    }
}

Thanks! "because CIL has no duck-typing" is the thing I was not sure. — V.B., Feb 15 '17 at 16:03

How to implement C# foreach optimization in IL

1 Answers1

Linked