Reference counting with less than half the overhead

[dumblob]

Just saw an interesting take on reference counting with less than half the overhead of "traditional" optimized RC.

https://verdagon.dev/blog/generational-references https://verdagon.dev/blog/hybrid-generational-memory

Might be interesting to explore in the context of Lobster.

[aardappel]

Hah, @Verdagon who wrote those is a friend, and I am familiar with his work.. but Lobster already optimizes reference counting by quite a bit more than half in a very different way, see https://aardappel.github.io/lobster/memory_management.html

[Verdagon]

Hey hows it going @aardappel! And thanks @dumblob, it's always good to see more people interested in new memory management blends!

I'm not sure generational memory would particularly help Lobster, unless it wanted to add weak references (but even then, having both an RC and a generation in every object might be a prohibitive space cost). Lobster is at a really nice spot on the simplicity-and-performance curve, so adding something else (single ownership) to it might detract from some of Lobster's simplicity benefits.

There's a different feature Lobster might benefit from, the region borrow checker which also gets rid of RC costs. It's nice because it's "opt-in complexity"; one can write an entire program without it. I can't gauge Lobster's complexity budget, maybe it would fit in!

[dumblob]

Hah, @Verdagon who wrote those is a friend, and I am familiar with his work...

That's awesome! The world is so small...

but Lobster already optimizes reference counting by quite a bit more than half in a very different way, see https://aardappel.github.io/lobster/memory_management.html

Yeah I know that. My initial idea was to further optimize those 5% remaining RC which are not being discussed much in memory docs of Lobster :wink:.

There's a different feature Lobster might benefit from, the region borrow checker which also gets rid of RC costs. It's nice because it's "opt-in complexity"; one can write an entire program without it. I can't gauge Lobster's complexity budget, maybe it would fit in!

That's interesting - I somehow lived in a world where this type of optimization is ubiquitous common thing. But as I see it's not. Then yes, that definitely makes sense to add to RC runtimes if the language provides enough semantics for that. Lobster seems like a good candidate.

[aardappel]

Certainly, optimizing that remaining 5% of runtime refcounts is not the current "low hanging fruit" in making Lobster faster, it would be quite a bit of work to support for diminishing return gains.. and there's plenty more basic work to be done before that.

But, noted for a future where refc once again becomes a bottleneck :)

[theduke]

Drive by comment because I stumbled on Vale and Lobster recently:

@Verdagon

I have a question about generational indexes:

It seems like your implementation with a custom allocator that keeps a free list has a consequence: the allocated memory can never be released back to the OS, because there might still be references alive that point to the allocation. So while the allocator can re-use memory locally, memory usage can only grow, never shrink. I guess this could be mitigated with regions, because when a region is known to be dead it's memory can be released. So there could be separate freelists per region.

[Verdagon]

Good question. Until recently, the answer was basically this, we'd use some virtual memory tricks to merge pages and release them to the OS. Since then, we've actually just decided to let the generation number overflow, and also just release the memory back to the OS. If they use-after free, we'll get a seg fault, which we'll catch, and then blast away the containing region. It does mean we have to rework our weak references, but we've got some promising methods for that. Happy to give more details on my discord or at https://github.com/ValeLang/Vale/issues.

BTW, Wouter, I gave you some shout-outs on https://news.ycombinator.com/item?id=31139610 =)

[aardappel]

BTW, Wouter, I gave you some shout-outs on https://news.ycombinator.com/item?id=31139610 =)

Ooh thanks :)