Had similar epiphanies some many years ago (ugh, I'm old) when I was playing around writing a garbage collected persistent (in the 'stored on [spinny spinny] disk' sense not the FP sense of the word) programming language / runtime. This was back when it was roughly infeasible to be holding large "worlds" of objects purely in-memory on machines of the style of the time, so intelligently paging objects in and out was imperative. (Aside, I think with the recent doubling... tripling of RAM prices this area of thinking is now again more imperative)...
In any case, if one is doing GC in such a language, a full tracing collector (whether copying or mark & sweep) is madness, as to find live references means walking nearly the entire heap including the portions living in secondary storage, and now you're in a world of pain.
In this case, an intelligent cycle collecting garbage collector in the Bacon style was the answer. You keep in in-memory table of reference counts, and you only trace when you hit cycles. [and hopefully design your language semantics to discourage cycles]
Is it possible that by knowing less about garbage collection in Java this person might have arrived at the same solution earlier? After all his initial construction of a tracing garbage collector was wasted effort.
Reference counting does not trace dead objects. Most of its activity is concerned with maintaining reference counts on live objects.
When a reference count hits zero, that's when refcounting begins to be concerned with a dead object; and that part of its operation corresponds to the sweep activity in garbage collection, not to the tracing of live objects.
It is not a dual to garbage collection concerned with its negative spaces; it's simply a less general (we could legitimately say lesser) garbage collection that doesn't deal with cycles on its own.
Also, the closest thing to a graph search in reference counting, as most of us understand it, occurs at a totally different level in the stack.
In a GC: the graph search is hidden from view and implemented in any number of clever ways by the language runtime. Or, if you’re implementing the GC yourself, it sits out of the way of normal operations on your “heap”.
In ref counting: down ref to zero triggers a destructor. That destructor can do anything. It so happens that if the type has reference counted references, then the destructor will, either automatically or manually, invoke downref operations. All of this is part of the language’s normal execution semantics.
To say that these things are alike is a stretch. You could use similar logic to say that anyone doing a graph search is collecting garbage
You seem to be referring to a reference counting scheme that is retrofitted into a language, where the application has the responsibility of indicating where, in an application-defined type, the references are to other objects.
That can be true of garbage collection also; it can be bolted on in a way that the application is responsible for providing a handler for traversing objects during marking.
(Of course, it is vastly less likely that a marking traverser would be doing anything other than its job of recursing or otherwise indicating pointers to be traversed, whereas finalization routines will mix the downing of references with other resource clean up.)
“The overall strategy consists of determining which objects should be garbage collected by tracing which objects are reachable by a chain of references from certain root objects, and considering the rest as garbage and collecting them.”
"This was the answer I needed! Rather than visiting all the live objects, I wanted to only visit the dead ones, and reference counting would let me do that.
So I added a way of maintaining a reference count for all the nodes in the doc. When we produce a new document, we decrement the reference count of the old root node (it will always be 0 afterwards). So we recursively decrement the ref count of its children, and so on. This gives me exactly what I wanted — a way to find all the nodes that were not reused, without having to visit most of the nodes in the doc."
I think there's a bit missing from the description here in the and so on, you would only recurse on a node when it's new refcount is zero, right (and the set of zero refcount nodes produced is exactly the set of dead nodes)?
Isn't this sort of just like having a dirty flag on nodes, and then replacing dirty nodes?
I’ve often noted that most projects of a certain size tend to implement some form of garbage collection and allocation.
Perhaps general purpose systems of these sorts aren’t suitable for specialized applications… but I don’t get the “hate” (if you can call it that) which some programmers have for GC.
At some point, the trade-offs just shift. Manual memory control feels empowering until the complexity piles up, and suddenly GC looks like a smart compromise
Why does he need to manually do the tracing or reference counting of all these nodes?
Instead, he could just use the references he needs in the new tree, delete/override the old tree's root node, and expect the Javascript GC to discard all the nodes that are now referenced.
> Then, my plan was to construct a ProseMirror transaction that would turn the old tree into the new one. To do that, it’s helpful to know which nodes appeared in the old document, but not the new one.
So, it's not actually about reclaiming the memory. It's about taking some action on the nodes that will be reclaimed. It's akin to a destructor/finalizer, but I need that to happen synchronously at a time that I control. JavaScript does now support finalization (https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...) but it can't be relied on to actually happen, which makes it useless in this scenario.
18 comments
[ 5.0 ms ] story [ 43.2 ms ] threadIn any case, if one is doing GC in such a language, a full tracing collector (whether copying or mark & sweep) is madness, as to find live references means walking nearly the entire heap including the portions living in secondary storage, and now you're in a world of pain.
In this case, an intelligent cycle collecting garbage collector in the Bacon style was the answer. You keep in in-memory table of reference counts, and you only trace when you hit cycles. [and hopefully design your language semantics to discourage cycles]
When a reference count hits zero, that's when refcounting begins to be concerned with a dead object; and that part of its operation corresponds to the sweep activity in garbage collection, not to the tracing of live objects.
It is not a dual to garbage collection concerned with its negative spaces; it's simply a less general (we could legitimately say lesser) garbage collection that doesn't deal with cycles on its own.
Also, the closest thing to a graph search in reference counting, as most of us understand it, occurs at a totally different level in the stack.
In a GC: the graph search is hidden from view and implemented in any number of clever ways by the language runtime. Or, if you’re implementing the GC yourself, it sits out of the way of normal operations on your “heap”.
In ref counting: down ref to zero triggers a destructor. That destructor can do anything. It so happens that if the type has reference counted references, then the destructor will, either automatically or manually, invoke downref operations. All of this is part of the language’s normal execution semantics.
To say that these things are alike is a stretch. You could use similar logic to say that anyone doing a graph search is collecting garbage
That can be true of garbage collection also; it can be bolted on in a way that the application is responsible for providing a handler for traversing objects during marking.
(Of course, it is vastly less likely that a marking traverser would be doing anything other than its job of recursing or otherwise indicating pointers to be traversed, whereas finalization routines will mix the downing of references with other resource clean up.)
> […]
> and that part of its operation corresponds to the sweep activity in garbage collection, not to the tracing of live objects.
The sweep activity in garbage collection traces live objects. https://en.wikipedia.org/wiki/Garbage_collection_(computer_s...:
“The overall strategy consists of determining which objects should be garbage collected by tracing which objects are reachable by a chain of references from certain root objects, and considering the rest as garbage and collecting them.”
"This was the answer I needed! Rather than visiting all the live objects, I wanted to only visit the dead ones, and reference counting would let me do that.
So I added a way of maintaining a reference count for all the nodes in the doc. When we produce a new document, we decrement the reference count of the old root node (it will always be 0 afterwards). So we recursively decrement the ref count of its children, and so on. This gives me exactly what I wanted — a way to find all the nodes that were not reused, without having to visit most of the nodes in the doc."
I think there's a bit missing from the description here in the and so on, you would only recurse on a node when it's new refcount is zero, right (and the set of zero refcount nodes produced is exactly the set of dead nodes)?
Isn't this sort of just like having a dirty flag on nodes, and then replacing dirty nodes?
Perhaps general purpose systems of these sorts aren’t suitable for specialized applications… but I don’t get the “hate” (if you can call it that) which some programmers have for GC.
Instead, he could just use the references he needs in the new tree, delete/override the old tree's root node, and expect the Javascript GC to discard all the nodes that are now referenced.
> Then, my plan was to construct a ProseMirror transaction that would turn the old tree into the new one. To do that, it’s helpful to know which nodes appeared in the old document, but not the new one.
So, it's not actually about reclaiming the memory. It's about taking some action on the nodes that will be reclaimed. It's akin to a destructor/finalizer, but I need that to happen synchronously at a time that I control. JavaScript does now support finalization (https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...) but it can't be relied on to actually happen, which makes it useless in this scenario.