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 — GH-126491: Lower heap size limit with faster marking by markshannon · Pull Request #127519 · python/cpython

Conversation

@markshannon

@markshannon markshannon commented Dec 2, 2024 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

With marking added to the cyclic GC (#127110) we spend a lot of the time in the GC forming transitive closures, both for marking and for the increments of the incremental GC.

Unfortunately the current algorithm has a couple of mistakes in it. One harmful, one beneficial.

  • The beneficial one is counting the initial mark twice. This helps because it reduces the cost of GC on heaps with little or no garbage
  • The harmful one is allowing the amount of work done to grow in proportion to the heap size.

These more or less cancel out.
This PR deliberately counts marking as twice as effective as normal collection, but limits the amount of work done.
To do so, we need to increase the typical amount of work done a bit.
This has the advantage of limiting the amount of garbage to (roughly) 1/3 of the heap.

This PR does two things:

  • Speeds up the marking and increment creation phases
  • Visits objects a bit faster to maintain a lower heap size.
  • Issue: Mark all objects reachable from roots as live before doing main cyclic GC pass #126491

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
markshannon added 7 commits November 18, 2024 14:32
@markshannon
Faster marking of reachable objects
3038a78
@markshannon
Handle more classes in fast marking
c024484
@markshannon
Add support for asyn generators on fast path. Simplify counting
e8497ae
@markshannon
Check stackref before converting to PyObject *
4c1a6bc
@markshannon
Rename stuff
6efb4c0
@markshannon
Remove expand_region_transitively_reachable and use move_all_transiti…
b1c7ab0 
…vely_reachable.
@markshannon
Merge branch 'main' into faster-marking
07f228b
@bedevere-app bedevere-app Bot mentioned this pull request Dec 2, 2024
Mark all objects reachable from roots as live before doing main cyclic GC pass #126491
Open
@markshannon
Fix compiler warnings and linkage
51ff78e
@markshannon markshannon added the skip news label Dec 2, 2024
markshannon added 10 commits December 2, 2024 16:12
@markshannon
Fix another linkage issue
df907b5
@markshannon
Try 'extern'
9ca64f5
@markshannon
Go back to PyAPI_FUNC and move functions together
bda13f4
@markshannon
Use _Py_FALLTHROUGH
d9d63c8
@markshannon
Add necessary #ifndef Py_GIL_DISABLED
57b8820
@markshannon
Go back to using tp_traverse, but make traversal more efficient
a607059
@markshannon
Tidy up
1545508
@markshannon
A bit more tidying up
a1a38c8
@markshannon
Move all work to do calculations to one place
68fc90b
@markshannon
Assume that increments are 50% garbage for work done calculation
8893cf5
@markshannon

markshannon commented Dec 3, 2024

Copy link
Copy Markdown
Member Author

!buildbot iOS
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-bot

bedevere-bot commented Dec 3, 2024

Copy link
Copy Markdown

🤖 New build scheduled with the buildbot fleet by @markshannon for commit 8893cf5 🤖

The command will test the builders whose names match following regular expression: iOS

The builders matched are:

  • iOS ARM64 Simulator PR
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@markshannon

markshannon commented Dec 3, 2024

Copy link
Copy Markdown
Member Author

!buildbot Android
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-bot

bedevere-bot commented Dec 3, 2024

Copy link
Copy Markdown

🤖 New build scheduled with the buildbot fleet by @markshannon for commit 8893cf5 🤖

The command will test the builders whose names match following regular expression: Android

The builders matched are:

  • aarch64 Android PR
  • AMD64 Android PR
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@markshannon
Elaborate comment
ba20c7c
@markshannon markshannon changed the title GH-126491: Faster marking GH-126491: Lower heap size limit with faster marking Dec 4, 2024
@mhsmith mhsmith mentioned this pull request Dec 4, 2024
Two selective !buildbot commands in quick succession causes ALL buildbots to run python/buildmaster-config#566
Open
@markshannon
More tweaking of thresholds
8262bf0
@markshannon

markshannon commented Dec 4, 2024

Copy link
Copy Markdown
Member Author

!buildbot Android|iOS
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-bot

bedevere-bot commented Dec 4, 2024

Copy link
Copy Markdown

🤖 New build scheduled with the buildbot fleet by @markshannon for commit 8262bf0 🤖

The command will test the builders whose names match following regular expression: Android|iOS

The builders matched are:

  • iOS ARM64 Simulator PR
  • aarch64 Android PR
  • AMD64 Android PR
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@markshannon

markshannon commented Dec 4, 2024

Copy link
Copy Markdown
Member Author

Performance is a wash overall, but I think that is an artifact of our benchmarks. I would expect this to perform better on larger heaps and consume less memory, although the benchmarks show no overall change in memory consumption.

Note that the "create gc cycles" benchmark shows a 10% speedup and "gc traversal" an 8% speedup, but there is an equivalent slowdown on the "xml etree" benchmarks.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@markshannon
markshannon marked this pull request as ready for review December 4, 2024 14:03
@markshannon
markshannon requested a review from methane as a code owner December 4, 2024 14:03
@bedevere-app bedevere-app Bot added the awaiting core review label Dec 4, 2024
markshannon added 2 commits December 4, 2024 16:54
@markshannon
Do some algebra
3c2116e
@markshannon
Revert to 2M+I from 3M+I
72d0284
iritkatriel
iritkatriel reviewed Dec 5, 2024
View reviewed changes
Comment thread InternalDocs/garbage_collector.md Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread InternalDocs/garbage_collector.md Resolved

Uh oh!

There was an error while loading. Please reload this page.
Comment thread InternalDocs/garbage_collector.md Resolved

Uh oh!

There was an error while loading. Please reload this page.
@markshannon
Address review comments
0f182e2
iritkatriel
iritkatriel reviewed Dec 5, 2024
View reviewed changes
Comment thread InternalDocs/garbage_collector.md Outdated

To work out how much work we need to do, consider a heap with `L` live objects
and `G0` garbage objects at the start of a full scavenge and `G1` garbage objects
at the end of the scavenge. We don't want amount of garbage to grow, `G1 ≤ G0`, and

@iritkatriel iritkatriel Dec 5, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
at the end of the scavenge. We don't want amount of garbage to grow, `G1 ≤ G0`, and
at the end of the scavenge. We don't want the amount of garbage to grow, `G1 ≤ G0`, and

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread InternalDocs/garbage_collector.md Outdated
The number of new objects created `N` must be at least the new garbage created, `N ≥ G1`,
assuming that the number of live objects remains roughly constant.
If we set `T == 4*N` we get `T > 4*G1` and `T = L + G0 + G1` => `L + G0 > 3G1`
For a steady state heap `G0 == G1` we get `L > 2G` and the desired garbage ratio.

@iritkatriel iritkatriel Dec 5, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
For a steady state heap `G0 == G1` we get `L > 2G` and the desired garbage ratio.
For a steady state heap `G0 == G1` we get `L > 2*G0` and the desired garbage ratio.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread InternalDocs/garbage_collector.md Outdated
The number of new objects created `N` must be at least the new garbage created, `N ≥ G1`,
assuming that the number of live objects remains roughly constant.
If we set `T == 4*N` we get `T > 4*G1` and `T = L + G0 + G1` => `L + G0 > 3G1`
For a steady state heap `G0 == G1` we get `L > 2G` and the desired garbage ratio.

@iritkatriel iritkatriel Dec 5, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
For a steady state heap `G0 == G1` we get `L > 2G` and the desired garbage ratio.
For a steady state heap (`G0 == G1`) we get `L > 2G` and the desired garbage ratio.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread InternalDocs/garbage_collector.md Outdated

If we choose the amount of work done such that `2*M + I == 6N` then we can do
less work in most cases, but are still guaranteed to keep up.
Since `I ≥ G0 + G1` (not strictly true, but close enough)

@iritkatriel iritkatriel Dec 5, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
Since `I ≥ G0 + G1` (not strictly true, but close enough)
Since `I ≈ G0 + G1` (not strictly true, but close enough)

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@markshannon markshannon Dec 5, 2024 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The increments (I) can include some of the live heap, depending on the how much is keep alive by C extensions.
So ≥ is more correct. Although ≳ is even more correct.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread InternalDocs/garbage_collector.md Outdated
If we choose the amount of work done such that `2*M + I == 6N` then we can do
less work in most cases, but are still guaranteed to keep up.
Since `I ≥ G0 + G1` (not strictly true, but close enough)
`T == M + I == (6N + I)/2` and `(6N + I)/2 ≥ 4G`, so we can keep up.

@iritkatriel iritkatriel Dec 5, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
`T == M + I == (6N + I)/2` and `(6N + I)/2 ≥ 4G`, so we can keep up.
`T == M + I == (6N + I)/2` and `(6N + I)/2 ≳ 4G`, so we can keep up.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread InternalDocs/garbage_collector.md Outdated
`T == M + I == (6N + I)/2` and `(6N + I)/2 ≥ 4G`, so we can keep up.

The reason that this improves performance is that `M` is usually much larger
than `I` Suppose `M == 10I`, then `T ≅ 3N`.

@iritkatriel iritkatriel Dec 5, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
than `I` Suppose `M == 10I`, then `T ≅ 3N`.
than `I`. If `M == 10I`, then `T ≅ 3N`.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread Python/gc.c
assess_work_to_do(GCState *gcstate)
{
/* The amount of work we want to do depends on three things.
/* The amount of work we want to do depends on two things.

@iritkatriel iritkatriel Dec 5, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is it worth linking to the doc from here?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
markshannon reacted with thumbs up emoji
All reactions
  • 👍 1 reaction
Comment thread Python/gc.c Outdated
}
intptr_t new_objects = gcstate->young.count;
intptr_t max_heap_fraction = new_objects*3/2;
intptr_t max_heap_fraction = new_objects*5;

@iritkatriel iritkatriel Dec 5, 2024

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why is this called fraction?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@markshannon markshannon Dec 5, 2024

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Not for any good reason. I'll rename it.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@markshannon
Address review comments and clarify code a bit
d3c21bb
iritkatriel
iritkatriel approved these changes Dec 5, 2024
View reviewed changes
@bedevere-app bedevere-app Bot added awaiting merge and removed awaiting core review labels Dec 5, 2024
@markshannon
markshannon merged commit 023b7d2 into python:main Dec 6, 2024
@bedevere-app bedevere-app Bot removed the awaiting merge label Dec 6, 2024
@encukou

encukou commented Dec 9, 2024

Copy link
Copy Markdown
Member

This commit introduced reference leaks in test_import.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
encukou added a commit to encukou/cpython that referenced this pull request Dec 9, 2024
@encukou
Revert "pythonGH-126491: Lower heap size limit with faster marking (p…
16327ad 
…ythonGH-127519)"

This reverts commit 023b7d2, which introduced
a refleak.
@encukou

encukou commented Dec 9, 2024

Copy link
Copy Markdown
Member

I filed a revert PR: #127770
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
encukou added a commit that referenced this pull request Dec 10, 2024
@encukou
gh-126491: Revert "GH-126491: Lower heap size limit with faster marki…
690fe07 
…ng (GH-127519)" (GH-127770)

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

This reverts commit 023b7d2, which introduced
a refleak.
srinivasreddy pushed a commit to srinivasreddy/cpython that referenced this pull request Jan 8, 2025
@markshannon @srinivasreddy
pythonGH-126491: Lower heap size limit with faster marking (pythonGH-…
52244d1 
…127519)

* Faster marking of reachable objects

* Changes calculation of work to do and work done.

* Merges transitive closure calculations
srinivasreddy pushed a commit to srinivasreddy/cpython that referenced this pull request Jan 8, 2025
@encukou @srinivasreddy
pythongh-126491: Revert "pythonGH-126491: Lower heap size limit with …
13d7d0b 
…faster marking (pythonGH-127519)" (pythonGH-127770)

Revert "pythonGH-126491: Lower heap size limit with faster marking (pythonGH-127519)"

This reverts commit 023b7d2, which introduced
a refleak.
@markshannon markshannon mentioned this pull request Jan 8, 2025
test_import leaks references #127738
Closed
@markshannon
markshannon deleted the faster-marking branch January 10, 2025 16:23
This was referenced Jul 25, 2025
Inconsistency handling of immortal objects in gc #137110
Closed
gh-137110: Untrack immortal objects from expand_region_transitivity_reachable #137111
Closed
This was referenced Nov 24, 2025
GH-141890: Fix GC double-counting of marked objects #141891
Closed
GH-142002: Revert GC changes to "work_to_do" logic. #142001
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@iritkatriel iritkatriel iritkatriel approved these changes
@methane methane Awaiting requested review from methane methane is a code owner

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

skip news

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

4 participants

@markshannon @bedevere-bot @encukou @iritkatriel
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
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.