Comment by generichuman | Hacker News Reader

Comment by generichuman | Hacker News Reader

Parent Full thread

> which is not all that common/general.

Your objects in trees and arrays don't have the same lifecycle?

Quoting GP:

> ... reference counting (RC) have stampeding characteristics similar to GC pauses when releasing large hierarchies e.g. persistent data structures, or large trees of widgets: all the tree is freed synchronously and recursively, if it's large it can be very sensible.

This is mostly where RC & MMM fails. This is also where you are supposed to use arena allocators.

If you have a tree you're constantly adding to / deleting from, you can use a Pool backed by an Arena. At that point you don't use pointers, only indices into the pool. When you want to remove something from the tree, you mark the objects in the pool "deleted" until you want something added back again.

> Your objects in trees and arrays don't have the same lifecycle?

No, there is a nested set of lifetimes.

Take a hierarchy of widgets for instance, if you change a sub-view you're going to reclaim the widgets composing that sub-view, replacing them with widgets of an other sub-view.

Then there's persistent datastructures, where lifetimes are reversed (higher nodes are younger), you update a node, you're going to invalidate all the nodes on the path to that, but the nodes which are not on that path are still alive.

> If you have a tree you're constantly adding to / deleting from, you can use a Pool backed by an Arena. At that point you don't use pointers, only indices into the pool. When you want to remove something from the tree, you mark the objects in the pool "deleted" until you want something added back again.

So you're implementing an ad-hoc GC by hand (and so does everyone else) and making your traversal more complicated.

If there's a GC pointer provided (by the language or a library), in the vast majority of cases it will work well enough and you won't need to waste time on that, you can solve actual issues instead.

Sure, it’s a great optimization opportunity — though I would argue that replacing pointers with indexes can be a bad thing (often seen in Rust when people don’t want to argue with the compiler), since then not even valgrind and the like can catch your “use-after-free” errors.

Reply on news.ycombinator.com