René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Mark all objects reachable from roots as live before doing main cyclic GC pass","articleBody":"Objects can only be cyclic garbage if they are not reachable.\r\nSo, 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.\r\n\r\nPerforming 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 \u003e90% of all objects relatively cheaply.\r\n\r\nInitial experiments show a [~3% speedup, with an almost 50% speedup of the most gc-heavy benchmark](https://raw.githubusercontent.com/faster-cpython/benchmarking-public/refs/heads/main/results/bm-20241104-3.14.0a1%2B-5e813c5/bm-20241104-linux-x86_64-faster%252dcpython-mark_first_gc-3.14.0a1%2B-5e813c5-vs-base.svg).\r\n\r\nThis idea has been proposed a few times. \r\n@nascheme has definitely suggested it before. Perhaps he can add links to any prior discussion and/or experiments?\r\n\r\nWhat 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.\n\n\u003c!-- gh-linked-prs --\u003e\n### Linked PRs\n* gh-126502\n* gh-126983\n* gh-126984\n* gh-127110\n* gh-127519\n* gh-127770\n\u003c!-- /gh-linked-prs --\u003e\n","author":{"url":"https://github.com/markshannon","@type":"Person","name":"markshannon"},"datePublished":"2024-11-06T12:12:05.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":7},"url":"https://github.com/126491/cpython/issues/126491"}