Jump to page: 1 2 3
Thread overview
Idea: Ownership & lifetime escape analysis by variables in reference to
May 29, 2022
Rikki Cattermole
May 29, 2022
deadalnix
May 29, 2022
rikki cattermole
May 29, 2022
drug
May 29, 2022
rikki cattermole
May 29, 2022
rikki cattermole
May 29, 2022
rikki cattermole
May 29, 2022
rikki cattermole
May 29, 2022
rikki cattermole
May 29, 2022
rikki cattermole
May 29, 2022
rikki cattermole
May 29, 2022
rikki cattermole
May 29, 2022
Walter Bright
May 29, 2022
rikki cattermole
May 30, 2022
Walter Bright
May 30, 2022
rikki cattermole
May 29, 2022

Walter suggested that I create a thread for an idea I've had for memory ownership & lifetimes.

The basic explanation is that every variable (including temporaries and returns) are always in reference to other variables. So that the order of destruction is correct and nothing escapes its owner (they can be bundled unless scope is involved).

These examples come from a talk with Timon a couple of days ago on Discord. His existing dislike for this idea is that it conflates different levels of indirection.

My worked example:

int[] array = [1, 2, 3]; // ownership: []
// arg ownership: [] (not ref/out)
// return ownership: [first argument] -> [array]
int* got = func(array); // ownership: [array]

int* func(int[] source) {
  int[] slice = source[1 .. 2]; // ownership: [source]
  int* ptr = &slice[0]; // ownership: [slice, source] -> [source]
  return ptr; // ownership: [ptr] -> [source]
}

A question Timon came up with that I answered:

int[][] func(int[] a, int[] b){
    return [a,b];
}

(for return value): // ownership: [first argument, second argument]

This ticks a lot of the boxes I'm using as preferable acceptance criteria:

  1. Inferred for anything non-virtual
  2. Nothing outlives its owner
  3. Fairly straight forward to understand
May 29, 2022

On Sunday, 29 May 2022 at 00:22:03 UTC, Rikki Cattermole wrote:

>

Walter suggested that I create a thread for an idea I've had for memory ownership & lifetimes.

The basic explanation is that every variable (including temporaries and returns) are always in reference to other variables. So that the order of destruction is correct and nothing escapes its owner (they can be bundled unless scope is involved).

These examples come from a talk with Timon a couple of days ago on Discord. His existing dislike for this idea is that it conflates different levels of indirection.

My worked example:

int[] array = [1, 2, 3]; // ownership: []
// arg ownership: [] (not ref/out)
// return ownership: [first argument] -> [array]
int* got = func(array); // ownership: [array]

int* func(int[] source) {
  int[] slice = source[1 .. 2]; // ownership: [source]
  int* ptr = &slice[0]; // ownership: [slice, source] -> [source]
  return ptr; // ownership: [ptr] -> [source]
}

A question Timon came up with that I answered:

int[][] func(int[] a, int[] b){
    return [a,b];
}

(for return value): // ownership: [first argument, second argument]

This ticks a lot of the boxes I'm using as preferable acceptance criteria:

  1. Inferred for anything non-virtual
  2. Nothing outlives its owner
  3. Fairly straight forward to understand

Yes, this is a good start. You have one major missing point: you need something to transfers ownership or you end up very limited.

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/msr-tr-2012-79.pdf

All we need is one god damn type qualifier and we make DIP1000, @live, RC object, nogc exception and couple of other long standing problem a thing of the past.

May 29, 2022
On 29/05/2022 12:26 PM, deadalnix wrote:
> Yes, this is a good start. You have one major missing point: you need something to transfers ownership or you end up very limited.

Can you please write up an example similar to what I wrote, so that we can see what would be added (my mind just go blank on that paper)?
May 29, 2022
On 29.05.2022 03:26, deadalnix wrote:
> Yes, this is a good start. You have one major missing point: you need something to transfers ownership or you end up very limited.
> 
> https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/msr-tr-2012-79.pdf 
> 
> 
> All we need is one god damn type qualifier and we make DIP1000, @live, RC object, nogc exception and couple of other long standing problem a thing of the past.

You mean `isolated`? Funny but we almost have this type qualifier - in fact it is opposite/antonym to `shared`, I guess.
May 29, 2022

On Sunday, 29 May 2022 at 00:22:03 UTC, Rikki Cattermole wrote:

>

Walter suggested that I create a thread for an idea I've had for memory ownership & lifetimes.

The basic explanation is that every variable (including temporaries and returns) are always in reference to other variables. So that the order of destruction is correct and nothing escapes its owner (they can be bundled unless scope is involved).

Maybe look at the basic ideas for static analysis? Then you will know the limitations.

How do you deal with conditionals?
How do you deal with mutable arrays of pointers?

Simple stuff like a queue of size two? How do you know what it contains?

With lifetimes you can be pessimitic: max lifetime of anything that could in theory be put into it unless I am able to prove otherwise. Then you dont have to try to prove something unless it is needed.

Better to just add ARC and do all these things as optimizations.

May 29, 2022

On Sunday, 29 May 2022 at 07:42:29 UTC, Ola Fosheim Grøstad wrote:

>

Maybe look at the basic ideas for static analysis? Then you will know the limitations.

Think of it like this:

If you try to be precise then parts of it has to happen at runtime.

If you want to do it at compile time then you have to overapproximate (be more pessimistic than the possible runtime situations).

May 29, 2022
On 29/05/2022 7:42 PM, Ola Fosheim Grøstad wrote:
> Maybe look at the basic ideas for static analysis? Then you will know the limitations.
> 
> How do you deal with conditionals?

```d
Thing func(Thing a, Thing b, bool pickB) {
	return pickB ? a : b; // ownership: [a, b]
}
```

> How do you deal with mutable arrays of pointers?

```d

void func(Thing a, Thing b) {
	int[] arr; // ownership: []
	
	arr ~= a; // arr ownership: [a]
	arr ~= b; // arr ownership: [a, b]

	arr = arr[0 .. 1]; // arr ownership: [a, b]
	arr ~= b; // arr ownership: [a, b]
}
```

> Simple stuff like a queue of size two? How do you know what it contains?

See above

> With lifetimes you can be pessimitic: max lifetime of anything that could in theory be put into it unless I am able to prove otherwise. Then you dont have to try to prove something unless it is needed.
> 
> Better to just add ARC and do all these things as optimizations.

I too would like to have proper reference counting on structs and classes with optimizations, but the compiler has to know what object to do the reference counting on! Right now things can escape reference counting.
May 29, 2022
On 29/05/2022 7:57 PM, Ola Fosheim Grøstad wrote:
> On Sunday, 29 May 2022 at 07:42:29 UTC, Ola Fosheim Grøstad wrote:
>> Maybe look at the basic ideas for static analysis? Then you will know the limitations.
> 
> Think of it like this:
> 
> If you try to be precise then parts of it has to happen at runtime.
> 
> If you want to do it at compile time then you have to overapproximate (be more pessimistic than the possible runtime situations).

My goals for this was to be a very cheap set of checks at compile time, that can catch most naive wrong life time issues, while being easily explained.

I'm not concerned too much about preciseness as long as the false positives are low (or at least lower than DIP1000).
May 29, 2022

On Sunday, 29 May 2022 at 08:03:57 UTC, rikki cattermole wrote:

>

On 29/05/2022 7:42 PM, Ola Fosheim Grøstad wrote:

>

Simple stuff like a queue of size two? How do you know what it contains?

See above

You will end up being too pessimistic. For instance: if the queue is empty you will assume it is tainted by eveything that went through it...

To get to a good place you have to do a good overapproximation.

>

I too would like to have proper reference counting on structs and classes with optimizations, but the compiler has to know what object to do the reference counting on! Right now things can escape reference counting.

Impose more limits on @safe. Then give @trusted and @system wrappers and other constructs that allows them to give @safe code what it needs.

A fat pointer can track ownership when you address fields. Then get rid of fat pointers by optimization.

May 29, 2022
On 29/05/2022 7:42 PM, Ola Fosheim Grøstad wrote:
> Simple stuff like a queue of size two? How do you know what it contains?

I've been thinking back on my past thought experiments, how I use to turn this on was with scope as a type qualifier.

For non-owning data structures like queues, you would never intentionally mark that as scope since its entries will always have separate lifetimes from that of the data structure itself.

So even if implemented, this may not be a general solution that we are looking for.
« First   ‹ Prev
1 2 3