Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Candidate-root based cycle GC #693

Open
markshannon opened this issue Aug 5, 2024 · 0 comments
Open

Candidate-root based cycle GC #693

markshannon opened this issue Aug 5, 2024 · 0 comments

Comments

@markshannon
Copy link
Member

markshannon commented Aug 5, 2024

For a unreachable cycle to be be formed the refcount of the last reachable object in the cycle must drop to a non-zero value.

All objects whose reference counts drops to a non-zero value are thus candidate roots of cycles.
We can exploit this, when performing GC by only creating increments from candidate roots.

Since 5 in 6 decrefs are to non-zero, almost all objects would end up as candidate roots anyway, and it would add significant cost to DECREF operations.

However, with deferred reference counting the numbers change a lot.
With deferred RC, only about a third of DECREFs will leave the RC > 0.
The additional cost of marking objects as candidate roots would be much lower, and the effectiveness of cycle GC much increased.

The algorithm

def decref(obj):
    if obj.refcnt == 1:
        free(obj)
    else:
        if is_gc(obj):
            if obj in candidate_roots:
                candidate_roots.move_to_end(obj)
            else:
                candidate_roots.append(obj)
        obj.refcnt -= 1

GC:

while work_to_do > 0:
     obj = candidate_roots.pop(0)
     graph = form_transitive_closure(obj)
     work_to_do -= len(graph)
     collect_if_unreachable(graph)
@markshannon markshannon changed the title Candidate root base cycle GC Candidate-root based cycle GC Oct 1, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant