720916 - Investigate incremental CC via candidate cycle checking

Status: RESOLVED WONTFIX

(Core :: Cycle Collector, defect)

Description

[Patrick Walton (:pcwalton)]

Per a discussion today, there's a potential way to incrementalize the cycle collector:
(1) Build up the cycle graph incrementally, yielding to the main event loop every so often.
(2) When the graph is complete, identify candidate cycles.
(3) Check to ensure that the objects in the candidate cycles have not changed. If an object has changed, don't recycle it. (Flood purple by reinserting the candidate cycles that fail the changed test into the purple buffer perhaps? Need to ensure that we maintain correctness and avoid leaks here.)
(4) Recycle candidate cycles by unlinking and freeing.

We should investigate Bacon's paper, as it has fairly clever algorithms here (the sigma-test and the delta-test).

Comment 1

[Andrew McCreight (out until 2026) [:mccr8]]

Our hope is that our simpler situation will not require quite as much cleverness as that paper.

Due to the UnmarkGray read barrier, JS wouldn't seem to pose too much additional trouble.

Comment 2

[Olli Pettay [:smaug][[e-mail]]]

The biggest problem I've seen so far in our CC handling is that we create huge graph because
we don't know that something is black. That happens usually because there is some kind
of blackC++->grayJS->C++. Black-bit-propagation helps with that.
(I haven't found any papers about GC and CC.)

After some bbp runs building (now hopefully smaller) cc graph incrementally would be great.
That would help with cases when there really is lots of garbage.
The most difficult part of this all is, I would assume, knowing whether something has changed
in the possible cycle (step 3)

Comment 3

[Olli Pettay [:smaug][[e-mail]]]

If we're talking about the original article from David F. Bacon and V.T. Rajan, its
'4 Concurrent Cycle Collection' has the problem that it relies on
"Essentially, we use the synchronous algorithm to find candidate cycles" and that is what is
usually slow. sigma and delta tests are used only after that.

Another way to do incremental CC is to do it in generations (well, that is perhaps then
called generational CC, although it would end up being incremental, kind of).
I think Andrew has a WIP patch for that, right?

Comment 4

[Olli Pettay [:smaug][[e-mail]]]

We could detect some gray (DOM) cycles during bbp runs. It is a lot faster to check in DOM whether
some DOM subtree is owned only by internal refs than use CC for that. We could also detect there
which objects are kept alive by external refs.

Comment 5

[Andrew McCreight (out until 2026) [:mccr8]]

I've started implementing a sliding views incremental CC over in bug 850065, which does not require candidate cycle checking.  As there is code written for it already, I may yoink back the alias for it. ;)

Comment 6

[Andrew McCreight (out until 2026) [:mccr8]]

I implemented another approach to incremental CC in bug 850065.