Jump to page: 1 2
Thread overview
unique ownership + unlimited safe generational references
Mar 29
IGotD-
March 29

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.

March 29

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?

March 29

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.

March 30

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?

March 30

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).

March 30

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.

March 30

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?

March 30

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?

March 30

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.

April 03

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.

« First   ‹ Prev
1 2