[1] https://gist.github.com/stedolan/52c13d6b1a30276db31ca98683c8db16
Stephen Dolan suggested that we count only live data as sweeping work for the purpose of GC pacing. In other words, the work counter for sweeping is only incremented when we sweep a live block, not when we sweep a free block or a garbage block.
This is to improve the stability of the system by removing a feedback loop. If we count the whole heap size as sweeping work, then the GC speed depends on the heap size, which itself depends on the GC speed (if the GC is slow, heap size will increase).
Then the formulas found in [1] are modified as follows:
Allocated data at cycle start:
L + Lg
Allocated data at the end of marking:
L + Lg + L/m
Allocated data at the end of sweeping, assuming that we also sweep all the data allocated during sweeping (which is all live, as far as this cycle is concerned):
L + L/m + (L + L/m) / s + (L + L/m) / s^2 + ...
= (L + L/m) s / (s - 1)
This is: what was live at cycle start (L), plus what was allocated during marking (L/m), plus what was allocated during sweeping of the (L + L/m) that are live at the beginning of sweeping ((L + L/m) / s), plus what was allocated during the sweeping of these allocations, etc.
L + L g' = (L + L/m) s / (s - 1)
1 + g' = (1 + 1/m) s / (s - 1)
g' = (s/m + 1) / (s - 1) = 1/m + 1/(s-1) + 1/m(s-1)
There is no linear recurrence anymore, but the stability condition is
still the same: s > 1.
the overhead o = g + 1/m is now:
o = 2/m + 1/(s-1) + 1/m(s-1)
Still taking
λ = m/s
m = λs
We now have
o = 2/λs + 1/(s-1) + 1/λs(s-1)
oλs^2 - (oλ + λ + 2)s + 1 = 0
Solving for s, we get two solutions, using μ = 1 + 2/λ to make it more readable:
s1 = 1/2 + (μ + sqrt(o^2 + μ^2)) / 2o
s2 = 1/2 + (μ - sqrt(o^2 + μ^2)) / 2o
s2 is less than 1, so our solution is s1.