www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Idea for avoiding GC for lambdas

reply Steven Schveighoffer <schveiguy gmail.com> writes:
I have some code in my codebase that does stuff like this:

```d
struct S
{
    int id;
    int field1;
}

auto foo(S[] arr, int someval) //  nogc not allowed :(
{
    // remove all the elements of arr that have someval for field1
    import std.algorithm;
    return arr.filter!(v => v.field1 == someval);
}
```

While this works, and is nice, it's using a lambda with local references 
to filter data. This means a GC closure allocation is involved.

However, the value that is referenced (someval) is the only thing 
needed, and it seems a huge waste to allocate a stack frame *just* for that.

Let's look at another way to do this. `filter` does not have an overload 
which accepts a *value* to compare to, but `find` does. So let's build a 
new `filter` that uses it:

```d
auto nogcfilter(alias pred, T, V)(T[] rng, V val)
{
     import std.range;
     import std.algorithm : find;
     static struct Filter {
         T[] src;
         V val;
         auto front() { return src.front; }
         void popFront() {src.popFront; src = src.find!pred(val); }
         auto empty() { return src.empty; }
     }
     return Filter(rng, val);
}

auto foo(S[] arr, int someval)  nogc // :)
{
    // note: the explicit lambda types are needed for some reason
    return arr.nogcfilter!((S v, int a) => v.field1 == a)(someval);
}
```

Now we get filter capability, but without the GC.

This works great because the context items used do NOT require any 
mutability. It also works great because the filter function is building 
a custom type ANYWAY.

Now, we could add this kind of functionality to `filter`, but being the 
lazy programmer that I am, what if the compiler could do this for me? In 
most cases, I don't want to sleuth out what context is needed (which 
might change as the code evolves). To force the user to both invent the 
context type (here, it's just an `int`, but it may require other values) 
and explicitly pass it is a bit verbose (I already don't like having to 
pass the `int`, and declaring the parameter).

What if, a function that accepts a lambda, could also accept a *context* 
which the compiler made up and passed in? Here's how it would possibly 
look (with a new magic type `__context`):

```d
auto nogcfilter(alias pred, T, __context...)(T[] rng, __context ctxt)
{
     import std.range;
     import std.algorithm : find;
     static struct Filter {
         T[] src;
         __context val;
         auto front() { return src.front; }
         void popFront() {src.popFront; src = src.find!pred(val); }
         auto empty() { return src.empty; }
     }
     return Filter(rng, ctxt);
}

auto foo(S[] arr, int someval)  nogc
{
    return arr.nogcfilter!((v) => v.field1 == someval);
}
```

The compiler would see there's a lambda involved, automatically pass the 
context parameter `someval` into the function itself, and everything 
magically works. It would only be used when a closure would otherwise be 
allocated, and the function being called declares the context parameter.

Disclaimer: I am not a language developer.

Does this make sense? Is there anything feasible that might be similar? 
Would it be more feasible with different syntax?

I realize there are implications if the context parameter is mutable, so 
perhaps we would have to require only const contexts (though the 
compiler might be able to figure out that something isn't modified 
anywhere, and allow it to go in).

-Steve
Jun 21 2021
next sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/21/21 4:01 PM, Steven Schveighoffer wrote:

     // remove all the elements of arr that have someval for field1


Obviously, that should have said *include* all the elements that have 
someval.

-Steve
Jun 21 2021
prev sibling next sibling parent reply Elronnd <elronnd elronnd.net> writes:
The reason delegates involve GC is because the closure is shared. 
  E.G.:

int x;
auto f = () => x++;
auto g = () => x++;
f(); //0
g(); //1
f(); //2

f and g share a reference to the same x, so we need GC to know 
when to clean it up.

Your proposal is essentially a value delegate; the __context 
stuff makes that explicit, but it's not actually fundamentally 
different from the current scheme, it's just that the context 
becomes a value type rather than a reference type.

I think value closures are a good idea--for semantics reasons 
too, not just avoiding gc--but problematic for existing APIs to 
support, because every value closure will have a different type 
and a different size.  And we have enough problems already with 
compile time template explosion :)

WRT your proposal, I think it would be better to introduce an 
alternate syntax for function literals: we have  function(parm) 
=> ret  and  delegate(parm) => ret; add  valuedelegate(parm) => 
ret.  And make it so that valuedelegate.ptr is a struct (the 
context struct) so you can still introspect it if needed.


 I realize there are implications if the context parameter is 
 mutable, so perhaps we would have to require only const contexts


Why?  What you've made is basically a functor where the compiler 
infers the context; structs are received by reference (by their 
methods).  If the context were shared, then const wouldn't be 
enough; it would have to be immutable to retain value semantics.  
But the whole point of this was to avoid sharing (and hence GC), 
so I don't see why that would be a problem.
Jun 21 2021
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/21/21 6:19 PM, Elronnd wrote:

 The reason delegates involve GC is because the closure is shared.  E.G.:
 
 int x;
 auto f = () => x++;
 auto g = () => x++;
 f(); //0
 g(); //1
 f(); //2


Yes, but only necessary if the data is mutated.


 Your proposal is essentially a value delegate; the __context stuff makes 
 that explicit, but it's not actually fundamentally different from the 
 current scheme, it's just that the context becomes a value type rather 
 than a reference type.


Right, I honestly don't know how the context is passed for an alias 
parameter. The compiler must pass some sort of context pointer to the 
calling function, which then gets stored somehow. But it's all hidden. 
If it's hidden, it might as well be as big as needed.


 I think value closures are a good idea--for semantics reasons too, not 
 just avoiding gc--but problematic for existing APIs to support, because 
 every value closure will have a different type and a different size.


Remember, these aren't delegates in the strict sense, they are alias 
parameters. They can be implemented however D wants. Take a look at the 
`filter` 
[implementation](https://github.com/dlang/phobos/blob/61c00065a8c7efdf21efb92ce69d7a9de4904ec9/std/algorithm/itera
ion.d#L1371-L1432), 
there's not a delegate in sight.


 And we have enough problems already with compile time template explosion :)


This shouldn't have a significant effect on templates -- aliases are 
already unique parameters, causing a new template for every call.


 
 WRT your proposal, I think it would be better to introduce an alternate 
 syntax for function literals: we have  function(parm) => ret  and  
 delegate(parm) => ret; add  valuedelegate(parm) => ret.  And make it so 
 that valuedelegate.ptr is a struct (the context struct) so you can still 
 introspect it if needed.


I'm unsure if this is how it works, the alias parameters aren't exactly 
delegates, though that might be how the compiler implements them.

My thought was that the compiler could pick to send the function alias 
in as a straight alias (without context) and pass the context in as a 
separate parameter. The function itself would have a type that accepts 
the context data.


 I realize there are implications if the context parameter is mutable, 
 so perhaps we would have to require only const contexts


 
 Why?  What you've made is basically a functor where the compiler infers 
 the context; structs are received by reference (by their methods).  If 
 the context were shared, then const wouldn't be enough; it would have to 
 be immutable to retain value semantics. But the whole point of this was 
 to avoid sharing (and hence GC), so I don't see why that would be a 
 problem.


I mean non-changeable contexts. These can be const data, as long as they 
aren't const references, they should be unchangeable.

I.e. the compiler should be able to pass an x like:

```d
const x = 5;
```

-Steve
Jun 22 2021
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Jun 22, 2021 at 11:05:18AM -0400, Steven Schveighoffer via
Digitalmars-d wrote:

 On 6/21/21 6:19 PM, Elronnd wrote:


[...]

 Your proposal is essentially a value delegate; the __context stuff
 makes that explicit, but it's not actually fundamentally different
 from the current scheme, it's just that the context becomes a value
 type rather than a reference type.


 
 Right, I honestly don't know how the context is passed for an alias
 parameter. The compiler must pass some sort of context pointer to the
 calling function, which then gets stored somehow. But it's all hidden.
 If it's hidden, it might as well be as big as needed.


AFAIK, delegates are essentially just:

	struct __dg {
		void* context;
		RetType function(void* context, Args...) func;
	}

An alias parameter, being a template parameter, simply causes the
aliased function to get template-expanded in the body of the delegate.
Any context it carries must be shared with the delegate's context, which
is the source of the recent issue with multi-context template functions
that resulted in the compiler change getting reverted.

The context must be stored *somewhere*, usually on the GC heap, which is
why delegates depend on the GC. Except for scope delegates where it's
guaranteed that the parent scope won't go out of scope before the
delegate does, so the context pointer can just point to the stack where
the parent's scope is stored.

Unless I'm missing something obvious, I don't think value delegates
would work well with D, because it's pretty important for delegates with
the same parameter and return types to be interchangeable. I.e., two
delegates with external type `int delegate(string)` must have the same
fixed size and memory layout, regardless of the size of the context of
one delegate vs. the other, otherwise you have a pretty serious problem
at the language level.


T

-- 
Everybody talks about it, but nobody does anything about it!  -- Mark Twain
Jun 22 2021
next sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/22/21 12:13 PM, H. S. Teoh wrote:


 Unless I'm missing something obvious, I don't think value delegates
 would work well with D, because it's pretty important for delegates with
 the same parameter and return types to be interchangeable. I.e., two
 delegates with external type `int delegate(string)` must have the same
 fixed size and memory layout, regardless of the size of the context of
 one delegate vs. the other, otherwise you have a pretty serious problem
 at the language level.


This again, is a misunderstanding of my proposal. I'm not talking about 
altering delegates in any way.

There are no delegates involved in `filter`. It is, instead, an inner 
struct with a hidden context pointer. Could just as well be a struct 
with context carried with it instead of allocated on the heap.

Note that this generates 2 *different* `FilterResult` instances, because 
they are 2 different lambdas:

```d
int[] arr = [1, 2, 3];

auto f1 = arr.filter!(v => v % 2);
atuo f2 = arr.filter!(v => v % 2);
static assert(!is(typeof(f1) == typeof(f2)));
```

I'm unclear how the compiler generates and passes the context, but I 
know that it uses the GC. However, it would be reasonable to allow 
functions to accept the context by value (if it makes sense). One way to 
do this is to work out whether you can do it by value, and use that if 
possible. Another way is to explicitly have different syntax to pass the 
context by value.

I was hoping for a possible way forward where the compiler figures it 
all out for me.

-Steve
Jun 22 2021
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Jun 22, 2021 at 03:56:03PM -0400, Steven Schveighoffer via
Digitalmars-d wrote:
[...]

 This again, is a misunderstanding of my proposal. I'm not talking
 about altering delegates in any way.
 
 There are no delegates involved in `filter`. It is, instead, an inner
 struct with a hidden context pointer. Could just as well be a struct
 with context carried with it instead of allocated on the heap.


[...]

Ohhh I see what you mean now. So essentially what you're saying is,
whenever there's an alias parameter bound to a lambda, the compiler
should, in effect, insert additional parameters to the template
function that captures the context the lambda is bound to?

IOW, this:

	auto filter(alias fun, R)(R range) {
		struct Voldemort {
			...
			if (fun(range.front)) ...
			...
		}
		return Voldemort(range);
	}

	int x = 2, y = 3;
	auto r = [1, 2, 3].filter!(e => e == x || e == y);

gets lowered into something like this:

	struct __lambda_context {
		int x, y;
	}
	bool __lambda_fun(__lambda_context ctxt, int e) {
		return e == ctxt.x || e == ctxt.y;
	}
	auto __filter_instance(R)(__lambda_context ctxt, R range) {
		struct Voldemort {
			__lambda_context secretCtxt;
			...
			if (__lambda_fun(secretCtxt, range.front)) ...
			...
		}
		return Voldemort(ctxt, range);
	}

	int x = 2, y = 3;
	auto r = __filter_instance(__lambda_context(x, y), [1, 2, 3]);

Am I right?

__lambda_context may not necessarily carry a copy of the captured
variables; possibly it could use pointers instead. Though care would
have to be taken not to leave dangling pointers to out-of-scope local
variables -- probably you'd have to make the references `scope` unless
you copy them by value into the Voldemort struct.


T

-- 
Не дорог подарок, дорога любовь.
Jun 22 2021
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/22/21 5:31 PM, H. S. Teoh wrote:

 On Tue, Jun 22, 2021 at 03:56:03PM -0400, Steven Schveighoffer via
Digitalmars-d wrote:
 [...]

 This again, is a misunderstanding of my proposal. I'm not talking
 about altering delegates in any way.

 There are no delegates involved in `filter`. It is, instead, an inner
 struct with a hidden context pointer. Could just as well be a struct
 with context carried with it instead of allocated on the heap.


 [...]


[snip]


 Am I right?


Yes, exactly! The only tricky part is that the filter function has to 
explicitly accept the context so it can tell the compiler where to put 
the context.

Essentially, it gives a place to accept the context and has the compiler 
give it a way to forward that context to the lambda function(s).

It may be trickier than I originally wrote, but the goal is to avoid 
having to do any work as a user (the library can be instrumented as much 
as we want), and the compiler just does the right thing.

-Steve
Jun 23 2021
prev sibling parent IGotD- <nise nise.com> writes:
On Tuesday, 22 June 2021 at 16:13:06 UTC, H. S. Teoh wrote:

 The context must be stored *somewhere*, usually on the GC heap, 
 which is why delegates depend on the GC. Except for scope 
 delegates where it's guaranteed that the parent scope won't go 
 out of scope before the delegate does, so the context pointer 
 can just point to the stack where the parent's scope is stored.


The way C++ works is that a lambda (which is essentially a 
template class) when you pass it to a function/method it will be 
converted to an std::function. Inside of std::function it will 
store context data on the heap. However, it has some "SSO" 
capability meaning if the captures are few and small it might fit 
into meta data of std::function. Essentially this is the same SSO 
(short string optimization) strategy for std::string.

Not sure if this helps but for small lambdas that does simple 
things like in the initial example, the context could easily be 
stored in the struct.

Now the problem is in D the delegate is very small, while in C++ 
it is probably more going on like reference counting making 
std::function bigger than in D. Making structs bigger isn't 
always that popular.
Jun 22 2021
prev sibling next sibling parent reply Ola Fosheim Grostad <ola.fosheim.grostad gmail.com> writes:
On Monday, 21 June 2021 at 20:01:27 UTC, Steven Schveighoffer 
wrote:

 The compiler would see there's a lambda involved, automatically 
 pass the context parameter `someval` into the function itself, 
 and everything magically works. It would only be used when a 
 closure would otherwise be allocated, and the function being 
 called declares the context parameter.

 Disclaimer: I am not a language developer.

 Does this make sense? Is there anything feasible that might be 
 similar? Would it be more feasible with different syntax?


You are asking for C++ lambdas? No need for a new type of 
template parameter.
Jun 21 2021
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/22/21 1:57 AM, Ola Fosheim Grostad wrote:

 On Monday, 21 June 2021 at 20:01:27 UTC, Steven Schveighoffer wrote:

 The compiler would see there's a lambda involved, automatically pass 
 the context parameter `someval` into the function itself, and 
 everything magically works. It would only be used when a closure would 
 otherwise be allocated, and the function being called declares the 
 context parameter.

 Disclaimer: I am not a language developer.

 Does this make sense? Is there anything feasible that might be 
 similar? Would it be more feasible with different syntax?


 
 You are asking for C++ lambdas? No need for a new type of template 
 parameter.
 


I was kinda hoping for the compiler to assist in the generation and 
management of the context data since it's already doing it. The 
receiving function just needs a variable to receive and pass the context 
data to the lambda.

-Steve
Jun 22 2021
parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= <ola.fosheim.grostad gmail.com> writes:
On Tuesday, 22 June 2021 at 14:49:34 UTC, Steven Schveighoffer 
wrote:

 I was kinda hoping for the compiler to assist in the generation 
 and management of the context data since it's already doing it. 
 The receiving function just needs a variable to receive and 
 pass the context data to the lambda.


Off the top of my head:

I think it should just be an ordinary template parameter. Then 
you can let the compiler do the optimization if is possible 
without changing the semantics.

That way it isn't a language change.

So you could instead just introduce a UDA that signals that a 
compiler should issue a warning if it cannot do the optimization?

Or am I wrong?
Jun 23 2021
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/23/21 7:04 AM, Ola Fosheim Grøstad wrote:

 On Tuesday, 22 June 2021 at 14:49:34 UTC, Steven Schveighoffer wrote:

 I was kinda hoping for the compiler to assist in the generation and 
 management of the context data since it's already doing it. The 
 receiving function just needs a variable to receive and pass the 
 context data to the lambda.


 
 Off the top of my head:
 
 I think it should just be an ordinary template parameter. Then you can 
 let the compiler do the optimization if is possible without changing the 
 semantics.
 
 That way it isn't a language change.


Well, the library function needs to signify to the compiler that the 
parameter is meant to accept the value context. Otherwise, really odd 
things might happen with existing template parameters.


 So you could instead just introduce a UDA that signals that a compiler 
 should issue a warning if it cannot do the optimization?
 
 Or am I wrong?
 


A UDA might work.

-Steve
Jun 23 2021
parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= <ola.fosheim.grostad gmail.com> writes:
On Wednesday, 23 June 2021 at 13:43:21 UTC, Steven Schveighoffer 
wrote:

 A UDA might work.


Ok, so you use a templated filter function with a regular 
delegate for the parameter, but the delegate parameter is adorned 
with  __nogc_lambda. Then the compiler turns the  __nogc_lambda 
delegate into a context.

Compilers that don't support  __lambda will simply gc-allocate 
the lambda? So it is a nonbreaking extension.

Is that good enough? If so, then we can do it without a DIP.
Jun 23 2021
prev sibling next sibling parent reply rm <rymrg memail.com> writes:
On 21/06/2021 23:01, Steven Schveighoffer wrote:

 I have some code in my codebase that does stuff like this:
 
 ```d
 struct S
 {
     int id;
     int field1;
 }
 
 auto foo(S[] arr, int someval) //  nogc not allowed :(
 {
     // remove all the elements of arr that have someval for field1
     import std.algorithm;
     return arr.filter!(v => v.field1 == someval);
 }
 ```
 
 While this works, and is nice, it's using a lambda with local references 
 to filter data. This means a GC closure allocation is involved.
 
 *snip*


It does come up every so often. You can also follow the links here.
https://forum.dlang.org/post/qnigarkuxxnqwdernhzv forum.dlang.org


Maybe the zip+repeat trick should be streamlined a bit.
Jun 21 2021
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/22/21 2:20 AM, rm wrote:

 It does come up every so often. You can also follow the links here.
 https://forum.dlang.org/post/qnigarkuxxnqwdernhzv forum.dlang.org


Thanks for the link, I didn't remember this (it just happened a few 
months ago too!)


 
 
 Maybe the zip+repeat trick should be streamlined a bit.


Yeah, I'm suggesting to avoid having to specify explicitly on the call 
side how to pass the data. The compiler could figure it out for me, and 
I get ` nogc` `filter` for free.

-Steve
Jun 22 2021
prev sibling parent reply 12345swordy <alexanderheistermann gmail.com> writes:
On Monday, 21 June 2021 at 20:01:27 UTC, Steven Schveighoffer 
wrote:

 I have some code in my codebase that does stuff like this:

 ```d
 struct S
 {
    int id;
    int field1;
 }

 auto foo(S[] arr, int someval) //  nogc not allowed :(
 {
    // remove all the elements of arr that have someval for 
 field1
    import std.algorithm;
    return arr.filter!(v => v.field1 == someval);
 }
 ```

 While this works, and is nice, it's using a lambda with local 
 references to filter data. This means a GC closure allocation 
 is involved.

 However, the value that is referenced (someval) is the only 
 thing needed, and it seems a huge waste to allocate a stack 
 frame *just* for that.

 Let's look at another way to do this. `filter` does not have an 
 overload which accepts a *value* to compare to, but `find` 
 does. So let's build a new `filter` that uses it:

 ```d
 auto nogcfilter(alias pred, T, V)(T[] rng, V val)
 {
     import std.range;
     import std.algorithm : find;
     static struct Filter {
         T[] src;
         V val;
         auto front() { return src.front; }
         void popFront() {src.popFront; src = 
 src.find!pred(val); }
         auto empty() { return src.empty; }
     }
     return Filter(rng, val);
 }

 auto foo(S[] arr, int someval)  nogc // :)
 {
    // note: the explicit lambda types are needed for some reason
    return arr.nogcfilter!((S v, int a) => v.field1 == 
 a)(someval);
 }
 ```

 Now we get filter capability, but without the GC.

 This works great because the context items used do NOT require 
 any mutability. It also works great because the filter function 
 is building a custom type ANYWAY.

 Now, we could add this kind of functionality to `filter`, but 
 being the lazy programmer that I am, what if the compiler could 
 do this for me? In most cases, I don't want to sleuth out what 
 context is needed (which might change as the code evolves). To 
 force the user to both invent the context type (here, it's just 
 an `int`, but it may require other values) and explicitly pass 
 it is a bit verbose (I already don't like having to pass the 
 `int`, and declaring the parameter).

 What if, a function that accepts a lambda, could also accept a 
 *context* which the compiler made up and passed in? Here's how 
 it would possibly look (with a new magic type `__context`):

 ```d
 auto nogcfilter(alias pred, T, __context...)(T[] rng, __context 
 ctxt)
 {
     import std.range;
     import std.algorithm : find;
     static struct Filter {
         T[] src;
         __context val;
         auto front() { return src.front; }
         void popFront() {src.popFront; src = 
 src.find!pred(val); }
         auto empty() { return src.empty; }
     }
     return Filter(rng, ctxt);
 }

 auto foo(S[] arr, int someval)  nogc
 {
    return arr.nogcfilter!((v) => v.field1 == someval);
 }
 ```

 The compiler would see there's a lambda involved, automatically 
 pass the context parameter `someval` into the function itself, 
 and everything magically works. It would only be used when a 
 closure would otherwise be allocated, and the function being 
 called declares the context parameter.

 Disclaimer: I am not a language developer.

 Does this make sense? Is there anything feasible that might be 
 similar? Would it be more feasible with different syntax?

 I realize there are implications if the context parameter is 
 mutable, so perhaps we would have to require only const 
 contexts (though the compiler might be able to figure out that 
 something isn't modified anywhere, and allow it to go in).

 -Steve


Why can't it be implemented by using templates?

- Alex
Jun 22 2021
parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 6/22/21 8:38 PM, 12345swordy wrote:

 Why can't it be implemented by using templates?


Oh it can, I did in the original message! It just doesn't look as nice.

-Steve
Jun 23 2021