Proposal: enforced inlining of functions, including lambdas passed into them

[orthoxerox]

Kotlin does that, and enforced inlining would greatly improve the performance of LINQ to objects and LINQ to monads.

Let's say I have the following code:

using System;
public class C {
    public void M() {
        var h = "Hello";
        var w = " world";
        var hw = S(1, h, x => x + w);
    }
    
    public static T S<T>(int i, T input, Func<T, T> func)
    {
        return (i > 0) ? func(input) : default(T);
    }
}

It currently generates the following CIL (boring no-op ctors skipped):

//I can't believe GitHub has no CIL highlighting!
.class public auto ansi beforefieldinit C
    extends [mscorlib]System.Object
{
    // Nested Types
    .class nested private auto ansi sealed beforefieldinit Closure
        extends [mscorlib]System.Object
    {
        .custom instance void [mscorlib]System.Runtime.CompilerServices.CompilerGeneratedAttribute::.ctor() = (
            01 00 00 00
        )
        // Fields
        .field public string w

        // Methods
        .method assembly hidebysig 
            instance string Lambda (
                string x
            ) cil managed 
        {
            // Method begins at RVA 0x20bd
            // Code size 13 (0xd)
            .maxstack 8

            IL_0000: ldarg.1
            IL_0001: ldarg.0
            IL_0002: ldfld string C/Closure::w
            IL_0007: call string [mscorlib]System.String::Concat(string, string)
            IL_000c: ret
        } // end of method Closure::Lambda

    } // end of class Closure


    // Methods
    .method public hidebysig 
        instance void M () cil managed 
    {
        // Method begins at RVA 0x2050
        // Code size 45 (0x2d)
        .maxstack 4
        .locals init (
            [0] class C/Closure,
            [1] string,
            [2] string
        )

        IL_0000: newobj instance void C/Closure::.ctor()
        IL_0005: stloc.0
        IL_0007: ldstr "Hello"
        IL_000c: stloc.1
        IL_000d: ldloc.0
        IL_000e: ldstr " world"
        IL_0013: stfld string C/Closure::w
        IL_0018: ldc.i4.1
        IL_0019: ldloc.1
        IL_001a: ldloc.0
        IL_001b: ldftn instance string C/Closure::Lambda(string)
        IL_0021: newobj instance void class [mscorlib]System.Func`2<string, string>::.ctor(object, native int)
        IL_0026: call !!0 C::S<string>(int32, !!0, class [mscorlib]System.Func`2<!!0, !!0>)
        IL_002b: stloc.2
        IL_002c: ret
    } // end of method C::M

    .method public hidebysig static 
        !!T S<T> (
            int32 i,
            !!T input,
            class [mscorlib]System.Func`2<!!T, !!T> func
        ) cil managed 
    {
        // Method begins at RVA 0x208c
        // Code size 28 (0x1c)
        .maxstack 2
        .locals init (
            [0] !!T,
            [1] !!T
        )

        IL_0001: ldarg.0
        IL_0002: ldc.i4.0
        IL_0003: bgt.s IL_0010
        IL_0005: ldloca.s 0
        IL_0007: initobj !!T
        IL_000d: ldloc.0
        IL_000e: ret
        IL_0010: ldarg.2
        IL_0011: ldarg.1
        IL_0012: callvirt instance !1 class [mscorlib]System.Func`2<!!T, !!T>::Invoke(!0)
        IL_001b: ret
    } // end of method C::S

} // end of class C

A super-intelligent compiler could've rewritten this as if I've written the following code:

using System;
public class C {
    public void M() {
        var h = "Hello";
        var w = " world";
        var i = 1; //to prevent inlining
        var hw = (i > 0) ? h + w : default(string);
    }
}

.class public auto ansi beforefieldinit C
    extends [mscorlib]System.Object
{
    // Methods
    .method public hidebysig 
        instance void M () cil managed 
    {
        // Method begins at RVA 0x2050
        // Code size 25 (0x19)
        .maxstack 2
        .locals init (
            [0] string,
            [1] string
        )

        IL_0000: ldstr "Hello"
        IL_0005: stloc.0
        IL_0006: ldstr " world"
        IL_000b: stloc.1
        IL_000c: ldc.i4.1
        IL_000d: ldc.i4.0
        IL_000e: ble.s IL_0018
        IL_0010: ldloc.0
        IL_0011: ldloc.1
        IL_0012: call string [mscorlib]System.String::Concat(string, string)
        IL_0017: pop
        IL_0018: ret
    } // end of method C::M

} // end of class C

I believe it should be possible to achieve something close to this code by inlining S and the lambda passed into it, even when S is from another assembly, as long as S is static and doesn't read from or write to static fields:

(Please ignore invalid labels and nonexistent stloc/ldloc.X opcodes)

    // Methods
    .method public hidebysig 
        instance void M () cil managed 
    {
        // Method begins at RVA 0x2050
        // Code size 45 (0x2d)
        .maxstack 4
        .locals init (
            [0] class C/Closure,
            [1] string,
            [2] string,
			//new locals for arguments passing from M to S
			[3] int,
			[4] string,
			[5] class C/Closure,
			//locals of S
            [6] string,
            [7] string
			//new locals for arguments passing from S to the lambda
			[8] class C/Closure,
			[9] string
        )

        //We keep the closure to simplify the translation,
		//but the closure no longer has its methods
        IL_0000: newobj instance void C/Closure::.ctor()
        IL_0005: stloc.0
        IL_0007: ldstr "Hello"
        IL_000c: stloc.1
        IL_000d: ldloc.0
        IL_000e: ldstr " world"
        IL_0013: stfld string C/Closure::w
        IL_0018: ldc.i4.1
        IL_0019: ldloc.1
        IL_001a: ldloc.0
		//At this point our stack looks like this:
		// ... 1 "Hello" closure <
		//We store them in the new locals to simulate by value arguments:
		IL_new0: stloc.5
		IL_new1: stloc.4
		IL_new2: stloc.3
        //S invocation is removed and replaced with the modified body of S:
			//ldargs are replaced with ldlocs
			//rets are replaced with a branch to the end of the function
			//generics are specialized
			SIL_0001: ldloc.3 //ldarg.0
			SIL_0002: ldc.i4.0
			SIL_0003: bgt.s SIL_0010
			SIL_0005: ldloca.s 6 //0
			SIL_0007: initobj [mscorlib]System.String //!!T
			SIL_000d: ldloc.6 //ldloc.0
			SIL_000e: br.s SIL_new0 //ret
			SIL_0010: ldloc.5 //ldarg.2
			SIL_0011: ldloc.4 //ldarg.1
			//At this point the stack looks like this:
			// ... closure "Hello" <
			//We store them in the new locals to simulate by value arguments:
			SIL_new1: stloc.9
			SIL_new2: stloc.8
			//Delegate invocation is removed and replaced with the modified body of the lambda:
				//ldargs are replaced with ldlocs
				//rets are replaced with a branch to the end of the function
				LIL_0000: ldloc.9 //ldarg.1
				LIL_0001: ldloc.8 //ldarg.0
				LIL_0002: ldfld string C/Closure::w
				LIL_0007: call string [mscorlib]System.String::Concat(string, string)
				LIL_000c: br.s LIL_new0
				LIL_new0: nop			

			//back to S
			SIL_001b: br.s SIL_new0 //ret
			SIL_new0: nop
		
		//back to the outer method
        IL_002b: stloc.2
        IL_002c: ret
    } // end of method C::M

The resulting method is longer than the super-optimized one, but should be faster than the original double invocation.

Syntax

I don't care if it's an attribute or a new contextual keyword. It should be an error to mark a function as inline if it cannot be inlined because it manipulates external state.

Open questions:

• Can we avoid making defensive copies of by value args?
• What about by ref args? They should theoretically result in simpler code.
• Can the produced CIL be optimized post-emission?
• Generators
• Async

[svick]

How could this possibly work for framework methods (like the ones in Enumerable), considering that the C# compiler almost always compiles against reference assemblies and so it doesn't have access to their IL?

[orthoxerox]

@svick why doesn't it have access to their IL?

[svick]

@orthoxerox That's what reference assemblies are: assemblies containing only metadata, but no method bodies.

It's also what .Net Standard is about: you compile against an assembly that contains no method bodies, that part is up to the framework that ends up running the code.

[yaakov-h]

This can't work cross-assembly as you may be compiling against a reference assembly (as mentioned above), or the implementation in the other assembly can change by replacing the file on disk.

I reckon it could work internally within a single assembly though.

[jnm2]

But for things like the standard IEnumerable LINQ methods, you can ignore the actual implementation and inline the logic.

[yaakov-h]

Can you, considering that .NET Core has a more optimised implementation than .NET Framework, or that the implementation can change for many reasons including perhaps when DIM rolls around?

[jnm2]

This is what I'm talking about:

(from x in new[] { 1, 2, 3 } where x % 2 == 1 select x * 10).Sum()

Inlines the logic, not the extension method implementation, as:

var total = 0;
foreach (var x in new[] { 1, 2, 3 })
{
    if (x % 2 == 1) total += x * 10;    
}
total

The IL in the extension methods would be irrelevant because the compiler knows the semantics of System.Linq.Enumerable.Where, .Select, etc, and rolls its own ad-hoc specialized implementation in place.

[orthoxerox]

Looks like reference assemblies throw a wrench in the works. I wonder if inlining is possible during JITting, not compilation.

[HaloFour]

Well, that would be a pretty drastic change in the language spec. Currently all of the LINQ keywords do explicitly translate to methods following the LINQ convention. It doesn't even care if they are instance methods or extension methods. This enables designing LINQ capable APIs that aren't enumerable, or even compile-time specialization of LINQ implementations.

In fact, having the compiler explicitly rewrite LINQ keywords could break existing code. I can currently write extension methods to specialize LINQ implementations, e.g.:

public static class FooExtensions {
    public static IEnumerable<int> Where(this IEnumerable<int> source, Func<int, bool> predicate) { ... }
}

And the compiler will prefer that implementation over the one provided by the BCL.

[jnm2]

@HaloFour It's not the LINQ keywords that would be transformed, it's the System.Linq.Enumerable.* method calls themselves.

IOW this would also inline just the same:

new[] { 1, 2, 3 }.Where(x => x % 2 == 1).Select(x =>x * 10).Sum()

Your FooExtensions.Where would cause the whole thing to be un-inlinable because the assembly-qualified type name would not be recognized. Same with the IQueryable extension methods.

[HaloFour]

@jnm2

The C# compiler knows nothing about where any type/method comes from. And I don't think it should.

[jnm2]

And I do. =) At the very least, it should check the namespace and name like it does for ValueTuple.
Or provide a way to annotate a set of extension methods such that the compiler knows how to inline a specialized implementation.

[HaloFour]

@jnm2

Doesn't seem like the LDM does. They closed this very issue on Roslyn after declining it:

dotnet/roslyn#275

In my opinion LINQ inlining is something ripe for a post-compiler IL transformer or AOT compilation, if not JIT.

[Joe4evr]

In my opinion LINQ inlining is something ripe for a post-compiler IL transformer or AOT compilation, if not JIT.

And what do you know?

[jnm2]

I think it's inconsistent to have semantic understanding of ValueTuple by namespace and name if we can't have semantic understanding of System.Linq.Enumerable methods by name.

[orthoxerox]

@HaloFour what good would a rewritten tree be when you don't have access to neither the source nor the CIL of another function during compilation?

[alrz]

@HaloFour

Honestly this is one of those scenarios where I wished Roslyn would offer a way to rewrite syntax trees during compilation.

This relates to "modifying generators". The problem is that there is no sane way to debug such programs. If you step into a rewritten tree, what do you expect to see?

[orthoxerox]

@alrz What do I see when I step into an generatoriterator method?

[alrz]

Apparently nothing, because that ain't released yet mainly because of IDE story. Could be some .g.cs files?

With modifying generator we probably should see a whole new (rewritten) version of the compilation unit, even though only a part of it is being changed during compilation.

[orthoxerox]

@alrz Sorry, I meant generator as in a method with yield return. Its syntax tree is heavily rewritten during compilation, but you can step into it and step through without any issues.

[alrz]

@orthoxerox

I don't know what it would take to support a new construct in the debugger or ENC but the compiler and IDE know exactly what would be generated for a async or iterator state machine, etc. Since the output is known, IDE can handle the debugger behavior but it surely does not light up automatically. With a modifying generator there are infinite possible outputs to be handled so it could be really challenging.

[HaloFour]

@orthoxerox

what good would a rewritten tree be when you don't have access to neither the source nor the CIL of another function during compilation?

You mean for the content of the lambdas? IIRC Roslyn includes them inline with the syntax tree of the parent method, although I have very little experience working with Roslyn syntax nodes so I can't speak definitively as to how difficult this might be to interpret.

This relates to "modifying generators". The problem is that there is no sane way to debug such programs. If you step into a rewritten tree, what do you expect to see?

What would you expect to see if you stepped into a rewritten assembly? I guess in opting-in to such a step implies that the developer is throwing away the debug experience.

It's a shame. I think that LINQ to Objects optimization would be a fantastic feature, but it seems none of the teams at Microsoft are particularly interested in seeing it implemented or owning it. With LINQ syntax being as abstract as it is it's a shame that it can't just produce the fastest implementation possible. Then maybe performance-sensitive codebases (like Roslyn) could actually make more use of it.

[orthoxerox]

@HaloFour I mean for the content of Enumerable.Where and the rest of the gang.

Come to think of it, even when it's not LINQ to objects, but, say, @louthy's monads that you're trying to inline, the function you're trying to inline is in another assembly that you link dynamically to. You cannot do the inlining at compile time, since there's no guarantee that the library your executable will link to at runtime will be the same one.

[HaloFour]

@orthoxerox

I mean for the content of Enumerable.Where and the rest of the gang.

Oh, yes. I was going more with @jnm2's approach of special-casing System.Linq.Enumerable methods and translating that based on reasonable assumptions about their implementation. That's not something that I would recommend to be baked into the compiler, but I think that something like a "modifying generator" can be more aggressive about.

[orthoxerox]

You don't even have to special-case them, you could have System.Linq2.Enumerable methods that work with expression trees and compile them into a single method like Nessos Linq Optimizer does.

[jnm2]

Expression trees can be overly restrictive. What if I want to use tuples? Or null-safe dereference?

[svick]

@orthoxerox That works well for queries that operate on large sequences, but not for queries that are executed many times. For those, you either allocate and probably compile the expression trees many times, or you manually implement some form of caching. And you still have one delegate invocation per query (that's much better than LINQ to objects, but not perfect).

Rewriting C# or IL could offer better performance (no delegate invocation at all) and be more convenient than that (no need for manual caching, or anything like that).

[svick]

@jnm2 That's #158. I think that proposal has a good chance of being implemented before this one.

[Pzixel]

@jnm2 @svick there is already a tool that rewrites queries. We only need some way to integrate is smoothly into build process. I was thinking about it for several months but without any results yet.

[Thaina]

Was proposed since roslyn https://github.com/dotnet/roslyn/issues/11882