digitalmars.D - unique ownership + unlimited safe generational references
- Nick Treleaven (21/21) Mar 29 2022 Hi,
- IGotD- (9/31) Mar 29 2022 In general I think that unique ownership of pointers is a plague
- Nick Treleaven (11/19) Mar 29 2022 Vale has unique ownership of objects, the references/pointers
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (2/11) Mar 30 2022 How does this work with multithreaded shared references?
- Nick Treleaven (10/11) Mar 30 2022 Vale doesn't allow sharing mutable data across threads. But if
- Nick Treleaven (3/5) Mar 30 2022 Ignore that last sentence, I think that only applies to
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (2/13) Mar 30 2022 You would need a lock on the object, so it is far worse than ARC?
- Nick Treleaven (5/7) Mar 30 2022 Wouldn't you need a lock on the object anyway if you're accessing
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (3/11) Mar 30 2022 No, not comparable. Preventing the object from being reused as a
- Evan Ovadia (22/33) Apr 02 2022 Vale author here, someone pointed me to this thread.
- Nick Treleaven (12/20) Apr 06 2022 That's an interesting idea. So for a mutable object shared across
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
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
Nick Treleaven <nick geany.org> 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
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
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
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
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:You would need a lock on the object, so it is far worse than ARC?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
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
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:No, not comparable. Preventing the object from being reused as a random type is different from controlling access sequencing.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
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: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.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).
Apr 02 2022
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