Repository navigation
Mark all objects reachable from roots as live before doing main cyclic GC pass #126491
Description
Objects can only be cyclic garbage if they are not reachable.
So, if we can cheaply identify the majority of reachable objects before performing the (relatively slow) cycle detecting pass, we can save a lot of time.
Performing a transitive closure of all objects reachable from global roots (the sys and builtins modules as well as builtin class's dicts and sublasses) plus a transitive closure of all objects reachable from the stacks can eliminate >90% of all objects relatively cheaply.
Initial experiments show a ~3% speedup, with an almost 50% speedup of the most gc-heavy benchmark.
This idea has been proposed a few times.
@nascheme has definitely suggested it before. Perhaps he can add links to any prior discussion and/or experiments?
What makes this more feasible now is that the GC can see the evaluation stack of frames, thanks to #124392, so we would now expect that the vast majority of reachable objects can be cheaply marked, thus improving the efficiency of cycle detection considerably.
Linked PRs
- GH-126491: GC: Mark objects reachable from roots before doing cycle collection #126502
- Revert "GH-126491: GC: Mark objects reachable from roots before doing cycle collection (GH-126502)" #126983
- GH-126491: Increase the threshold for the GC fast cycle test. #126984
- GH-126491: GC: Mark objects reachable from roots before doing cycle collection #127110
- GH-126491: Lower heap size limit with faster marking #127519
- gh-126491: Revert "GH-126491: Lower heap size limit with faster marking (GH-127519)" #127770
Activity
kumaraditya303 commentedon Nov 6, 2024
Is that benchmark public, link isn't working for me?
markshannon commentedon Nov 6, 2024
Fixed the link
nascheme commentedon Nov 6, 2024
FYI, I made an incremental "mark alive" version of my idea. My PR is based off of 3.13 but it could be done on top of the "incremental gc" that's in the "main" branch as well. This approach avoids a problem with the current incremental GC: if you happen to pull in an object near the root of the object graph, the GC pause could be long because all reachable objects are pull in to the cyclic GC pass.
#126511
GH-126491: GC: Mark objects reachable from roots before doing cycle c…
Revert "pythonGH-126491: GC: Mark objects reachable from roots before…
Revert "GH-126491: GC: Mark objects reachable from roots before doing…
GH-126491: GC: Mark objects reachable from roots before doing cycle c…
eendebakpt commentedon Dec 3, 2024
@markshannon Out of curiosity:
Revert "pythonGH-126491: GC: Mark objects reachable from roots before…
nascheme commentedon Dec 3, 2024
Python doesn't have a precise set of roots. For example, an extension module can create objects but not have them connected to any roots that the CPython runtime knows about.
Reapply "pythonGH-126491: GC: Mark objects reachable from roots befor…
Revert "pythonGH-126491: GC: Mark objects reachable from roots before…
GH-126491: Lower heap size limit with faster marking (GH-127519)
Revert "pythonGH-126491: Lower heap size limit with faster marking (p…
gh-126491: Revert "GH-126491: Lower heap size limit with faster marki…
encukou commentedon Dec 10, 2024
I've reverted the last change, which introduced a refleak.
pythonGH-126491: GC: Mark objects reachable from roots before doing c…
pythonGH-126491: Lower heap size limit with faster marking (pythonGH-…
pythongh-126491: Revert "pythonGH-126491: Lower heap size limit with …
pythonGH-126491: GC: Mark objects reachable from roots before doing c…
Revert "pythonGH-126491: GC: Mark objects reachable from roots before…
pythonGH-126491: GC: Mark objects reachable from roots before doing c…
nascheme commentedon Feb 26, 2025
Could this be closed now? Or, are we waiting for a revised version of gh-127519 to be merged? @markshannon