From c0c4ec2da14429d0e6c9aa30f32439e85edd8f94 Mon Sep 17 00:00:00 2001 From: Michael Anthony Knyszek Date: Thu, 16 Sep 2021 22:14:25 +0000 Subject: design: update gc-pacer-redesign and remove inaccuracies This change updates the GC pacer redesign design document to remove a few inaccuracies and update two points that became apparent after experimentation. Firstly, the inaccuracies were mostly around what was ignored. For instance, goroutines already donate their debt or credit back to the global pool on death. Secondly, the definition of the heap goal included S_n and G_n twice erroneously. It was written that way with _overall_ GC-work-related memory used in mind, but the definition is _just_ for heap memory. Lastly, it turns out that the current pacer does (in its own indirect way) account for idle priority GC in some way, and not accounting for it in the new pacer leads to a performance regression. This change adds a section describing how to account for it. For golang/go#44167. Change-Id: I396bbcb87fc3acd84584b10769e31d7da699fdb9 Reviewed-on: https://go-review.googlesource.com/c/proposal/+/350429 Reviewed-by: Michael Knyszek --- design/44167-gc-pacer-redesign.md | 55 +++++++++++++++++++-------------- design/44167/eqn1.png | Bin 10205 -> 10205 bytes design/44167/eqn2.png | Bin 1172 -> 1089 bytes design/44167/eqn3.png | Bin 1329 -> 1329 bytes design/44167/eqn4.png | Bin 1489 -> 1489 bytes design/44167/eqn5.png | Bin 1527 -> 1527 bytes design/44167/eqn6.png | Bin 2714 -> 2714 bytes design/44167/eqn7.png | Bin 5899 -> 5899 bytes design/44167/eqn8.png | Bin 2060 -> 2060 bytes design/44167/gc-pacer-redesign.src.md | 56 +++++++++++++++++++--------------- design/44167/inl1.png | Bin 368 -> 368 bytes design/44167/inl10.png | Bin 391 -> 391 bytes design/44167/inl11.png | Bin 359 -> 359 bytes design/44167/inl12.png | Bin 775 -> 775 bytes design/44167/inl13.png | Bin 617 -> 617 bytes design/44167/inl14.png | Bin 355 -> 355 bytes design/44167/inl15.png | Bin 364 -> 364 bytes design/44167/inl16.png | Bin 543 -> 543 bytes design/44167/inl17.png | Bin 426 -> 426 bytes design/44167/inl18.png | Bin 447 -> 447 bytes design/44167/inl19.png | Bin 395 -> 395 bytes design/44167/inl2.png | Bin 449 -> 449 bytes design/44167/inl20.png | Bin 397 -> 397 bytes design/44167/inl21.png | Bin 434 -> 434 bytes design/44167/inl22.png | Bin 464 -> 464 bytes design/44167/inl23.png | Bin 419 -> 419 bytes design/44167/inl24.png | Bin 531 -> 531 bytes design/44167/inl25.png | Bin 758 -> 758 bytes design/44167/inl26.png | Bin 698 -> 698 bytes design/44167/inl27.png | Bin 478 -> 478 bytes design/44167/inl28.png | Bin 439 -> 439 bytes design/44167/inl29.png | Bin 389 -> 389 bytes design/44167/inl3.png | Bin 455 -> 455 bytes design/44167/inl4.png | Bin 482 -> 482 bytes design/44167/inl5.png | Bin 462 -> 462 bytes design/44167/inl6.png | Bin 374 -> 374 bytes design/44167/inl7.png | Bin 357 -> 357 bytes design/44167/inl8.png | Bin 351 -> 351 bytes design/44167/inl9.png | Bin 407 -> 407 bytes 39 files changed, 64 insertions(+), 47 deletions(-) diff --git a/design/44167-gc-pacer-redesign.md b/design/44167-gc-pacer-redesign.md index 23b4242..62909bf 100644 --- a/design/44167-gc-pacer-redesign.md +++ b/design/44167-gc-pacer-redesign.md @@ -409,6 +409,37 @@ As a result, I propose the target utilization be reduced once again to 25%, eliminating GC assists in the steady-state (that's not out-pacing the GC), and potentially improving application latency as a result. +#### Idle-priority background GC workers + +Idle-priority GC workers are extra workers that run if the application isn't +utilizing all `GOMAXPROCS` worth of parallelism. +The scheduler schedules "low priority" background workers on any additional CPU +resources, and this ultimately skews utilization measurements in the GC. +In today's pacer, they're somewhat accounted for. +In general, the idle workers skew toward undershoot: because the pacer is not +explicitly aware of the idle workers, GC cycles will complete sooner than it +might expect. +However if a GC cycle completes early, then in theory the current pacer will +simply adjust. +From its perspective, scanning and marking objects was just faster than +expected. + +The new proposed design must also account for them somehow. +I propose including idle priority worker CPU utilization in both the measured +utilization, ![`u_n`](44167/inl23.png), and the target utilization, +![`u_t`](44167/inl9.png), in each GC cycle. +In this way, the only difference between the two terms remains GC assist +utilization, and while idle worker CPU utilization remains stable, the pacer may +effectively account for it. + +Unfortunately this does mean idle-priority GC worker utilization becomes part of +the definition of a GC steady-state, making it slightly more fragile. +The good news is that that was already true. +Due to other issues with idle-priority GC workers, it may be worth revisiting +them as a concept, but they do appear to legitimately help certain applications, +particularly those that spend a significant chunk of time blocked on I/O, yet +spend some significant chunk of their time awake allocating memory. + ### Smoothing out GC assists This discussion of GC assists brings us to the existing issues around pacing @@ -503,8 +534,6 @@ though many are. Notable exclusions are: 1. Mark assists are front-loaded in a GC cycle. 1. The hard heap goal isn't actually hard in some circumstances. -1. Dealing with idle GC workers. -1. Donating goroutine assist credit/debt on exit. 1. Existing trigger limits to prevent unbounded memory growth. (1) is difficult to resolve without special cases and arbitrary heuristics, and @@ -521,27 +550,7 @@ progress, and how GC assists are a back-up mechanism. I believe that the fundamental problem there lies with the fact that fractional GC workers don't provide that sort of consistent progress. -For (3) I believe we should remove idle GC workers entirely, which is why this -document ignores them. -Idle GC workers are extra mark workers that run if the application isn't -utilizing all GOMAXPROCS worth of parallelism. -The scheduler schedules "low priority" background workers on any additional CPU -resources, and this ultimately skews utilization measurements in the GC, because -as of today they're unaccounted for. -Unfortunately, it's likely that idle GC workers have accidentally become -necessary for the GC to make progress, so just pulling them out won't be quite -so easy. -I believe that needs a separate proposal given other large potential changes -coming to the compiler and runtime in the near future, because there's -unfortunately a fairly significant risk of bugs with doing so, though I do think -it's ultimately an improvement. -See [the related issue for more -details](https://github.com/golang/go/issues/44163). - -(4) is easy and I don't believe needs any deliberation. -That is a bug we should simply fix. - -For (5), I propose we retain the limits, translated to the current design. +For (3), I propose we retain the limits, translated to the current design. For reference, these limits are ![`0.95 (\gamma - 1)`](44167/inl25.png) as the upper-bound on the trigger ratio, and ![`0.6 (\gamma - 1)`](44167/inl26.png) as the lower-bound. diff --git a/design/44167/eqn1.png b/design/44167/eqn1.png index 7261d6e..a092617 100644 Binary files a/design/44167/eqn1.png and b/design/44167/eqn1.png differ diff --git a/design/44167/eqn2.png b/design/44167/eqn2.png index 6207419..209b6b2 100644 Binary files a/design/44167/eqn2.png and b/design/44167/eqn2.png differ diff --git a/design/44167/eqn3.png b/design/44167/eqn3.png index 1919c35..bad25d3 100644 Binary files a/design/44167/eqn3.png and b/design/44167/eqn3.png differ diff --git a/design/44167/eqn4.png b/design/44167/eqn4.png index 0ec898d..428cd18 100644 Binary files a/design/44167/eqn4.png and b/design/44167/eqn4.png differ diff --git a/design/44167/eqn5.png b/design/44167/eqn5.png index c120a67..b9edde2 100644 Binary files a/design/44167/eqn5.png and b/design/44167/eqn5.png differ diff --git a/design/44167/eqn6.png b/design/44167/eqn6.png index 6806914..76dcb0f 100644 Binary files a/design/44167/eqn6.png and b/design/44167/eqn6.png differ diff --git a/design/44167/eqn7.png b/design/44167/eqn7.png index 6c02c17..40a1913 100644 Binary files a/design/44167/eqn7.png and b/design/44167/eqn7.png differ diff --git a/design/44167/eqn8.png b/design/44167/eqn8.png index 302e9ed..2c8dbf3 100644 Binary files a/design/44167/eqn8.png and b/design/44167/eqn8.png differ diff --git a/design/44167/gc-pacer-redesign.src.md b/design/44167/gc-pacer-redesign.src.md index 1420b34..2662215 100644 --- a/design/44167/gc-pacer-redesign.src.md +++ b/design/44167/gc-pacer-redesign.src.md @@ -189,7 +189,7 @@ GC work. Let `$N_n$` be the heap goal for GC `$n$` ("N" stands for "Next GC"). ```render-latex -N_n = \gamma(M_{n-1} + S_n + G_n) +N_n = \gamma M_{n-1} + S_n + G_n ``` The old definition makes the assumption that non-heap sources of GC work are @@ -412,6 +412,36 @@ As a result, I propose the target utilization be reduced once again to 25%, eliminating GC assists in the steady-state (that's not out-pacing the GC), and potentially improving application latency as a result. +#### Idle-priority background GC workers + +Idle-priority GC workers are extra workers that run if the application isn't +utilizing all `GOMAXPROCS` worth of parallelism. +The scheduler schedules "low priority" background workers on any additional CPU +resources, and this ultimately skews utilization measurements in the GC. +In today's pacer, they're somewhat accounted for. +In general, the idle workers skew toward undershoot: because the pacer is not +explicitly aware of the idle workers, GC cycles will complete sooner than it +might expect. +However if a GC cycle completes early, then in theory the current pacer will +simply adjust. +From its perspective, scanning and marking objects was just faster than +expected. + +The new proposed design must also account for them somehow. +I propose including idle priority worker CPU utilization in both the measured +utilization, `$u_n$`, and the target utilization, `$u_t$`, in each GC cycle. +In this way, the only difference between the two terms remains GC assist +utilization, and while idle worker CPU utilization remains stable, the pacer may +effectively account for it. + +Unfortunately this does mean idle-priority GC worker utilization becomes part of +the definition of a GC steady-state, making it slightly more fragile. +The good news is that that was already true. +Due to other issues with idle-priority GC workers, it may be worth revisiting +them as a concept, but they do appear to legitimately help certain applications, +particularly those that spend a significant chunk of time blocked on I/O, yet +spend some significant chunk of their time awake allocating memory. + ### Smoothing out GC assists This discussion of GC assists brings us to the existing issues around pacing @@ -512,8 +542,6 @@ though many are. Notable exclusions are: 1. Mark assists are front-loaded in a GC cycle. 1. The hard heap goal isn't actually hard in some circumstances. -1. Dealing with idle GC workers. -1. Donating goroutine assist credit/debt on exit. 1. Existing trigger limits to prevent unbounded memory growth. (1) is difficult to resolve without special cases and arbitrary heuristics, and @@ -530,27 +558,7 @@ progress, and how GC assists are a back-up mechanism. I believe that the fundamental problem there lies with the fact that fractional GC workers don't provide that sort of consistent progress. -For (3) I believe we should remove idle GC workers entirely, which is why this -document ignores them. -Idle GC workers are extra mark workers that run if the application isn't -utilizing all GOMAXPROCS worth of parallelism. -The scheduler schedules "low priority" background workers on any additional CPU -resources, and this ultimately skews utilization measurements in the GC, because -as of today they're unaccounted for. -Unfortunately, it's likely that idle GC workers have accidentally become -necessary for the GC to make progress, so just pulling them out won't be quite -so easy. -I believe that needs a separate proposal given other large potential changes -coming to the compiler and runtime in the near future, because there's -unfortunately a fairly significant risk of bugs with doing so, though I do think -it's ultimately an improvement. -See [the related issue for more -details](https://github.com/golang/go/issues/44163). - -(4) is easy and I don't believe needs any deliberation. -That is a bug we should simply fix. - -For (5), I propose we retain the limits, translated to the current design. +For (3), I propose we retain the limits, translated to the current design. For reference, these limits are `$0.95 (\gamma - 1)$` as the upper-bound on the trigger ratio, and `$0.6 (\gamma - 1)$` as the lower-bound. diff --git a/design/44167/inl1.png b/design/44167/inl1.png index 65e95c4..5a8fabf 100644 Binary files a/design/44167/inl1.png and b/design/44167/inl1.png differ diff --git a/design/44167/inl10.png b/design/44167/inl10.png index d456b71..2ed019b 100644 Binary files a/design/44167/inl10.png and b/design/44167/inl10.png differ diff --git a/design/44167/inl11.png b/design/44167/inl11.png index b49102e..83919e3 100644 Binary files a/design/44167/inl11.png and b/design/44167/inl11.png differ diff --git a/design/44167/inl12.png b/design/44167/inl12.png index e01717e..48d195e 100644 Binary files a/design/44167/inl12.png and b/design/44167/inl12.png differ diff --git a/design/44167/inl13.png b/design/44167/inl13.png index 49e45f3..85c2de9 100644 Binary files a/design/44167/inl13.png and b/design/44167/inl13.png differ diff --git a/design/44167/inl14.png b/design/44167/inl14.png index 8fbcaba..c9bd278 100644 Binary files a/design/44167/inl14.png and b/design/44167/inl14.png differ diff --git a/design/44167/inl15.png b/design/44167/inl15.png index 0c92c3b..aacc6ca 100644 Binary files a/design/44167/inl15.png and b/design/44167/inl15.png differ diff --git a/design/44167/inl16.png b/design/44167/inl16.png index bb885e8..639824e 100644 Binary files a/design/44167/inl16.png and b/design/44167/inl16.png differ diff --git a/design/44167/inl17.png b/design/44167/inl17.png index de913d6..ce8dfac 100644 Binary files a/design/44167/inl17.png and b/design/44167/inl17.png differ diff --git a/design/44167/inl18.png b/design/44167/inl18.png index cc76b06..8dcceaa 100644 Binary files a/design/44167/inl18.png and b/design/44167/inl18.png differ diff --git a/design/44167/inl19.png b/design/44167/inl19.png index f258005..6d4c8eb 100644 Binary files a/design/44167/inl19.png and b/design/44167/inl19.png differ diff --git a/design/44167/inl2.png b/design/44167/inl2.png index b75dfe1..20029f9 100644 Binary files a/design/44167/inl2.png and b/design/44167/inl2.png differ diff --git a/design/44167/inl20.png b/design/44167/inl20.png index ebd9fee..b86b91a 100644 Binary files a/design/44167/inl20.png and b/design/44167/inl20.png differ diff --git a/design/44167/inl21.png b/design/44167/inl21.png index 65057ea..77ca2d4 100644 Binary files a/design/44167/inl21.png and b/design/44167/inl21.png differ diff --git a/design/44167/inl22.png b/design/44167/inl22.png index df1cd2f..1d560e4 100644 Binary files a/design/44167/inl22.png and b/design/44167/inl22.png differ diff --git a/design/44167/inl23.png b/design/44167/inl23.png index 58366dc..d66fade 100644 Binary files a/design/44167/inl23.png and b/design/44167/inl23.png differ diff --git a/design/44167/inl24.png b/design/44167/inl24.png index 254ac81..df164b1 100644 Binary files a/design/44167/inl24.png and b/design/44167/inl24.png differ diff --git a/design/44167/inl25.png b/design/44167/inl25.png index be1423f..71c19b2 100644 Binary files a/design/44167/inl25.png and b/design/44167/inl25.png differ diff --git a/design/44167/inl26.png b/design/44167/inl26.png index 5d08eab..86bfb70 100644 Binary files a/design/44167/inl26.png and b/design/44167/inl26.png differ diff --git a/design/44167/inl27.png b/design/44167/inl27.png index 1752ae2..b76bc3d 100644 Binary files a/design/44167/inl27.png and b/design/44167/inl27.png differ diff --git a/design/44167/inl28.png b/design/44167/inl28.png index f385442..f7f387d 100644 Binary files a/design/44167/inl28.png and b/design/44167/inl28.png differ diff --git a/design/44167/inl29.png b/design/44167/inl29.png index f447caa..5654f40 100644 Binary files a/design/44167/inl29.png and b/design/44167/inl29.png differ diff --git a/design/44167/inl3.png b/design/44167/inl3.png index 42bb9f1..3b607a2 100644 Binary files a/design/44167/inl3.png and b/design/44167/inl3.png differ diff --git a/design/44167/inl4.png b/design/44167/inl4.png index ea1729a..506375d 100644 Binary files a/design/44167/inl4.png and b/design/44167/inl4.png differ diff --git a/design/44167/inl5.png b/design/44167/inl5.png index 7090982..326b4a4 100644 Binary files a/design/44167/inl5.png and b/design/44167/inl5.png differ diff --git a/design/44167/inl6.png b/design/44167/inl6.png index 4c5d9a4..b04cbec 100644 Binary files a/design/44167/inl6.png and b/design/44167/inl6.png differ diff --git a/design/44167/inl7.png b/design/44167/inl7.png index 5516cd6..d7cb17e 100644 Binary files a/design/44167/inl7.png and b/design/44167/inl7.png differ diff --git a/design/44167/inl8.png b/design/44167/inl8.png index fa56487..298e846 100644 Binary files a/design/44167/inl8.png and b/design/44167/inl8.png differ diff --git a/design/44167/inl9.png b/design/44167/inl9.png index 05c1a1c..3e6551a 100644 Binary files a/design/44167/inl9.png and b/design/44167/inl9.png differ -- cgit v1.3