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

proposal: runtime: GC pacer redesign #44167

Closed
mknyszek opened this issue Feb 8, 2021 · 29 comments
Closed

proposal: runtime: GC pacer redesign #44167

mknyszek opened this issue Feb 8, 2021 · 29 comments

Comments

@mknyszek
Copy link
Contributor

@mknyszek mknyszek commented Feb 8, 2021

GC Pacer Redesign

Author: Michael Knyszek (with lots of input from Austin Clements, David Chase, and Jeremy Faller)

Abstract

Go's tracing garbage collector runs concurrently with the application, and thus requires an algorithm to determine when to start a new cycle. In the runtime, this algorithm is referred to as the pacer. Until now, the garbage collector has framed this process as an optimization problem, utilizing a proportional controller to achieve a desired stopping-point (that is, the cycle completes just as the heap reaches a certain size) as well as a desired CPU utilization. While this approach has served Go well for a long time, the design has accrued many corner cases due to resolved issues, as well as a backlog of unresolved issues.

I propose redesigning the garbage collector's pacer from the ground up to capture the things it does well and eliminate the problems that have been discovered.

More specifically, I propose:

  1. Including all non-heap sources of GC work (stacks, globals) in pacing decisions.
  2. Reframing the pacing problem as a search problem, "solved" by a proportional-integral controller,
  3. Extending the hard heap goal to the worst-case heap goal of the next GC,

(1) will resolve long-standing issues with small heap sizes, allowing the Go garbage collector to scale down and act more predictably in general.
(2) will eliminate offset error present in the current design, will allow turning off mark-assist almost entirely outside of exceptional cases, improving allocation latency, and will enable clearer designs for setting memory limits on Go applications.
(3) will enable smooth and consistent response to large changes in the live heap size with large GOGC values.

Full design

Found here.

@mknyszek mknyszek added this to the Go1.17 milestone Feb 8, 2021
@mknyszek mknyszek self-assigned this Feb 8, 2021
@gopherbot
Copy link

@gopherbot gopherbot commented Feb 8, 2021

Change https://golang.org/cl/290489 mentions this issue: design: add GC pacer redesign

Loading

@ianlancetaylor ianlancetaylor added this to Incoming in Proposals Feb 8, 2021
@mknyszek
Copy link
Contributor Author

@mknyszek mknyszek commented Feb 8, 2021

By the way: this design feels solid to me, but has not gone through any rounds of feedback yet. In the interest of transparency, I'm hoping to get feedback and work on this here on GitHub going forward.

So, given that, I would not be surprised if there are errors in the document. Please take a look when you have a chance!

CC @randall77 @jeremyfaller @dr2chase @aclements

Loading

@storozhukBM
Copy link

@storozhukBM storozhukBM commented Feb 12, 2021

@mknyszek

Do I understand correctly that the forcegcperiod is required because the current pacer does not consider non-heap sources of GC work? Is it necessary to call GC periodically in application with effectively zero heap allocation rate to collects stacks, etc.? If I understood your proposal correctly, it seems like it should be possible to remove these periodic calls of GC, and applications that don't create new goroutines and don't allocate anything on heap should never trigger garbage collections, which is a good benefit by itself.

Loading

@mknyszek
Copy link
Contributor Author

@mknyszek mknyszek commented Feb 13, 2021

@storozhukBM forcegcperiod is pretty much completely separate from this proposal. Not accounting for non-heap sources of work more directly affects the minimum heap size and whether the GC reaches its goals. Related though is #44163, which is partly motivated by some of the ill effects of the forcegcperiod trigger.

I believe forcegcperiod exists these days to help finalizers run in long-running mostly-idle programs. For example, if you have an external resource tied to the finalizer, you want that cleaned up eventually (and sooner, probably). Going by the API it need not ever run. But, then we could just turn the forced GC on only if there's active finalizers or something, so I'm not convinced that's the only reason. Shrinking stacks periodically also might be a reason, but that seems less critical.

Anyway, I have to look into this again so don't quote me. My memory is hazy. :) I'll dig into the reasons why next week (I don't see them documented anywhere).

Loading

gopherbot pushed a commit to golang/proposal that referenced this issue Feb 16, 2021
For golang/go#44167.

Change-Id: I468aa78edb8588b4e48008ad44cecc08544a8f48
Reviewed-on: https://go-review.googlesource.com/c/proposal/+/290489
Reviewed-by: Michael Pratt <mpratt@google.com>
Reviewed-by: Jeremy Faller <jeremy@golang.org>
@gopherbot
Copy link

@gopherbot gopherbot commented Feb 16, 2021

Change https://golang.org/cl/292789 mentions this issue: design: add user-configurable memory target

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Feb 18, 2021

Change https://golang.org/cl/293790 mentions this issue: design: regenerate graphs for GC pacer redesign

Loading

gopherbot pushed a commit to golang/proposal that referenced this issue Feb 19, 2021
A couple of the graphs were wrong (from the wrong scenario, that is)
because I copied them in manually. Fatal mistake.

Regenerate the graphs following the usual pipeline. Because there's
a degree of jitter and randomness in these graphs they end up slightly
different, but they're all mostly the same.

By regenerating these graphs, it also adds a new line to each graph
for the live heap size. I think this is nice for readability, so I'll
let that get updated too.

For golang/go#44167.

Change-Id: I097f812ba07ca7fd740d8460e2830de6492b3945
Reviewed-on: https://go-review.googlesource.com/c/proposal/+/293790
Reviewed-by: Michael Pratt <mpratt@google.com>
@gopherbot
Copy link

@gopherbot gopherbot commented Feb 23, 2021

Change https://golang.org/cl/295509 mentions this issue: design: add initial conditions section to GC pacer redesign

Loading

gopherbot pushed a commit to golang/proposal that referenced this issue Feb 23, 2021
I realized I neglected to talk about initial conditions, even though all
the simulations clearly set *something*.

For golang/go#44167.

Change-Id: Ia1727d5c068847e9192bf87bc1b6a5f0bb832303
Reviewed-on: https://go-review.googlesource.com/c/proposal/+/295509
Reviewed-by: Michael Pratt <mpratt@google.com>
@gopherbot
Copy link

@gopherbot gopherbot commented Apr 1, 2021

Change https://golang.org/cl/306605 mentions this issue: runtime: make gcEffectiveGrowthRatio a method on gcControllerState

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 1, 2021

Change https://golang.org/cl/306603 mentions this issue: runtime: move next_gc and last_next_gc into gcControllerState

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 1, 2021

Change https://golang.org/cl/306599 mentions this issue: runtime: make gcSetTriggerRatio a method of gcControllerState

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 1, 2021

Change https://golang.org/cl/306600 mentions this issue: runtime: move gcPercent and heapMinimum into gcControllerState

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 1, 2021

Change https://golang.org/cl/306596 mentions this issue: runtime: break out GC pacer into its own file

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 1, 2021

Change https://golang.org/cl/306597 mentions this issue: runtime: rename gcpercent, readgogc, and heapminimum to match Go style

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 1, 2021

Change https://golang.org/cl/306602 mentions this issue: runtime: create setGCPercent method for gcControllerState

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 1, 2021

Change https://golang.org/cl/306604 mentions this issue: runtime: pass work.userForced to gcController.endCycle explicitly

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 1, 2021

Change https://golang.org/cl/306601 mentions this issue: runtime: create initializer for gcControllerState

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 1, 2021

Change https://golang.org/cl/306598 mentions this issue: runtime: move internal GC statistics from memstats to gcController

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 8, 2021

Change https://golang.org/cl/308690 mentions this issue: runtime: formalize and fix gcPercent synchronization

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 11, 2021

Change https://golang.org/cl/309274 mentions this issue: runtime: move pacer time updates and state resets into methods

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 11, 2021

Change https://golang.org/cl/309273 mentions this issue: runtime: detangle sweeper pacing from GC pacing

Loading

gopherbot pushed a commit that referenced this issue Apr 14, 2021
These variables are core to the pacer, and will be need to be non-global
for testing later.

Partially generated via

rf '
    ex . {
	gcPercent -> gcController.gcPercent
	heapMinimum -> gcController.heapMinimum
    }
'

The only exception to this generation is usage of these variables
in gcControllerState methods.

For #44167.

Change-Id: I8b620b3061114f3a3c4b65006f715fd977b180a8
Reviewed-on: https://go-review.googlesource.com/c/go/+/306600
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
gopherbot pushed a commit that referenced this issue Apr 14, 2021
Now that gcControllerState contains almost all of the pacer state,
create an initializer for it instead of haphazardly setting some fields.

For #44167.

Change-Id: I4ce1d5dd82003cb7c263fa46697851bb22a32544
Reviewed-on: https://go-review.googlesource.com/c/go/+/306601
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
gopherbot pushed a commit that referenced this issue Apr 14, 2021
This change breaks out the computations done by setGCPercent into
a method on gcControllerState for easier testing later. It leaves behind
the global implementation details.

For #44167.

Change-Id: I3b0cf1475b032fcd4ebbd01cf4e80de0b55ce7b0
Reviewed-on: https://go-review.googlesource.com/c/go/+/306602
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
gopherbot pushed a commit that referenced this issue Apr 14, 2021
This change moves next_gc and last_next_gc into gcControllerState under
the names heapGoal and lastHeapGoal respectively. These are
fundamentally GC pacer related values, and so it makes sense for them to
live here.

Partially generated by

rf '
    ex . {
	memstats.next_gc -> gcController.heapGoal
	memstats.last_next_gc -> gcController.lastHeapGoal
    }
'

except for updates to comments and gcControllerState methods, where
they're accessed through the receiver, and trace-related renames of
NextGC -> HeapGoal, while we're here.

For #44167.

Change-Id: I1e871ad78a57b01be8d9f71bd662530c84853bed
Reviewed-on: https://go-review.googlesource.com/c/go/+/306603
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
gopherbot pushed a commit that referenced this issue Apr 14, 2021
For #44167.

Change-Id: I15817006f1870d6237cd06dabad988da3f23a6d6
Reviewed-on: https://go-review.googlesource.com/c/go/+/306604
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
gopherbot pushed a commit that referenced this issue Apr 14, 2021
For #44167.

Change-Id: Ie3cf8d2960c843a782ec85426fa73c279adaed64
Reviewed-on: https://go-review.googlesource.com/c/go/+/306605
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
@mknyszek
Copy link
Contributor Author

@mknyszek mknyszek commented Apr 15, 2021

Unfortunately with everything already going into this release, I need to push this back.

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Sep 16, 2021

Change https://golang.org/cl/350429 mentions this issue: design: update gc-pacer-redesign and remove inaccuracies

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Oct 1, 2021

Change https://golang.org/cl/353353 mentions this issue: runtime: pass nanotime and gomaxprocs into endCycle explicitly

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Oct 1, 2021

Change https://golang.org/cl/353354 mentions this issue: runtime: add testing framework and basic tests for GC pacer

Loading

gopherbot pushed a commit that referenced this issue Oct 21, 2021
Currently gcController.gcPercent is read non-atomically by
gcControllerState.revise and gcTrigger.test, but these users may
execute concurrently with an update to gcPercent.

Although revise's results are best-effort, reading it directly in this
way is, generally speaking, unsafe.

This change makes gcPercent atomically updated for concurrent readers
and documents the complete synchronization semantics.

Because gcPercent otherwise only updated with the heap lock held or the
world stopped, all other reads can remain unsynchronized.

For #44167.

Change-Id: If09af103aae84a1e133e2d4fed8ab888d4b8f457
Reviewed-on: https://go-review.googlesource.com/c/go/+/308690
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
gopherbot pushed a commit that referenced this issue Oct 29, 2021
The sweeper's pacing state is global, so detangle it from the GC pacer's
state updates so that the GC pacer can be tested.

For #44167.

Change-Id: Ibcea989cd435b73c5891f777d9f95f9604e03bd1
Reviewed-on: https://go-review.googlesource.com/c/go/+/309273
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
gopherbot pushed a commit that referenced this issue Oct 29, 2021
Currently GC pacer updates are applied somewhat haphazardly via direct
field access. To facilitate ease of testing, move these field updates
into methods. Further CLs will move more of these updates into methods.

For #44167.

Change-Id: I25b10d2219ae27b356b5f236d44827546c86578d
Reviewed-on: https://go-review.googlesource.com/c/go/+/309274
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
Reviewed-by: Michael Pratt <mpratt@google.com>
gopherbot pushed a commit that referenced this issue Oct 29, 2021
This change moves heapLive and heapScan updates on gcController into a
method for better testability. It's also less error-prone because code
that updates these fields needs to remember to emit traces and/or call
gcController.revise; this method now handles those cases.

For #44167.

Change-Id: I3d6f2e7abb22def27c93feacff50162b0b074da2
Reviewed-on: https://go-review.googlesource.com/c/go/+/309275
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
gopherbot pushed a commit that referenced this issue Oct 29, 2021
This change adds two fields to gcControllerState: stackScan, used for
pacing decisions, and scannableStackSize, which directly tracks the
amount of space allocated for inuse stacks that will be scanned.

scannableStackSize is not updated directly, but is instead flushed from
each P when at an least 8 KiB delta has accumulated. This helps reduce
issues with atomics contention for newly created goroutines. Stack
growth paths are largely unaffected.

StackGrowth-48			51.4ns ± 0%	51.4ns ± 0%	~	(p=0.927 n=10+10)
StackGrowthDeep-48		6.14µs ± 3%	6.25µs ± 4%	~	(p=0.090 n=10+9)
CreateGoroutines-48		273ns ± 1%	273ns ± 1%	~	(p=0.676 n=9+10)
CreateGoroutinesParallel-48	65.5ns ± 5%	66.6ns ± 7%	~	(p=0.340 n=9+9)
CreateGoroutinesCapture-48	2.06µs ± 1%	2.07µs ± 4%	~	(p=0.217 n=10+10)
CreateGoroutinesSingle-48	550ns ± 3%	563ns ± 4%	+2.41%	(p=0.034 n=8+10)

For #44167.

Change-Id: Id1800d41d3a6c211b43aeb5681c57c0dc8880daf
Reviewed-on: https://go-review.googlesource.com/c/go/+/309589
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
gopherbot pushed a commit that referenced this issue Oct 29, 2021
For #44167.

Change-Id: I2cd13229d88f630451fabd113b0e5a04841e9e79
Reviewed-on: https://go-review.googlesource.com/c/go/+/309590
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
gopherbot pushed a commit that referenced this issue Oct 29, 2021
…plicitly

This is to facilitate testing of the pacer, since otherwise this is
accessing global state, which is impossible to stub out properly.

For #44167.

Change-Id: I52c3b51fc0ffff38e3bbe534bd66e5761c0003a8
Reviewed-on: https://go-review.googlesource.com/c/go/+/353353
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Michael Pratt <mpratt@google.com>
gopherbot pushed a commit that referenced this issue Oct 29, 2021
This change creates a formal exported interface for the GC pacer and
creates tests for it that simulate some series of GC cycles. The tests
are completely driven by the real pacer implementation, except for
assists, which are idealized (though revise is called repeatedly).

For #44167.

Change-Id: I0112242b07e7702595ca71001d781ad6c1fddd2d
Reviewed-on: https://go-review.googlesource.com/c/go/+/353354
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
Reviewed-by: Michael Pratt <mpratt@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
gopherbot pushed a commit that referenced this issue Nov 4, 2021
This change implements the GC pacer redesign outlined in #44167 and the
accompanying design document, behind a GOEXPERIMENT flag that is on by
default.

In addition to adding the new pacer, this CL also includes code to track
and account for stack and globals scan work in the pacer and in the
assist credit system.

The new pacer also deviates slightly from the document in that it
increases the bound on the minimum trigger ratio from 0.6 (scaled by
GOGC) to 0.7. The logic behind this change is that the new pacer much
more consistently hits the goal (good!) leading to slightly less
frequent GC cycles, but _longer_ ones (in this case, bad!). It turns out
that the cost of having the GC on hurts throughput significantly (per
byte of memory used), though tail latencies can improve by up to 10%! To
be conservative, this change moves the value to 0.7 where there is a
small improvement to both throughput and latency, given the memory use.

Because the new pacer accounts for the two most significant sources of
scan work after heap objects, it is now also safer to reduce the minimum
heap size without leading to very poor amortization. This change thus
decreases the minimum heap size to 512 KiB, which corresponds to the
fact that the runtime has around 200 KiB of scannable globals always
there, up-front, providing a baseline.

Benchmark results: https://perf.golang.org/search?q=upload:20211001.6

tile38's KNearest benchmark shows a memory increase, but throughput (and
latency) per byte of memory used is better.

gopher-lua showed an increase in both CPU time and memory usage, but
subsequent attempts to reproduce this behavior are inconsistent.
Sometimes the overall performance is better, sometimes it's worse. This
suggests that the benchmark is fairly noisy in a way not captured by the
benchmarking framework itself.

biogo-igor is the only benchmark to show a significant performance loss.
This benchmark exhibits a very high GC rate, with relatively little work
to do in each cycle. The idle mark workers are quite active. In the new
pacer, mark phases are longer, mark assists are fewer, and some of that
time in mark assists has shifted to idle workers. Linux perf indicates
that the difference in CPU time can be mostly attributed to write-barrier
slow path related calls, which in turn indicates that the write barrier
being on for longer is the primary culprit. This also explains the memory
increase, as a longer mark phase leads to more memory allocated black,
surviving an extra cycle and contributing to the heap goal.

For #44167.

Change-Id: I8ac7cfef7d593e4a642c9b2be43fb3591a8ec9c4
Reviewed-on: https://go-review.googlesource.com/c/go/+/309869
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
Reviewed-by: Michael Pratt <mpratt@google.com>
@mknyszek mknyszek closed this Nov 10, 2021
@gopherbot
Copy link

@gopherbot gopherbot commented Dec 1, 2021

Change https://golang.org/cl/368137 mentions this issue: runtime: switch back to a 4 MiB min heap for GOEXPERIMENT=pacerredesign

Loading

@rsc rsc moved this from Incoming to Accepted in Proposals Dec 1, 2021
gopherbot pushed a commit that referenced this issue Dec 2, 2021
The new minimum heap of 512 KiB has been the cause of some build
slowdown (~1%) and microbenchmark slowdown (usually ~0%, up to ~50%)
because of two reasons:
1. Applications with lots of small short-lived processes execute many
   more GC cycles.
2. Applications with heaps <4 MiB GC up to 8x more often.

In many ways these consequences are inevitable given how GOGC works,
however we need to investigate more as to whether the apparent slowdowns
are indeed unavoidable or if the GC has issues scaling down, which it's
too late for for this release.

Given that this release is already huge, it's OK to push this back.
We'll take a closer look at it next cycle, so place block it behind a
new goexperiment to allow users and ourselves to easily experiment with
it.

Fixes #49744.
Updates #44167.

Change-Id: Ibad51f7873de7517490c89802f3c593834e77ff0
Reviewed-on: https://go-review.googlesource.com/c/go/+/368137
Trust: Michael Knyszek <mknyszek@google.com>
Run-TryBot: Michael Knyszek <mknyszek@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Austin Clements <austin@google.com>
Reviewed-by: David Chase <drchase@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Proposals
Accepted
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants