Proposal: Stack-allocated closures

[nothrow]

Problem

There are lot of places in code, where anonymous delegates (lambdas) passed to method are immediatelly evaluated, not stored, and when method returns, no longer used. This goes, for example, to ConcurrentDictionary.AddOrUpdate() calls.

However, such delegates and their closures are always allocated on heap.

Example:

using System;
using System.Linq;
using System.Collections.Concurrent;

class Counters
{
	private ConcurrentDictionary<string, int> _cd = new ConcurrentDictionary<string, int>();
	
	public void UpdateCounter(string counterName, int add)
	{
                /* allocate closure */
		_cd.AddOrUpdate("test", /* allocate delegate */_ => add, /* allocate delegate*/ (key, oldValue) => oldValue + add);
	}
}

Solution

Stack type delegates

Method accepting callback can declare it's intention not to store the callback with having ref System.ValueFunc<> / ref System.ValueAction<> parameter (similar to System.Threading.Tasks.ValueTask<>. That one will be ref readonly struct, so it can be kept on stack only, and also does not support multicasting.

ref readonly struct ValueFunc<TClosure, in T, out TResult>
{
    private IntPtr _methodPtr;
    private Pinnable<TClosure> _target;
}

When constructing the delegate from lambda, there is need to define that the lambda is actually value function. Proposal is to use ref keyword before the definition.

	_cd.AddOrUpdate("test", ref (_) => add, ref (key, oldValue) => oldValue + add);
  // calls AddOrUpdate(string, ref ValueFunc<closure, string, int>, ref ValueFunc<closure, string, int, int>);

Stack only closure

When compiler is building closure, it can enumerate all it's call-sites, and whenever every single call-site is referenced by ValueFunc<> (or alternative), it generates the closure as ref struct.

Rationale

The performance benefit is not game-changing, but reducing GC stress would be measurable.

[theunrepentantgeek]

This goes, for example, for LINQ queries.

LINQ queries are lazily evaluated - all of the lambda's used with LINQ are stashed away in member variables and only called if/when the enumerable requires.

Even if the expression was immediately evaluated with a ToList() call, LINQ couldn't/wouldn't benefit from this proposal because the deferred evaluation scenario is key to the design.

[nothrow]

Yes, but they could be still evaluated in scope of current method, as in my example (or when ended with ToArray()/ToList()/GetEnumerator() calls). 'Classic' Linq methods return IEnumerable<>.

Those can be done as something returning ref struct, when being passed the ValueFunc<>, so compiler prevents any boxing / IEnumerable<> leaking.

[HaloFour]

Yes, but they could be still evaluated in scope of current method

But they also might not be. In general the lambdas are assigned to fields on allocated iterator classes which are on the heap. This immediately violates the safety rules required for ref struct. Any given implementation of LINQ is a black box and there's nothing that the compiler can do to ensure that said implementation is a good actor.

[nothrow]

Valid points.

I will try to rephrase the proposal and examples not to use any LINQ.

[CyrusNajmabadi]

It is unclear to me what language change htis is proposing. This appears to be more about introducing a new API and having the compiler optimize in the presence of it. Do you think there would be any actual change to the language here?

[svick]

@CyrusNajmabadi

Do you think there would be any actual change to the language here?

I think converting lambdas to a type like ValueFunc would require language change.

[svick]

@nothrow

How exactly would closures work with your design? If closures were ref structs, then they couldn't be used as the TClosure type parameter. And even if that limitation was lifted, each ValueFunc would contain its own copy of the closure, not a reference to it, which would not work correctly if a closed over variable was mutated.

[nothrow]

I've updated the initial post, removed all LINQ-related stuff.

@CyrusNajmabadi, I suggest adding keyword to the language, that clearly marks the intent of creating ValueFunc. However, it also means adding new API, and learning compiler about it. Do you think this proposal belongs to other repo?

@svick, is unsafe out of discussion? I suggest using IntPtr for capturing the closure. Address of stack variable is always pinned anyway.

Some pseudo-compiler-generated code:

ref struct ValueAction<T> {
	private IntPtr closure;
    private IntPtr callback;
// CLR support would be handy here.
    public void Invoke(T p1) { callback.to_function.call(closure, p1); }
}

struct Closure {
	public int Value;
        
    public void MyCallback(int i)
    {
          Console.WriteLine(Value);
          Value = i;
    }
}

unsafe void Main()
{
	Closure closure;
	closure.Value = 4;
	
	ValueAction<int> vf = new ValueAction<int>
	{
		// closure = &closure,
		// callback = &closure.MyCallback
	};
	
	CallBackMe(ref vf);

	Console.WriteLine(closure.Value);	
}

void CallBackMe(ref ValueAction<int> vfc) {
	vfc.Invoke(10);
}

How would it look with my proposal:

void CallbackMe(ref ValueFunc<int> vfc) {
    vfc(10);
}

void Main() {
    int Value = 4;
    CallbackMe(ref (n) => {
        Console.WriteLine(Value);
        Value = n;
    });

    Console.WriteLine(Value);
}

Does this make sense?

[CyrusNajmabadi]

I think converting lambdas to a type like ValueFunc would require language change.

Could you clarify that? C# already knows how to convert lambdas to arbitrary delegates. Would there need to be a change here? Thanks!

[nothrow]

C# already knows how to convert lambdas to arbitrary delegates.

Yes, but in C#, delegate is always reference type (inherits from System.Delegate). My proposal adds completely new value-type delegate, incompatible with System.Delegate.

[svick]

@nothrow

Proposal is to use ref keyword before the definition.

I think it would be very confusing if ref (int i) => {} did something completely different than (ref int i) => {} (which is already valid syntax).

[benaadams]

Related: Proposal: Struct Lambdas #1060

[CyrusNajmabadi]

Yes, but in C#, delegate is always reference type (inherits from System.Delegate).

Nothing about inheriting from a class necessitates something being a reference type. For example, everything inherits from System.Object. All structs inherit from System.ValueType (which itself is a reference type). So we could certainly have a struct delegate type that derived from System.Delegate. I don't think the language would care at all :)

My proposal adds completely new value-type delegate, incompatible with System.Delegate.

In what way would it be incompatible?

[nothrow]

@CyrusNajmabadi good point. I considered the incompatibility as in "you can't upcast from ValueFunc to Delegate, or use Delegate.Combine on them" (since it would involve boxing), I did not realize that you can't upcast ref struct to ValueType. So the language can stay as-it-is, and implement this only on optimization level.

[DanielSchuessler]

Proposal is to use ref keyword before the definition.

I think it would be very confusing if ref (int i) => {} did something completely different than (ref int i) => {} (which is already valid syntax).

Does it need special syntax at the site of the lambda expression at all? Lambas require a target type anyway, so we could just make the lambda compile to a ValueFunc if that's the target type.

One could argue that the ref should be there a sort of warning that local variables can be mutated, but ordinary closures already do that! Lack of special syntax would allow library users to profit without changing their own code when the library migrates to ValueFunc (though there's no binary compat, of course, so the library would still have to increment its major version). Am I overlooking some dangerous change in behavior here?

Agreed that this isn't applicable to LINQ, but IMO there are many application where it would be useful, such as LINQ-like functions over materialized containers (arrays, lists, Maybe<T>, ...) and "wrapping scope"-type functions (TR WithDoSomethingOnException<TR>(ValueFunc<TR> body)).

[DanielSchuessler]

Addendum:

You can achieve almost the same thing today, like this (Sharplab):

public static T2[] Map<TStack, T1, T2>(
                    T1[] arr,
                    TStack env,
                    Func<TStack, T1, T2> func) 
{
    var result = new T2[arr.Length];
    for(int i = 0; i < arr.Length; i++) 
        result[i] = func(env, arr[i]);
    return result;
}

public static int[] Example(int[] arr, int i) {
    // Allocates only on first use; compiler stores this delegate in a static field
    return Map(arr, i, (i_, j) => i_ + j);
}

// Use some `RefFunc` delegate and pass `TStack` by ref if it might be big
// or you need to mutate it and reflect the changes back.

... but it's annoyingly verbose. So maybe it would be easier if we could just get some syntactic sugar for that?

[scalablecory]

It seems like Roslyn could automatically do this optimization. The only thing that might benefit is an attribute for method parameters that would indicate if the argument is stored for use after a method executes.

[jnm2]

Fyi, work has started on stack-allocated objects. dotnet/coreclr#20251

[declard]

Roslyn optimizations are cool, but such things are always a thin ice. What provides guarantees is types.

I'd propose that:

1. Structural delegates are represented with a family of readonly ref struct ValueFunc<...> types for each arity (e.g. readonly ref ValueFunc<TArg1, TArg2, TRes>), each of which contains an unmanaged pointer to a function and has Invoke method that pushes to the stack a ref to this along with the function pointer and performs calli
2. Structural closures are represented as anonymous structural types inheriting and subtyping from a ValueFunc (don't tell me it's impossible, it already works for enums) with Invoke function that corresponds to such for the already existing delegates

In such setup int F(in ValueFunc<int, int> f) => f(42); var y = 1; G(F(x => x + y)); would desugar into something like

readonly ref struct UnreadableScrewedName<>xy : ValueFunc<int, int>
{
  public int y;
  public UnreadableScrewedName<>xy()
    : base(UnmanagedPointerCompilerMagicGetter(Invoke)) { }
  int Invoke(int x) => x + y;
}
...
var closure<> = new UnreadableScrewedName<>xy();
closure<>.y = 1;
G(F(in closure<>));

Lambda expression syntax stays intact as lambdas already can specify to Func<..> or Expression<Func<..>> (as DanielSchuessler has noticed), so why whould a mechanism for ValueFunc<..> differ?

One of the drawbacks I see at the moment is that all those GetType and ToString methods can't behave as virtual, i.e. once you upcast from UnreadableScrewedName<>xy to ValueFunc<int, int> a run-time type info is erased. This can be handled by adding object header (sync + typeinfo) into ValueFunc which would, in turn, mean complications with boxing/unboxing (unless ValueFunc type itself is a ref struct) and on methods call site

[AartBluestoke]

Slightly OT:
It is always interesting to see the 2 points of view on a problem like this: "roslyn can optimize, and everyone would benefit" vs "We need a language guarantee because compiler optimisations are flaky, and sometimes can not make the assumption we would want to force them to (eg: nobody would argue that hints to force in-lining are not important). "

Variations of all the "what things can safely be left on the stack to make an operation non-allocating" set of discussions seems to be the primary place this occurs, and it often gets bogged down in escape analysis (eg: we can't do the above for lambdas because we can't force a complaint implementation).

This is especially true when many of the things we take as part of the language itself are merely an implementation detail (eg: async x.ConfigureAwait(false) ).

[YairHalberstadt]

Take a look at #2482 which investigates what it would take to make linq allocation free. ref struct closures are definitely a part of the story, but a lot more is needed as well :-)