Would it be a valid optimization to have D remove the requirement for allocation when it can determine that the entire data structure of the item in question is an rvalue, and would fit into the data pointer part of the delegate?

Here's what I'm looking at:

auto foo(int x)
{
   return { return x + 10; };
}

In this case, D allocates a pointer on the heap to hold "x", and then return a delegate which uses the pointer to read x, and then return that plus 10.

However, we could store x itself in the storage of the pointer of the delegate. This removes an indirection, and also saves the heap allocation.

Think of it like "automatic functors".

Does it make sense? Would it be feasible for the language to do this? The type system already casts the delegate pointer to a void *, so it can't make any assumptions, but this is a slight break of the type system.

The two requirements I can think of are:
1. The data in question must fit into a word
2. It must be guaranteed that the data is not going to be mutated (either via the function or any other function). Maybe it's best to require the state to be const/immutable.

I've had several cases where I was tempted to not use delegates because of the allocation cost, and simply return a specialized struct, but it's so annoying to do this compared to making a delegate. Plus something like this would be seamless with normal delegates as well (in case you do need a real delegate).

-Steve

On Monday, 30 July 2018 at 21:02:56 UTC, Steven Schveighoffer wrote:
> Would it be a valid optimization to have D remove the requirement for allocation when it can determine that the entire data structure of the item in question is an rvalue, and would fit into the data pointer part of the delegate?

Don't do that. It's valid in simple cases.
As soon as you want to chain delegate pointers it falls apart.
Also the delegate might require heap allocation to be memory correct.

On 8/2/18 8:42 AM, Stefan Koch wrote:
> On Monday, 30 July 2018 at 21:02:56 UTC, Steven Schveighoffer wrote:
>> Would it be a valid optimization to have D remove the requirement for allocation when it can determine that the entire data structure of the item in question is an rvalue, and would fit into the data pointer part of the delegate?
> 
> Don't do that. It's valid in simple cases.

Those are the cases I'm referring to.

> As soon as you want to chain delegate pointers it falls apart.

And so, don't do the skinny delegate optimization in that case?

> Also the delegate might require heap allocation to be memory correct.

Does the "might" depend on the caller or on the delegate implementation itself? The former would squash this idea.

-Steve

On Thursday, 2 August 2018 at 12:57:02 UTC, Steven Schveighoffer wrote:
> On 8/2/18 8:42 AM, Stefan Koch wrote:
>> On Monday, 30 July 2018 at 21:02:56 UTC, Steven Schveighoffer wrote:
>>> Would it be a valid optimization to have D remove the requirement for allocation when it can determine that the entire data structure of the item in question is an rvalue, and would fit into the data pointer part of the delegate?
>> 
>> Don't do that. It's valid in simple cases.
>
> Those are the cases I'm referring to.
>
I meant it seems valid in simple cases, and I doubt you can distinguish between cases that work and cases which don't work with 100% accuracy.
>> As soon as you want to chain delegate pointers it falls apart.
>
> And so, don't do the skinny delegate optimization in that case?
>
Again the question is whether you can tell the cases apart with local information.
>> Also the delegate might require heap allocation to be memory correct.
>
> Does the "might" depend on the caller or on the delegate implementation itself? The former would squash this idea.
>
I am not sure about that, it's just a gut feeling that skinny delegates will be breaking some invariant, I may be wrong.

Coming up with specific rules and throwing them at the wall until they don't break anymore, is fine for applications used in limited controlled circumstances, I would not want to do it with a compiler which is used by an unknown number of users.

On 8/2/18 9:21 AM, Stefan Koch wrote:
> On Thursday, 2 August 2018 at 12:57:02 UTC, Steven Schveighoffer wrote:
>> On 8/2/18 8:42 AM, Stefan Koch wrote:
>>> On Monday, 30 July 2018 at 21:02:56 UTC, Steven Schveighoffer wrote:
>>>> Would it be a valid optimization to have D remove the requirement for allocation when it can determine that the entire data structure of the item in question is an rvalue, and would fit into the data pointer part of the delegate?
>>>
>>> Don't do that. It's valid in simple cases.
>>
>> Those are the cases I'm referring to.
>>
> I meant it seems valid in simple cases, and I doubt you can distinguish between cases that work and cases which don't work with 100% accuracy.

When the data needed in the delegate is all effectively immutable (or maybe *actually* immutable), I can't see how using a pointer to it is different than using a copy of it.

>>> As soon as you want to chain delegate pointers it falls apart.
>>
>> And so, don't do the skinny delegate optimization in that case?
>>
> Again the question is whether you can tell the cases apart with local information.

This idea requires cooperation from the compiler, all the way down to code generation -- it's not really a lowering but a change in how the data is fetched from the context.

At a minimum, I would say anything that only depends on immutables can be a valid use case.

In order to prove effective immutability (anything that could possibly change elsewhere can't qualify for this), you would need a lot of local information. So maybe this only works if the type is actually immutable.

>>> Also the delegate might require heap allocation to be memory correct.
>>
>> Does the "might" depend on the caller or on the delegate implementation itself? The former would squash this idea.
>>
> I am not sure about that, it's just a gut feeling that skinny delegates will be breaking some invariant, I may be wrong.
> 
> Coming up with specific rules and throwing them at the wall until they don't break anymore, is fine for applications used in limited controlled circumstances, I would not want to do it with a compiler which is used by an unknown number of users.

I wasn't planning on that method of proof. What I wanted to do was start with the tightest possible, but easily provable constraints -- all data must be immutable -- and then relax as it makes sense.

What I don't know is the implications on the optimizer or semantic analysis -- does the context pointer being really a pointer have any affect on those pieces?

I also don't know what you meant by "memory correct".

-Steve

On Monday, 30 July 2018 at 21:02:56 UTC, Steven Schveighoffer wrote:

> In this case, D allocates a pointer on the heap to hold "x", and then return a delegate which uses the pointer to read x, and then return that plus 10.

Yeah, that seems like such a disproportionately heavy cost.

> Does it make sense?

I haven't though through the details, but if it can be done, I think it would be nice.  I like when programming tools are more intelligent about things like this because after you become familiar with it and build confidence in it, you can just code your ass off and know that the compiler is doing right on your behalf.

Mike

On Monday, 30 July 2018 at 21:02:56 UTC, Steven Schveighoffer wrote:

> Does it make sense?

It is also nice for domains like embedded systems.  It is common for embedded systems to only dynamically allocate during system initialization (depending on the application of course).  Avoiding the allocation would make the pattern you describe available to systems that have this restriction, and it's always nice to remove such limitations.

Mike

On 7/30/18 5:02 PM, Steven Schveighoffer wrote:
> Does it make sense? Would it be feasible for the language to do this? The type system already casts the delegate pointer to a void *, so it can't make any assumptions, but this is a slight break of the type system.

One possibility to avoid typesystem breakage is to internally treat a delegate structure like this:

struct Delegate(RT, PARAMS...)
{
   RT function(PARAMS params) funcptr;
   union
   {
      void *ptr;
      immutable ubyte[(void*).sizeof] context;
   }
}

Whereby the compiler is informed that the context could just be a bunch of bytes.

-Steve

I suppose it's mostly for mutability, so if it's const, it can be optimized based on type information only:

auto foo(in int x)
{
   return { return x + 10; };
}

On 8/2/18 11:00 AM, Kagamin wrote:
> I suppose it's mostly for mutability, so if it's const, it can be optimized based on type information only:
> 
> auto foo(in int x)
> {
>     return { return x + 10; };
> }

I'm not sure what you mean here.

-Steve