Ref delegates

[vdebellabre]

The software I'm working on uses a fair amount of delegates (including Action, Func, lambdas and so on).
Some of them can point to static functions and allow us to save on heap allocations, but many of them are short-lived and use closures, requiring heap allocations at runtime. Short-lived meaning they only live for the duration of the function they're declared in (e.g. Parallel.ForEach with a lambda body).

The idea/question therefore is to wonder if the concept of ref delegates would make sense, in the same spirit as using ref structs. i.e. they would only live on the stack and would prevent any operation that would put them on the heap. With the goal of saving on allocations whenever possible.

I don't know enough about how delegates are handled under the hood to assess that idea, would that make any sense in c# ?

Edit : maybe that question should be in charplang ?

To be clear, we can avoid allocation already, but that requires making the called function static, and updating its signature to take a custom struct used to carry the captured variables. This works and is allocation free, but that's a lot of work and is not a viable long term solution. Maybe the compiler could do this automatically under the hood ?

[hez2010]

You can try function pointer instead.

[vdebellabre]

Function pointers = static functions, they won't work with closures.

[huoyaoyuan]

This should be "value delegates" discussed in csharplang repo.

[danmoseley]

transferred there.

[RikkiGibson]

The BCL has many places, especially in LINQ where we might want something like this. We know the delegate passed as an argument to .Where() won't escape the call, so why not come up with some kind of delegate that can be created without heap allocation?

My instinct about this is that it's going to be really prohibitive to multiply out all the new methods to ensure we benefit from this across the ecosystem. I know that a whole lot of ink has already been spilled about how we could optimize LINQ. I'm not up to speed on all of it but it's very likely that "value delegates" have been explored in some depth already. It would be good to dig that up and review what people have already considered.

I would be interested to explore whether we can get this optimization without introducing a fundamentally new function type. This could happen via runtime escape analysis, or by compile-time annotations and checking, etc. I'm optimistic that this could get us to land where we want.

[TahirAhmadov]

We know the delegate passed as an argument to .Where() won't escape the call, so why not come up with some kind of delegate that can be created without heap allocation?

How is that possible given that LINQ is deferred? What if the method that calls .Where simply returns the resulting IEnumerable<T>?

I think this would be solved by creating a whole new set of methods, all of which operate with stack-only types. Basically, IEnumerable<T> would get an extension method, AsStruct() or something, which would return a StructEnumerable<T>, which would be a ref struct, and then you can think about optimizing all these methods - new Where(), etc.

[HaloFour]

@TahirAhmadov

Once you have the IEnumerable<T> it's already too late. You'd need the ref struct version from the start, with both the source and target being passed by ref to every single method in the chain. Not saying that it's not possible, but it would be involved and completely incompatible with the existing ecosystem.

[333fred]

One of the reasons I'm interested in championing associated types is that I believe it's one of the required steps on the way to a usable version of Linq that is stack-only. Once you have that, ref structs that can impl interfaces, and the ability to put ref structs in generics, you can make it work.

[TahirAhmadov]

Yes I just did some experimenting and this would be an entirely new system complete with its own enumeration approach, either using associated types FastEnum approach or something similar. It is, however, possible to use IEnumerable<T> as an input.

MY SCRATCH PAD

using System;
using System.Collections.Generic;

namespace RefStructEnumerable
{
	class Program
	{
		static void Main()
		{
			var list = new List<int> { 1, 2, 3, };
			var structEnumerable = list.AsStruct();

			foreach (int x in structEnumerable)
			{
				Console.WriteLine(x);
			}

			foreach (int x in structEnumerable.Select(y => y * 2))
			{
				Console.WriteLine(x);
			}
		}
	}
	public static class _IList_T_Extensions
	{
		public static StructEnumerable<T> AsStruct<T>(this IList<T> This)
		{
			return new StructEnumerable<T>(This);
		}
	}
	public delegate bool MoveNextDelegate(ref object state);
	public delegate T GetCurrentDelegate<T>(object state);
	public ref struct StructEnumerable<T>
	{
		public StructEnumerable(IEnumerable<T> source)
		{
			this._moveNext = (ref object state) =>
			{
				if (state is not IEnumerator<T> enumerator) state = enumerator = source.GetEnumerator();
				return enumerator.MoveNext();
			};
			this._getCurrent = state => ((IEnumerator<T>)state).Current;
		}
		public StructEnumerable(IList<T> source)
		{
			this._moveNext = (ref object state) =>
			{
				if (state is not int index) index = -1;
				bool res = ++index < source.Count;
				state = index;
				return res;
			};
			this._getCurrent = state => source[(int)state];
		}
		public StructEnumerable(MoveNextDelegate moveNext, GetCurrentDelegate<T> getCurrent)
		{
			this._moveNext = moveNext;
			this._getCurrent = getCurrent;
		}

		public StructEnumerator<T> GetEnumerator() => new StructEnumerator<T>(this);
		public StructEnumerable<T2> Select<T2>(Func<T, T2> selector)
		{
			var getCurrent = this._getCurrent;
			return new StructEnumerable<T2>(this._moveNext, state => selector(getCurrent(state)));
		}

		internal MoveNextDelegate _moveNext;
		internal GetCurrentDelegate<T> _getCurrent;
	}
	public ref struct StructEnumerator<T>
	{
		public StructEnumerator(StructEnumerable<T> enumerable)
		{
			this._enumerable = enumerable;
			this._state = null;
		}
		public bool MoveNext()
		{
			return this._enumerable._moveNext(ref this._state);
		}
		public T Current
		{
			get
			{
				return this._enumerable._getCurrent(this._state);
			}
		}
		readonly StructEnumerable<T> _enumerable;
		object _state;
	}
}

[RikkiGibson]

How is that possible given that LINQ is deferred? What if the method that calls .Where simply returns the resulting IEnumerable<T>?

You're right, LINQ is not a great example. You do actually
need something like what Fred has outlined where the returned enumerable contains embedded references and the compiler does the escape analysis. That means a new set of APIs.

[erik-kallen]

I might be falling into the "sufficiently smart compiler" trap here, but shouldn't the runtime be able to figure out this through escape analysis?

[TahirAhmadov]

The challenge isn't the compiler - rather it's the possibility that IEnumerable is actually enumerated after the current method returns, in which case what was on the stack is no longer there, hence the need for a heap object.

[erik-kallen]

Yes, but the runtime can figure this out for each call site if it is good enough at escape analysis.

[vdebellabre]

I understand the point made for IEnumerables but that is not really what I was talking about originally.

Consider the following code

public void M()
{
    int n = Random.Shared.Next(100);
    Func<int, int> myFunc = Random.Shared.Next(2) switch {
        0 => x => x + n,
        _ => x => x - n,
    };
    Console.WriteLine(myFunc(Random.Shared.Next(100)));
}

Because of the captured variable n, the function cannot be made static and the delegate will require a heap allocation at runtime.

This can be manually solved by declaring a custom struct to carry the capture :

private readonly struct MyParams { public int N { get; init; } }
public void M2() {
    int n = Random.Shared.Next(100);
    Func<int, MyParams, int> myFunc = Random.Shared.Next(2) switch {
        0 => static (x, p) => x + p.N,
        _ => static (x, p) => x - p.N,
    };
    Console.WriteLine(myFunc(Random.Shared.Next(100), new MyParams { N = n }));
}

Notice that the delegate declaration can now be static and won't require any heap allocation at runtime.
This is what I'm looking for, and while it is fairly easy to do, that method can't really be generalized to an entire application.
So I was wondering if some kind of automation could be applied by the compiler somehow.

Edit : in this example the struct isn't required per see, but sometimes there are several captured variables and it's simply easier to pack them into a single struct.