Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

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

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 ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
markshannon merged 24 commits intopython:mainfromfaster-cpython:faster-marking
Dec 6, 2024

Conversation

@markshannon
Copy link
Member

@markshannonmarkshannon commentedDec 2, 2024•
edited
Loading

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.

@markshannon
Copy link
MemberAuthor

!buildbot iOS

@bedevere-bot
Copy link

🤖 New build scheduled with the buildbot fleet by@markshannon for commit8893cf5 🤖

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

The builders matched are:

  • iOS ARM64 Simulator PR

@markshannon
Copy link
MemberAuthor

!buildbot Android

@bedevere-bot
Copy link

🤖 New build scheduled with the buildbot fleet by@markshannon for commit8893cf5 🤖

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

The builders matched are:

  • aarch64 Android PR
  • AMD64 Android PR

@markshannonmarkshannon changed the titleGH-126491: Faster markingGH-126491: Lower heap size limit with faster markingDec 4, 2024
@markshannon
Copy link
MemberAuthor

!buildbot Android|iOS

@bedevere-bot
Copy link

🤖 New build scheduled with the buildbot fleet by@markshannon for commit8262bf0 🤖

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

@markshannon
Copy link
MemberAuthor

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.

@markshannonmarkshannon marked this pull request as ready for reviewDecember 4, 2024 14:03

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
Copy link
Member

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 wanttheamount of garbage to grow,`G1 ≤ G0`, and

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.
Copy link
Member

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.

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.
Copy link
Member

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.


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)
Copy link
Member

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)

Copy link
MemberAuthor

@markshannonmarkshannonDec 5, 2024•
edited
Loading

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.

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.
Copy link
Member

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.

`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`.
Copy link
Member

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`.

assess_work_to_do(GCState*gcstate)
{
/* The amount of work we want to do depends onthree things.
/* The amount of work we want to do depends ontwo things.
Copy link
Member

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?

markshannon reacted with thumbs up emoji
Python/gc.c Outdated
}
intptr_tnew_objects=gcstate->young.count;
intptr_tmax_heap_fraction=new_objects*3/2;
intptr_tmax_heap_fraction=new_objects*5;
Copy link
Member

Choose a reason for hiding this comment

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

Why is this calledfraction?

Copy link
MemberAuthor

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.

@markshannonmarkshannon merged commit023b7d2 intopython:mainDec 6, 2024
43 checks passed
@encukou
Copy link
Member

This commit introduced reference leaks intest_import.

encukou added a commit to encukou/cpython that referenced this pull requestDec 9, 2024
@encukou
Copy link
Member

I filed a revert PR:#127770

encukou added a commit that referenced this pull requestDec 10, 2024
…ng (GH-127519)" (GH-127770)Revert "GH-126491: Lower heap size limit with faster marking (GH-127519)"This reverts commit023b7d2, which introduceda refleak.
srinivasreddy pushed a commit to srinivasreddy/cpython that referenced this pull requestJan 8, 2025
…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 requestJan 8, 2025
…faster marking (pythonGH-127519)" (pythonGH-127770)Revert "pythonGH-126491: Lower heap size limit with faster marking (pythonGH-127519)"This reverts commit023b7d2, which introduceda refleak.
@markshannonmarkshannon deleted the faster-marking branchJanuary 10, 2025 16:23
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment

Reviewers

@iritkatrieliritkatrieliritkatriel approved these changes

@methanemethaneAwaiting requested review from methanemethane is a code owner

Assignees

No one assigned

Labels

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@markshannon@bedevere-bot@encukou@iritkatriel
[8]ページ先頭
©2009-2025 Movatter.jp