"Only called" delegate parameters

[TahirAhmadov]

Currently, some methods which accept a delegate parameter, have an overload for passing an argument to said delegate, in order to avoid creating a closure context, like Dictionary.GetOrAdd, etc.
I came up with an idea of how to accomplish the goal - allow closures without allocations - in a way which is universal. For methods which are known to call the delegate only and do not store it anywhere, we introduce a new keyword - onlycalled:

TValue GetOrAdd(TKey key, onlycalled Func<TKey, TValue> valueFactory)
{
  if(!this.TryGetValue(key, out var res))
    this[key] = res = valueFactory(key);
  this._valueFactory = valueFactory; // error: valueFactory cannot be stored
  return res;
}

void Foo(string prefix)
{
  string suffix = "def";
  var x = dict.GetOrAdd("abc", key => prefix + key + suffix);
}

What happens in the above case is that GetOrAdd signature guarantees that valueFactory is called only during execution of GetOrAdd, and suffix can therefore be accessed directly from the stack frame of Foo.

The next question became, how to implement this, and here I'm not 100% if it's feasible or how expensive it is.

[HaloFour]

I think this is relevant: #1060

I think trying to make this work with normal delegate types would require Object Stack Allocation.

[TahirAhmadov]

My idea was, the stackframe of Foo is known to the compiler; it generates a special un-speakable struct type, which matches the layout of the parameters/locals of Foo:

struct <MANGLED>Closure
{
  string prefix; // the parameters come first
  string suffix; // the locals come next
}

The GetOrAdd actually gets a signature like this:

struct OnlyCalledDelegate<T> // this is added to the BCL
{
  IntPtr ClosureStructRef;
  T Delegate;
}
TValue GetOrAdd(TKey key, OnlyCalledDelegate<Func<TKey, TValue>> valueFactory) { ... }

And when invoking GetOrAdd:

var x = dict.GetOrAdd(..., OnlyCalledDelegate.Create(key=> { ... }));

OnlyCalledDelegate.Create is a special helper method which stores Foo stackframe as IntPtr for later access. The delegate receives this parameter of type ref <MANGLED>Closure, and compiler changes accessing a closure variable like suffix to essentially this.suffix, similarly to calling a struct method. The aforementioned ClosureStructRef is un-safe converted to ref <MANGLED>Closure.

I hope what I wrote above isn't too crazy :)

[TahirAhmadov]

Actually, why not just add the delegate method as a member of the <MANGLED>Closure, and create a delegate whose Target is set to ref <MANGLED>Closure, but is actually the same value as the stackframe of Foo? Then we don't need OnlyCalledDelegate<T> at all, and the parameter is just decorated with a hidden attribute when onlycalled is used.

[svick]

why not [...] create a delegate whose Target is set to ref <MANGLED>Closure

I don't see how that would work. Target is an object and you can't store a ref in that.

[TahirAhmadov]

Duh, you're right, of course. Back to the OnlyCalledDelegate<T> struct idea.

[Xyncgas]

What if the function is inside a ref struct so it cant be stored and you can hide the Func<E,T> by making it private and call it some other way

[TahirAhmadov]

#2500

[TahirAhmadov]

#8760

[BlinD-HuNTeR]

There are a lot of proposals for improvement of Delegates and LINQ, and this is something that could benefit A LOT of people since delegates are used literally everywhere. I think it would be a good idea if all those proposals were "unified", similar to what happened in the past with the "Extensions" feature (there were lots of proposals with different approaches, and eventually the discussion was unified in a single place before deciding which approach would be taken)

I believe there are mainly 3 topics relevant to the optimization of delegates and LINQ queries:

• Zero-allocation delegates (struct delegates, but still with indirect calls using calli opcode)
• Zero-allocation of closures (struct closures, passed either by ref, or even by IntPtr, since they are on the stack, they can't be moved by GC)
• Functional interfaces w/ generics (make lambda expressions implement interfaces with a synthesized struct, and that struct is then passed as a type argument)

The last one would bring maximum performance since the delegates would then be invoked by direct calls instead of indirect (since they are structs, at runtime there will be 1 copy of the callee for every callback used in code, and the callee would call the callback DIRECTLY, possibly even inlining it).

However, it's also the hardest to implement, and even the hardest to use: every method that takes a callback would need to have an extra type parameter for the lambda, and that type parameter would be constrained to a "functional interface", that would also have type parameters, resulting in lots of boilerplate, unless all of that is "hidden" by the compiler (invisible type parameters added automatically when some well-known callback type is used by a method).

Nevertheless, there are already some 3rd-party LINQ libraries that support this approach, and the performance has been shown to beat even hand-written loops , when using manually-written struct callbacks. All that is needed is the syntax sugar to transform a lambda into a struct callback.

The other two approaches are less aggressive. They deal mainly with the allocation issue, since every non-static delegate incurs in two allocations, having zero-allocation delegates is nice, but other than that, nothing else would change performance-wise, since you still have indirect calls. Also the allocation problem could be solved at runtime-level with stack-allocation of objects, so I think these approaches are kind of "obsolete".

So, for the last approach, I could find proposals #8736 and #8816. But they are a bit outdated since they are from a time where we didn't have as much ref support as we do now. So I think we should start a new one, unifying this discussion (I could write that proposal myself, if it makes sense).

[TahirAhmadov]

@BlinD-HuNTeR isn't the third approach a more tailored feature which can't really replace all possible use cases for delegates?
Also, see #8816 (comment); I haven't seen anybody address that concern yet.
And, we still need the first item (struct delegates) for persisted "callbacks"; I'm not even talking about events (they need to be re-worked, too); but just a situation where you have a class which needs to store a callback to a single method, or it gets passed around many methods - no need to allocate an object just to wrap a method pointer.

[BlinD-HuNTeR]

@BlinD-HuNTeR isn't the third approach a more tailored feature which can't really replace all possible use cases for delegates?

Indeed, this feature is mostly intended to be used for callbacks that are going be called immediately (as this is the subject of this topic). Maybe some allowance could be made for LINQ too, since LINQ operators never invoke the callback immediately, but maybe, if the final query is going to be evaluated right away, it should be possible to make it work.

Also, see #8816 (comment); I haven't seen anybody address that concern yet.

That comment is talking about the "challenge" of dealing with mutations in struct closures. This is not a challenge at all. In fact, Roslyn already generates struct closures for local funcions, as long as the local function is never used in a delegate.

To use struct closures with delegates, the delegate needs to capture a reference to the struct closure at the time it is instantiated. This reference could either be a managed pointer (in which case the delegate needs to be a ref struct), or a plain IntPtr (which is possible since the closure is guaranteed to be on the stack). The only hard part is to have the compiler enforce that the delegate never outlives the closure. But I think we could use existing ref-safety analysis for that.

And, we still need the first item (struct delegates) for persisted "callbacks";

If the callback is going to be persisted, then the closure cannot be a struct. Only the delegate itself could be made to be a struct, which saves one allocation. If you think this is feature is worth having, then by all means, let's go for it!

What do you think of proposing "pattern-based" delegates? I mean, any user-defined type that exposes an Invoke method, and a constructor that takes object and IntPtr, would be recognized by the compiler as a delegate, and as such, it can be used as the target of lambda/method group, and its instances would be invocable.

[TahirAhmadov]

To use struct closures with delegates, the delegate needs to capture a reference to the struct closure at the time it is instantiated. This reference could either be a managed pointer (in which case the delegate needs to be a ref struct), or a plain IntPtr (which is possible since the closure is guaranteed to be on the stack). The only hard part is to have the compiler enforce that the delegate never outlives the closure. But I think we could use existing ref-safety analysis for that.

Which is basically the approach I outlined above, but I think others had ideas along these lines way before me writing it, so by no means I'm claiming any credit here for inventing something new (I just didn't find those discussions up until recently). That comment was responding to the #8816 specifically. It's entirely possible to make it work with ref structs, but nobody wrote up an updated proposal which accounts for it.

If the callback is going to be persisted, then the closure cannot be a struct.

Yes, struct delegates only address the alloc-free delegates need; it's not about closures. I mentioned it only because from your previous comment it seemed like you implied that they're not needed at all if we get something like #8816.