Many years ago I read one of those Cliff Click “here’s
what I learned” articles in which he was giving advice about garbage
collector design, and one of the recommendations was that at a GC pause,
running mutator threads should cooperate with the collector by identifying roots from
their own stacks. You can read a similar assertion in their VEE2005
paper,
The Pauseless GC
Algorithm
,
though this wasn’t the source of the information.
One motivation for the idea was locality: a thread’s
stack is already local to a thread. Then specifically in the context of
a pauseless collector, you need to avoid races between the collector and
the mutator for a thread’s stack, and having the thread visit its own
stack neatly handles this problem.
However, I am not so interested any more in (so-called) pauseless collectors;
though I have not measured myself, I am convinced enough by the
arguments in the
Distilling the real costs of production garbage
collectors
paper, which finds that state of the art pause-minimizing collectors
actually increase both average and p99 latency, relative to a
well-engineered collector with a pause phase. So, the racing argument
is not so relevant to me, because a pause is happening anyway.
There was one more argument that I thought was interesting, which was
that having threads visit their own stacks is a kind of cheap
parallelism: the mutator threads are already there, they might as well
do some work; it could be that it saves time, if other threads
haven’t seen the safepoint yet. Mutators exhibit a
ragged stop
, in
the sense that there is no clean cutoff time at which all mutators stop
simultaneously, only a time after which no more mutators are running.
Visiting roots during a ragged stop introduces concurrency between the mutator
and the
collector
,
which is not exactly free; notably, it prevents objects marked while
mutators are running from being evacuated. Still, it could be worth it
in some cases.
Or so I thought! Let’s try to look at the problem analytically.
Consider that you have a system with
N
processors, a stop-the-world GC
with
N
tracing threads, and
M
mutator threads. Let’s assume that we
want to minimize GC latency, as defined by the time between GC is
triggered and the time that mutators resume. There will be one
triggering thread
that causes GC to begin, and then
M
–1
remote
threads
that need to reach a safepoint before the GC pause can begin.
The total amount of work that needs to be done during GC can be broken
down into
roots
i
, the time needed to visit roots for mutator
i
, and then
graph
, the time to trace the transitive closure of live
objects. We want to know whether it’s better to perform
roots
i
during
the ragged stop or in the GC pause itself.
Let’s first look to the case where
M
is 1 (just one mutator thread).
If we visit roots before the pause, we have
latencyragged,1 =
roots0 +
graphM
Which is to say, thread 0 triggers GC,
visits its own roots, then enters the pause in which the whole graph is
traced by all workers with maximum parallelism. (It may be that graph
tracing doesn’t fully parallelize, for example if the graph has a long
singly-linked list, but the parallelism with be maximal within the pause
as there are
N
workers tracing the graph.
If instead we visit roots within the pause, we have:
latencypause,1=
roots0+graphM
This is strictly better than the ragged-visit latency.
If we have two threads, then we will need to add in some delay,
corresponding to the time it takes for remote threads to reach a
safepoint. Let’s assume that there is a maximum period (in terms of
instructions) at which
a mutator will check for
safepoints
. In
that case the worst-case delay will be a constant, and we add it on to
the latency. Let us assume also there are more than two threads
available. The marking-roots-during-the-pause case it’s easiest to
analyze:
latencypause,2=
delay +
roots0+roots1+graphM
In this case, a ragged visit could win: while the triggering thread is
waiting for the remote thread to stop, it could perform
roots
0
, moving the work out of the pause, reducing pause
time, and reducing latency, for free.
However, we only have this win if the root-visiting time is smaller than
the safepoint delay; otherwise we are just prolonging the pause. Thing
is, you don’t know in general. If indeed the root-visiting time is
short, relative to the delay, we can assume the
roots
elements of our
equation are 0, and so the choice to mark during ragged stop doesn’t
matter at all! If we assume instead that root-visiting time is long,
then it is suboptimally parallelised: under-parallelised if we have more
than
M
cores, oversubscribed if
M
is greater than
N
, and
needlessly serializing before the pause while it waits for the last
mutator to finish marking its roots. What’s worse, root-visiting actually slows down
delay
, because the oversubscribed threads compete with visitation for CPU time.
So in summary, I plan to switch away from doing GC work during the ragged stop. It is complexity that doesn’t pay. Onwards and upwards!
chevron_right
Working of TinySPARQL Web IDE
TinySPARQL Web IDE
SPARQL Query successfully executed
Error handling