Thread by @Enichan

hrm i think i maybe??? found a way specific to QB# to make Bacon's simple synchronous cycles collector iterative 🤔

the problem with analyzing one potential reference cycle root at a time is that you can get quadratic complexity, which they illustrate using this figure

as i understand it the problem is if you trace these roots from left to right, assuming they're labeled A, B, C, D in order of appearance, you trace:

- A
- A + B
- A + B + C
- A + B + C + D

so you're doing 2.5 times the work to collect the garbage, and that's... bad

i'm looking at cycles collectors because it's too hard, in QB#, to actually know 100% certain what references are actually coming from the stack

but you DO know when a refcount being decreased came from the stack, aka from a root into the object graph:

in their approach you mark an object in the heap purple, a potential reference cycle root keeping garbage allocated, if its reference count decrements but doesn't hit zero

the problem is you have no further context

but we can pass along context on whether the decrement came from the freeing of a root on the stack, so for every branch in a cascade of refcount decreases, the first time you mark an object purple, instead you can mark it i dunno, red, and anything further down is marked purple

because you know the decrease came from a "true" reference root, the stack, you should be able to infer that red nodes are way more likely to be the true root of a section of garbage memory than purple nodes

i.e. red nodes are more likely to be the far right node in this figure

so presumably if you trace red nodes first you're less likely to repeatedly trace over parts of an object graph working your way down to the actual root of a section of garbage?

i dunno, though, my intuition on this one could be extremely off >_> but it feels like it makes sense to me that the closer a potential reference cycle root is to an actual root to the heap the more likely it is that its the root of a section of garbage

Bacon solves the problem of quadratic complexity by analyzing the entire graph all at once, in a stop-the-world style, because if you do all the work all at once you're not redoing any of the work

maybe by analyzing red nodes first, i can do the work in smaller, iterative steps

the problem, of course, is that i have no way to test this hypothesis since i can't find anything online about how to write a program that is designed to create garbage in order to "test" a garbage collection algorithm :D

suppose the flipside of this approach is that if the potential root is NOT a garbage root then you're tracing way more memory to find that out which would definitely be bad 🤔 and not something that would be a problem if you're tracing /all/ roots