How to emulate Expression.This() when using CompileToMethod

[rikimaru0345]

I'm using System.Linq.Expressions to implement formatters (serializers) for any type T.
At runtime everything works fine, but now I want to support IL2CPP (Unitys ahead-of-time compiler).
So I thought I'd just get a list of all types to be serialized in my serializer, and then compile those expressions using CompileToMethod and then saving them in an assembly.
That way - for IL2CPP - no code has to be compiled at runtime.

The issue is that the constants in the expression tree can't be saved, which is no surprise.
Each formatter (expression tree) has can have 0-N sub formatters that it uses to serialize the individual fields of its type. For example: A formatter IFormatter<Person> generated for class Person { public int Age; public string Name; } would itself contain IFormatter<int> and IFormatter<string> in order to serialize the two fields.

Ok, so it's obvious to me why this doesn't work.
So my idea now is to somehow replace the constants (the sub formatters) in the expression trees with fields!
So instead of genrating the two expressions (serialize and deserialize) of the IFormatter<Person> on their own, I would use DynamicType/TypeBuilder to generate a type that has fields for the needed formatters.
A Expression.Constant(stringFormatterInstance); I would generate something like Expression.MakeMemberAccess(???, stringFormatterField).

Now my problem is, there's no Expression.This() is there?
Also the LambdaCompiler seems to always want to include some sort of closure object. Maybe I can manually instantiate that somehow and use it as my "this"?

I'm a bit confused now regarding what my options are to actually solve this.
Maybe there's some other way to replace the constants when loading the generated assembly?
The solution obviously can't be anything that uses dynamic code generation, as the whole point is to have this run on an AOT platform.

[bartdesmet]

Unfortunately, System.Linq.Expressions's CompileToMethod can only emit static methods. A long time ago, I started a project that added support for classes, which is a bit involved because it needs to introduce some representation of symbols so one can refer ("ref") to members before they are being defined ("def"), e.g. to support methods calling each other. In the absence of this work, there are some approaches on the table.

Likely the easiest is to piggyback on closures and have a top-level single lambda expression that generates a function table and refers to variables defined in the outer scope (e.g. a BlockExpression with Variables on it). Here's an example of a getter/setter pair that uses shared state (i.e. emulating a field):

var x = Expression.Parameter(typeof(int));
var value = Expression.Parameter(typeof(int));

var f = Expression.Lambda<Func<Tuple<Func<int>, Action<int>>>>(
  Expression.Block(
    new[] { x },
    Expression.New(
      typeof(Tuple<Func<int>, Action<int>>).GetConstructor(new[] { typeof(Func<int>), typeof(Action<int>) }),
      Expression.Lambda<Func<int>>(x),
      Expression.Lambda<Action<int>>(Expression.Assign(x, value), value)
    )
  )
);

var g = f.Compile();

var obj = g();
var get = obj.Item1;
var set = obj.Item2;

set(42);
Console.WriteLine(get());

You could take it one step further by wrapping the whole thing in yet another Expression.Lambda so the top-level function is really akin to a constructor of a "type" (taking in a number of parameters), so each invocation of it returns an "instance" with a unique closure.

One drawback of piggybacking on the closures generated by the expression tree compiler is the baroque construction of StrongBox<T> objects in an object[] held by a Closure object, making each access rather expensive (field access + indexing + cast + field access). I got a prototype of a change to System.Linq.Expressions at https://github.com/bartdesmet/corefx/tree/CheaperClosures, which makes closures cheaper.

Given you're building a serializer, I suspect you may end up with cycles (e.g. if Person contains a field of type Person[] for Children). At that point, you're up for some puzzle, but likely the most pragmatic way to deal with it is to have your generated function take in a "serializer factory" that allows a serialization function to obtain a serializer for another type (likely a Func<Type, object> whose result can get cast). You'd then get the transitive closure of types starting from type T, build serializers for all of these, using the first parameter to obtain serializers for other types. All of these are then registered in some table, prior to calling the serializer.

A first final thought is that you can always emulate an object containing fields with a pair consisting of a function table (the methods defined on the type) and a tuple for the fields (using nesting of tuples if you have more than 8 fields, e.g. t.Rest.Rest.Item3).

A second final thought is that you can also "hoist" constants out of expressions and make them one or more parameters (e.g. a "constant table"). That's effectively what the expression compiler does as well through the first Closure parameter which has a field for hoisted constants (that cannot be loaded using IL instructions). The technique of constant hoisting can be useful to have explicit control over these constants (e.g. supplying a constant table at runtime) or to generalize code that's the same modulo constant values, thus reducing code generation by coalescing functions that are the same except for constants. I've used this technique extensively to build a high density service that relied on runtime code generation based on arbitrary user requests (which turn out to be often the same as a previous request, modulo some constants).

[rikimaru0345]

Hey @bartdesmet thank you for the in-depth answer!

I was thinking about this sort of "lambda generating a lambda" as well, but I wasn't entirely sure how that would work with expression trees (like if I can be sure that the lambda-compiler wouldn't sneak in a .Compile() somewhere for the inner lambda that gets constructed; because the whole point is to have absolutely no Compile calls, because there is no JIT).

I also had the idea that maybe I could "hack in" my own constants with reflection.
Like I'd replace the values of the constants with null, while preserving the type.
Then I'd compile the lambda to a method, save it to the assembly, and when loading I'd lookup the closure object and overwrite the constants in the closure with reflection.

So far, I unfortunately have not yet had the time to explore either of those ideas.

One thing that sounds a little scare is this part:

One drawback of piggybacking on the closures generated by the expression tree compiler is the baroque construction of StrongBox<T> objects in an object[] held by a Closure object, making each access rather expensive (field access + indexing + cast + field access).

I have only dabbled a bit in how the lambda compiler works. I inspected it with dnSpy and tried some basic reflection tricks to avoid / "jump over" the checks that ensure the method to emit into is static... (that obviously failed). But I haven't yet seen the StrongBox<T> type being used.
Anyway, you saying that there are some performance drawbacks is the scary thing.
Is that exclusive to the case where you have nested lambdas like that?
Or does something similar even happen with normal lambdas that use some constants that got dragged into a "Closure"?

One of the key parts of the thing I'm making is performance, so I definitely want to avoid any sort of casting, double-indirections, ...

Given you're building a serializer, I suspect you may end up with cycles (e.g. if Person contains a field of type Person[] for Children). At that point, you're up for some puzzle,

This scenario - cycles in the formatters, as well as cycles in the actual object-graph itself - is handled by: ReferenceFormatter.cs

The way it works is (I believe) as efficient as it gets given the constraints of the problem.
It compiles dynamic "dispatchers" (delegates) that are specialized per-type.
While there's still one cast remaining, I doubt that that one can be eliminated (but I'd love to be proven wrong :P).

A first final thought is that you can always emulate an object containing fields with a pair consisting of a function table (the methods defined on the type) and a tuple for the fields (using nesting of tuples if you have more than 8 fields, e.g. t.Rest.Rest.Item3).

Yeah, that's a good idea that I've played with as well, I'd essentially create a virtual object.
But the ugly part of that is that there's a type/object that already represents what I want to do (see here:
https://github.com/rikimaru0345/Ceras/blob/master/src/Ceras/Formatters/DynamicFormatter.cs ).
But I guess having that double indirection would not be too bad on the performance... (Hoping that the IL2CPP compiler can use its usual C++ compiler magic to de-virtualize all the additional cruft I'd add)

A second final thought is that you can also "hoist" constants out of expressions and make them one or more parameters (e.g. a "constant table").

So creating my own closure, yes. I'm not sure how realistic that is. Wouldn't that mean I'd have to create my own class FormatterTable<T1, T2, T3, ...> with an absolutely ridiculous number of generic arguments (one arg for every possible formatter!?)
Maybe I'm misunderstanding the idea though.

Anyway, thank you so much for the reply!! :)
I hope I have some more time soon to really get to know the ins and outs of the lambda compiler, and all the potential solutions / ideas floating around here now 😄

[rikimaru0345]

As for StrongBox<>, I think I see what you mean by that now.
The internal HoistedLocals just kinda represents this sort of case in normal C# code:

static void GetEntangledPair(out Action<int> setter, out Func<int> getter)
{
  int x = 0;
  setter = i => x = i;
  getter = () => x;
}

Where x would be a hoisted local. I've yet to investigate if that is only a compile-time representation or if it's actually compiled into the code in some way (leading to the performance degradation). The C# compiler doesn't have that issue though obviously. But from what you said it might indeed be used like that in some form :S

[bartdesmet]

The StrongBox<T> type is used primarily for closures, as a way to having single-variable closures (rather than bundling them all together in a "display class" as e.g. C# does). StrongBox<T> is nothing more than an object with a single field of type T, which can be used to take a ref in case the variable is to be passed to e.g. a ref or out parameter (an "lval").

Variables need to be hoisted in a number of cases, the most common of which is nested lambdas (and by extension the use of a Quote node which contains a Lambda). Another case is when using RuntimeVariables to get access to variables a runtime through an IRuntimeVariables object (used by dynamic languages). You can actually see a StrongBox<T> leaking into an expression tree if you write something like this:

Expression<Action<int>> f = x => Inspect(() => x);

void Inspect(Expression<Func<int>> f) { … }

The point is that a delegate produced by f.Compile() should have access to the same storage location as any other use site of x. As such, x will be a MemberExpression (for Value) over a ConstantExpression containing the StrongBox<T> which is the storage location for x.

My rewrite of closures effectively moved to the C# approach, by instantiating Closure<…> objects (akin to ValueTuple<…> types but with an IRuntimeVariables implementation). StrongBox<T> is still used for backwards compatibility in case it ends up in a Quote, where the caller may expect the Member(Constant(…), …) construction described above.

I'll see if I can share my "expression lambda compiler" internals write-up some time later this week. It'd been in perpetual draft, but it may be useful here.

[rikimaru0345]

My rewrite of closures effectively moved to the C# approach, by instantiating Closure<…> objects (akin to ValueTuple<…> types but with an IRuntimeVariables implementation). StrongBox<T> is still used for backwards compatibility in case it ends up in a Quote, where the caller may expect the Member(Constant(…), …) construction described above.

That totally makes sense. I was wondering why the existing implementation didn't do that already.
Making the closure itself generic would be so much better instead of having an object array of strongboxes that need to be casted back on every access...

One question though: Do you think it would be possible for me to somehow get this in a usable form? Like, surely a patch of that size will not be accepted as a PR that easily (I guess?), and even if it'd get accepted, it wouldn't necessarily help me for older platforms I want to support (or IL2CPP).

So is there maybe a way to use a custom LambdaCompiler with those changes, and have it re-use most of the existing parts of the existing LambdaCompiler through some hacky ways (just calling stuff through reflection)?
Or do you think that would quickly get out of hand and I'd have more luck with simply decompiling the whole System.Linq.Expressions.Compiler namespace and making my own thing from there?

[bartdesmet]

I was wondering why the existing implementation didn't do that already.

I don't have the full history on the original implementation, but there's definitely a tradeoff to be made. A few things that come to mind are:

• Bundling all hoisted locals together results in coupling the lifetimes of each of them, which is no different from the way C# does it.
• Instantiation of generic types (a Closure<> with many type arguments) has some JIT cost, but this is no different from Tuple<> types today.
• Using small single-cell StrongBox<T> instances could enable to pass a cell around, which is akin to passing a ref to a field in a bigger closure.

This said, my performance measurements show the savings on memory and closure field access paths are significant enough to consider it once/if System.Linq.Expressions gets some renewed attention.

surely a patch of that size will not be accepted as a PR that easily

Not easily indeed, given the risk of regressions. Expression trees have been plagued with compat issues before, and has been put on a list of assemblies to archive. See https://github.com/dotnet/corefx/issues/33170.

use a custom LambdaCompiler with those changes

It gets tricky quite quickly, at least from my experience trying to extend the existing functionality from an external assembly (see https://github.com/bartdesmet/ExpressionFutures which includes support for e.g. async lambda expressions).

You could also take a step back and reflect on the need to build whole types, which already requires a System.Reflection.Emit-based piece on top, causing the friction with the static methods generated by CompileToMethod. Maybe the benefits of using expression trees are rather limited, and it'd be doable to use System.Reflection.Emit all the way through? As far as I can understand, you merely need to traverse the structure of types (field reads, property gets, array indexing) and call type-specialized serialize methods, without any complex branching logic.

[ToddThomson]

• 1 vote for cheaper closed over variable access with lambda expressions.

I am writing a small dynamic DSL which transpiles to a lambda expression. I noticed the expense of closures when adding functional language features.

I am using the approach by @bartdesmet in ExpressionFutures to create extension expressions/statements and then reduce to get the IL required. @bartdesmet, I have reviewed your CheaperClosures and was thinking that rolling my own tuple based closures might be worth looking into. I do not want to fiddle with the lambda compiler, but perhaps adding a ClosureExpression to the generated lambda(s) might work. Any insights would be welcomed!

Argh...

  IL_0000: ldarg.0    
  IL_0001: ldfld      class [System.Linq.Expressions]System.Runtime.CompilerServices.Closure::Locals
  IL_0006: stloc.0    
  IL_0007: ldloc.0    
  IL_0008: ldc.i4.0   
  IL_0009: ldelem.ref 
  IL_000a: castclass  class [System.Private.CoreLib]System.Runtime.CompilerServices.StrongBox`1<int32>
  IL_000f: ldfld      class [System.Private.CoreLib]System.Runtime.CompilerServices.StrongBox`1<int32>::Value

[bartdesmet]

It's a bit involved but certainly doable to make the allocation profile of expression trees better by doing a rewrite of the tree prior to invoking Compile. You likely won't get as far as with a change to the guts of the compiler akin to my CheaperClosures branch. A possible sketch of a rewrite is outlined below.

Let's consider a simple example:

a => f(() => a)

where f expects a Func<int> as its argument. The generated closure here would really be a Closure with Locals containing a single slot of type StrongBox<int>. That's three heap allocations: the closure, the array of locals, and the box. The ceremony of the closure object and the locals array is hard to avoid without deeper surgery.

The low-hanging fruit whose cost can be reduced is the StrongBox<T> which holds the middle between a Tuple<T> and a ValueTuple<T>:

• It's like a Tuple<T>, because it's a class.
• It's like a ValueTuple<T>, because Item1 is a field (similar to Value).

We need the former to have a stable storage location (i.e. not having undesired copies showing up), but the latter because we need to get a ref to the storage location (e.g. when dealing with a MethodCallExpression targeting a method that has a ref or out parameter, and without write-back behavior that's non-atomic; the litmus test is whether Interlocked operations are functionally correct). Note we also need a strong type (i.e. not some object[] or so) because we can't box/unbox a value (you need to be able to get a ref T).

With that insight, you could rewrite the tree using ValueTuple<...>-based tuples that bundle all closed over variables in a scope and still rely on the LambdaCompiler to emit a closure (but now over just one variable). The analysis to find which variables need to be "closed over" is similar to what's done in the LambdaCompiler, namely to find definition and use sites of variables (and parameters) and figure out what needs to be hoisted into a closure (and what the access path to the variables is) because the definition and use sites cross lambda boundaries (or are referenced in RuntimeVariables). The analysis needs to keep track of scopes because Parameter nodes can shadow one another.

In the example above, a rewrite would look like:

a =>
{
  var t = new ValueTuple<int>(a);
  f(() => t.Item1);
}

where {...} is shorthand for a BlockExpression and ValueTuple<T> is a tuple type as described above (class with fields rather than properties).

However, you'll note that for our example, we haven't gained anything. We now have a LambdaCompiler-generated Closure instance whose Locals array contains a StrongBox<ValueTuple<int>>. Given that the ValueTuple<int> is a value, there's no additional heap allocation. Things are still ref-safe; something like t.Item1 in our rewritten tree is a MemberExpression that refers to a field. If it happens to be used "by ref", the lambda compiler will emit a ldflda instruction. Note that even though the memory cost has remained flat, the access path to the variable has gotten longer (from .Value on the box to .Value.Item1), so this technique has its limits.

Why bother if memory cost remains the same? Well, once you have many such variables that are closed over, you get memory savings because there's only one StrongBox<> instance and only one ValueTuple<...> that has all of the hoisted variables in it. However, the access path remains longer, and if you end up nesting tuples (e.g. after 7 slots), you end up with access paths like .Value.Rest.Rest.Item4. This can be avoided because you're in the business of runtime code generation, so it's relatively easy to build higher arity (generic) tuple types on the fly using System.Reflection.Emit.

Where my CheaperClosures edit to System.Linq.Expressions comes in is to remove the ceremony of the Closure and the object[] to hold the StrongBox<T> instances. First of all, the Closure object is only necessary if you both have (non-primitive) live constants as well as hoisted locals (both being kept in object[] arrays, thus Closure is two managed references, one of which is often null). Second, the object[] indirection containing StrongBox<T> instances is really a way to avoid having custom "display classes" (in C# parlance) or instantiations of generic tuple types (which weren't in the BCL at the time the lambda compiler went in during .NET Framework 3.5, and the tuples in .NET 4.0 were using properties as well). The CheaperClosures work removed this by using a tuple-like type with public fields (think of it as ManyStrongBoxes<T1, ..., Tn>). However, for compat, it figures out when variables are used within Quote nodes (where StrongBox<T> leaked into the quoted tree, so it keeps an additional StrongBox<T> wrapper for such variables) and RuntimeVariables nodes (where it needs special treatment to work correctly). Anyway, details are in that branch.

[ToddThomson]

Thanks for this @bartdesmet. Yes, perhaps too much work for not enough gain with the AST rewrite approach. I do have an Xpress.Language.Expressions port of S.L.Expressions so that I can make changes to the compiler and augment expression types if and when required.

My dream would be for the DLR to give a future growth path for S.L.Expressions ( including your ExpressionFutures and updates to the lambda compiler ).

[dotnet-policy-service]

Due to lack of recent activity, this issue has been marked as a candidate for backlog cleanup. It will be closed if no further activity occurs within 14 more days. Any new comment (by anyone, not necessarily the author) will undo this process.

This process is part of our issue cleanup automation.