www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - unique ownership + unlimited safe generational references

reply Nick Treleaven <nick geany.org> writes:
Hi,
This article is from 2021:
https://verdagon.dev/blog/generational-references

I've not seen Generational References mentioned on this forum but 
Reference Counting comes up a lot. I thought GR would interest 
people here. The article shows a benchmark based on naive RC vs 
naive GR, but the explanations why it was faster are interesting 
and promising. (I found this yesterday, I don't know yet if there 
is more info elsewhere).

The author explains why they believe aliasing of references was 
more common than dereferencing:
https://www.reddit.com/r/ProgrammingLanguages/comments/kpq805/vales_generational_references/gi0zmnn/

RC & GR aren't functionally equivalent, the memory is freed when 
the single owner goes out of scope. Any remaining references 
would then either halt or throw when dereferenced. So that's a 
pitfall you don't have with RC, but at least it's deterministic. 
And no lifetime annotation or restriction to only unique 
mutability a la Rust. So the programmer has more flexibility.

It also reminded me of a Microsoft idea to make calling `free` 
memory-safe, but I never found any detail on how that worked or 
what the overhead was.
Mar 29 2022
next sibling parent reply IGotD- <nise nise.com> writes:
On Tuesday, 29 March 2022 at 17:13:57 UTC, Nick Treleaven wrote:
 Hi,
 This article is from 2021:
 https://verdagon.dev/blog/generational-references

 I've not seen Generational References mentioned on this forum 
 but Reference Counting comes up a lot. I thought GR would 
 interest people here. The article shows a benchmark based on 
 naive RC vs naive GR, but the explanations why it was faster 
 are interesting and promising. (I found this yesterday, I don't 
 know yet if there is more info elsewhere).

 The author explains why they believe aliasing of references was 
 more common than dereferencing:
 https://www.reddit.com/r/ProgrammingLanguages/comments/kpq805/vales_generational_references/gi0zmnn/

 RC & GR aren't functionally equivalent, the memory is freed 
 when the single owner goes out of scope. Any remaining 
 references would then either halt or throw when dereferenced. 
 So that's a pitfall you don't have with RC, but at least it's 
 deterministic. And no lifetime annotation or restriction to 
 only unique mutability a la Rust. So the programmer has more 
 flexibility.

 It also reminded me of a Microsoft idea to make calling `free` 
 memory-safe, but I never found any detail on how that worked or 
 what the overhead was.
In general I think that unique ownership of pointers is a plague in computer science and it needs to die. The reason is that it is fundamentally data structure unfriendly. When it comes to the memory management described here (Generational References), it is like a runtime version of the borrow checker in Rust (not completely, but close). It solves use after free but what does it solve beyond that? Also, does need to do a check for every deference?
Mar 29 2022
parent Nick Treleaven <nick geany.org> writes:
On Tuesday, 29 March 2022 at 17:40:27 UTC, IGotD- wrote:
 In general I think that unique ownership of pointers is a 
 plague in computer science and it needs to die. The reason is 
 that it is fundamentally data structure unfriendly.
Vale has unique ownership of objects, the references/pointers aren't owned. But I think you could have shared ownership of objects and still benefit from generational references. Maybe GR are like weak references, except (hopefully) more efficient. (Based on a cursory google of weak references in C++ and Swift, it seems they require an extra allocation per-object for the counter).
 When it comes to the memory management described here 
 (Generational References), it is like a runtime version of the 
 borrow checker in Rust (not completely, but close). It solves 
 use after free but what does it solve beyond that?
Memory-safety without GC is a big thing.
 Also, does need to do a check for every deference?
I suppose it would need to re-check if any code/function call was made in between dereferences that could have destroyed the owner.
Mar 29 2022
prev sibling parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= <ola.fosheim.grostad gmail.com> writes:
On Tuesday, 29 March 2022 at 17:13:57 UTC, Nick Treleaven wrote:
 Hi,
 This article is from 2021:
 https://verdagon.dev/blog/generational-references

 I've not seen Generational References mentioned on this forum 
 but Reference Counting comes up a lot. I thought GR would 
 interest people here. The article shows a benchmark based on 
 naive RC vs naive GR, but the explanations why it was faster 
 are interesting and promising. (I found this yesterday, I don't 
 know yet if there is more info elsewhere).
How does this work with multithreaded shared references?
Mar 30 2022
parent reply Nick Treleaven <nick geany.org> writes:
On Wednesday, 30 March 2022 at 07:02:16 UTC, Ola Fosheim Grøstad 
wrote:
 How does this work with multithreaded shared references?
Vale doesn't allow sharing mutable data across threads. But if the assumption that most programs alias data (copying a pointer) more often than they access the data is correct, it seems thread-safe generational references would still be faster (at least naive RC vs naive GR). The cost of mutual-exclusion would be paid on any dereference check but there would be no cost on aliasing. (Also multiple dereferences of the same data may only need one check in some cases).
Mar 30 2022
next sibling parent Nick Treleaven <nick geany.org> writes:
On Wednesday, 30 March 2022 at 11:23:37 UTC, Nick Treleaven wrote:
 (Also multiple dereferences of the same data may only need one 
 check in some cases).
Ignore that last sentence, I think that only applies to single-threaded code.
Mar 30 2022
prev sibling next sibling parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= <ola.fosheim.grostad gmail.com> writes:
On Wednesday, 30 March 2022 at 11:23:37 UTC, Nick Treleaven wrote:
 On Wednesday, 30 March 2022 at 07:02:16 UTC, Ola Fosheim 
 Grøstad wrote:
 How does this work with multithreaded shared references?
Vale doesn't allow sharing mutable data across threads. But if the assumption that most programs alias data (copying a pointer) more often than they access the data is correct, it seems thread-safe generational references would still be faster (at least naive RC vs naive GR). The cost of mutual-exclusion would be paid on any dereference check but there would be no cost on aliasing. (Also multiple dereferences of the same data may only need one check in some cases).
You would need a lock on the object, so it is far worse than ARC?
Mar 30 2022
parent reply Nick Treleaven <nick geany.org> writes:
On Wednesday, 30 March 2022 at 12:39:40 UTC, Ola Fosheim Grøstad 
wrote:
 You would need a lock on the object, so it is far worse than 
 ARC?
Wouldn't you need a lock on the object anyway if you're accessing its fields? If not, why can't we access the generation field of the object without a lock too?
Mar 30 2022
parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= <ola.fosheim.grostad gmail.com> writes:
On Wednesday, 30 March 2022 at 14:19:36 UTC, Nick Treleaven wrote:
 On Wednesday, 30 March 2022 at 12:39:40 UTC, Ola Fosheim 
 Grøstad wrote:
 You would need a lock on the object, so it is far worse than 
 ARC?
Wouldn't you need a lock on the object anyway if you're accessing its fields? If not, why can't we access the generation field of the object without a lock too?
No, not comparable. Preventing the object from being reused as a random type is different from controlling access sequencing.
Mar 30 2022
prev sibling parent reply Evan Ovadia <verdagon gmail.com> writes:
On Wednesday, 30 March 2022 at 11:23:37 UTC, Nick Treleaven wrote:
 On Wednesday, 30 March 2022 at 07:02:16 UTC, Ola Fosheim 
 Grøstad wrote:
 How does this work with multithreaded shared references?
Vale doesn't allow sharing mutable data across threads. But if the assumption that most programs alias data (copying a pointer) more often than they access the data is correct, it seems thread-safe generational references would still be faster (at least naive RC vs naive GR). The cost of mutual-exclusion would be paid on any dereference check but there would be no cost on aliasing. (Also multiple dereferences of the same data may only need one check in some cases).
Vale author here, someone pointed me to this thread. Your understanding is correct! I'll add some details on improvements made since that original article, which could help explain why this seemingly crazy scheme might work well: * If we want to, we can lock an object to prevent it from being freed at runtime, which is a good call in some cases and can let us skip a lot of generation checks: https://verdagon.dev/blog/hybrid-generational-memory * Our "region borrow checker" would allow us to skip most generation checks, see https://verdagon.dev/blog/zero-cost-refs-regions. It would also apply to RC (the article was written with RC in mind, in fact). * (This is just a suspicion) Adding `iso` objects, like Pony does, could make the region borrow usable for more than just mutexes and pure functions. I recently discovered a function that, between those two mechanisms, would actually have zero overhead: https://verdagon.dev/blog/vale-7drl#the-good-parts If D wants to use any of these ideas, just give me a holler! Always happy to discuss.
Apr 02 2022
parent Nick Treleaven <nick geany.org> writes:
On Sunday, 3 April 2022 at 02:45:45 UTC, Evan Ovadia wrote:
 I'll add some details on improvements made since that original 
 article, which could help explain why this seemingly crazy 
 scheme might work well:
Thanks! (I still need to read these).
  * If we want to, we can lock an object to prevent it from 
 being freed at runtime, which is a good call in some cases and 
 can let us skip a lot of generation checks:
That's an interesting idea. So for a mutable object shared across threads in D, an atomic int could be incremented before dereferencing fields. Any intervening call to free the object would be deferred by the allocator until after the dereferencing. And this should have better cache locality than atomic reference counting.
 If D wants to use any of these ideas, just give me a holler! 
 Always happy to discuss.
I'd prefer D supported generational references instead of live which seems to be like rust's unique mutability. Failing that perhaps generational references can be supported in a D library, but they'd only work with compatible objects.
Apr 06 2022