GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Mark all objects reachable from roots as live before doing main cyclic GC pass · Issue #126491 · python/cpython

Mark all objects reachable from roots as live before doing main cyclic GC pass #126491

New issue
Copy link
New issue
Copy link
Open
Open
Mark all objects reachable from roots as live before doing main cyclic GC pass#126491
Copy link
Labels
interpreter-core(Objects, Python, Grammar, and Parser dirs)(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usagePerformance or resource usagetype-featureA feature request or enhancementA feature request or enhancement

Description

@markshannon
markshannon
opened on Nov 6, 2024
Issue body actions

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

  1. markshannon
    added
    performancePerformance or resource usagePerformance or resource usage
    interpreter-core(Objects, Python, Grammar, and Parser dirs)(Objects, Python, Grammar, and Parser dirs)
    3.14bugs and security fixesbugs and security fixes
    on Nov 6, 2024
  2. kumaraditya303 commented on Nov 6, 2024

    @kumaraditya303
    kumaraditya303
    on Nov 6, 2024
    Contributor
    More actions

    Is that benchmark public, link isn't working for me?

  3. markshannon commented on Nov 6, 2024

    @markshannon
    markshannon
    on Nov 6, 2024
    MemberAuthor
    More actions

    Fixed the link

  4. nascheme commented on Nov 6, 2024

    @nascheme
    nascheme
    on Nov 6, 2024
    Member
    More actions

    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

  5. markshannon
    added a commit that references this issue on Nov 18, 2024

    GH-126491: GC: Mark objects reachable from roots before doing cycle c…

    b0fcc2c
  6. hugovk
    added 2 commits that reference this issue on Nov 18, 2024

    Revert "pythonGH-126491: GC: Mark objects reachable from roots before…

    2ac5c48

    Revert "GH-126491: GC: Mark objects reachable from roots before doing…

    899fdb2
  7. markshannon
    added a commit that references this issue on Dec 2, 2024

    GH-126491: GC: Mark objects reachable from roots before doing cycle c…

    a8dd821
  8. eendebakpt commented on Dec 3, 2024

    @eendebakpt
    eendebakpt
    on Dec 3, 2024
    Contributor
    More actions

    @markshannon Out of curiosity:

    • Which kind of objects are not reachable by the transitive closure of the global roots + stack, but are reachable in some other way so they are not collected by the GC?
    • Are there any statistics on the ratio of number of objects (or number of cycles) that iskept by the GC to the number that is deallocated by the GC?
  9. picnixz
    added
    type-featureA feature request or enhancementA feature request or enhancement
    and removed
    3.14bugs and security fixesbugs and security fixes
    on Dec 3, 2024
  10. mpage
    added a commit that references this issue on Dec 3, 2024

    Revert "pythonGH-126491: GC: Mark objects reachable from roots before…

    2923163
  11. nascheme commented on Dec 3, 2024

    @nascheme
    nascheme
    on Dec 3, 2024
    Member
    More actions

    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.

  12. mpage
    added 2 commits that reference this issue on Dec 4, 2024

    Reapply "pythonGH-126491: GC: Mark objects reachable from roots befor…

    4049072

    Revert "pythonGH-126491: GC: Mark objects reachable from roots before…

    0f5d11c
  13. markshannon
    added a commit that references this issue on Dec 6, 2024

    GH-126491: Lower heap size limit with faster marking (GH-127519)

    023b7d2
  14. encukou
    added 2 commits that reference this issue on Dec 9, 2024

    Revert "pythonGH-126491: Lower heap size limit with faster marking (p…

    16327ad

    gh-126491: Revert "GH-126491: Lower heap size limit with faster marki…

    690fe07
  15. encukou commented on Dec 10, 2024

    @encukou
    encukou
    on Dec 10, 2024
    Member
    More actions

    I've reverted the last change, which introduced a refleak.

  16. srinivasreddy
    added 3 commits that reference this issue on Jan 8, 2025

    pythonGH-126491: GC: Mark objects reachable from roots before doing c…

    59470ef

    pythonGH-126491: Lower heap size limit with faster marking (pythonGH-…

    52244d1

    pythongh-126491: Revert "pythonGH-126491: Lower heap size limit with …

    13d7d0b
  17. ebonnal
    added 3 commits that reference this issue on Jan 12, 2025

    pythonGH-126491: GC: Mark objects reachable from roots before doing c…

    452fbb4

    Revert "pythonGH-126491: GC: Mark objects reachable from roots before…

    53b8263

    pythonGH-126491: GC: Mark objects reachable from roots before doing c…

    f926b8c
  18. nascheme commented on Feb 26, 2025

    @nascheme
    nascheme
    on Feb 26, 2025
    Member
    More actions

    Could this be closed now? Or, are we waiting for a revised version of gh-127519 to be merged? @markshannon

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    interpreter-core(Objects, Python, Grammar, and Parser dirs)(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usagePerformance or resource usagetype-featureA feature request or enhancementA feature request or enhancement

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      You are visitor 01402503 — GeezerVison does not store the pages you look up.
      Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.