Heap Growth and the Pacing of Collection Cycles

A collector that runs at the wrong time is worse than one that runs at the right time, even if both are correct. Collect too often and the program spends its cycles in marking and copying rather than in doing work; collect too late and the heap grows to the point where each collection takes a long time and the pause becomes visible. The policy that decides when is called pacing, and it is the part of a collector that has the most direct effect on what a program observes, because it controls both the memory footprint and the pause distribution.

Pacing is also the part with the least theoretical guidance, and the work that exists tends to come from the embedded and real-time end of the field, where the memory budget is fixed in advance. There is no optimal policy without a model of the program’s future allocation, and the runtime has only the past. Every practical policy is a feedback controller over measurements taken at collection points.

The one measurement that matters

After a collection completes, the collector knows the size of the live set: the bytes that survived. That number is the only reliable input to pacing, because it is the quantity that determines how much heap is needed and how expensive the next collection will be.

Two derived quantities follow. The heap overhead is the ratio of heap size to live-set size; a heap holding twice the live set has overhead 2. The allocation headroom is the difference between the current heap size and the live set, which is the number of bytes the program can allocate before the heap is full. A policy that maintains a fixed overhead ratio keeps the heap proportional to the live set; a policy that maintains fixed headroom keeps the interval between collections proportional to the allocation rate.

The choice between them determines the failure mode. Fixed overhead means the heap grows with the live set, which is right for a program whose live data grows slowly, and it means collections happen at a frequency proportional to the allocation rate divided by the live set. Fixed headroom means the heap grows with the allocation rate, which is right for a program that allocates heavily and retains little, and it means the collection frequency is constant regardless of the live set.

A collector that uses neither, and collects only when the heap is exhausted, produces a sawtooth: the heap grows until it is full, a collection frees a small amount, and the program immediately exhausts the heap again. That pattern is the classic symptom of a pacing policy that has no hysteresis.

The feedback loop, concretely

A workable policy has three parts: a trigger, a post-collection heap size adjustment, and a cap.

The trigger is usually a threshold on allocated bytes since the last collection, expressed as a fraction of the current heap. A threshold at 50 percent means a collection starts when half the heap has been allocated since the previous one, which gives the collector a fixed budget of work per collection and keeps the collection frequency proportional to the allocation rate.

The adjustment after a collection sets the next heap size from the measured live set. If the live set is L bytes and the target overhead ratio is r, the new heap size is r × L, rounded up to a page multiple and clamped to a minimum and a maximum.

/* Post-collection sizing: target a multiple of the measured live set. */
#define MIN_HEAP (4u << 20)           /* floor of 4 MiB */
static size_t next_heap_size(size_t live, size_t current, size_t max_heap) {
    const double overhead = 1.5;      /* 50 percent headroom above the live set */
    size_t target = (size_t)(live * overhead);
    if (target < MIN_HEAP) target = MIN_HEAP;
    if (target > max_heap) target = max_heap;
    /* Grow toward the target; shrink only on a clear excess. */
    if (target > current) return target;
    if (current * 3 > target * 4) return target;   /* current exceeds target by a third */
    return current;
}

The asymmetry in the last two lines is deliberate. Growing immediately is safe, because extra memory does not hurt correctness and avoids a collection. Shrinking on every small excess is risky, because the live set may grow again and the runtime would have to reacquire the memory it just released; the standard approach is to shrink only when the excess is substantial, as in the comparison above, which leaves the heap alone until it is more than a third larger than the target.

The cap matters more than it appears. Without a maximum, a program with a growing live set grows the heap until the operating system refuses to supply more, at which point the collector must either fail or run a full compaction under memory pressure. A maximum converts that failure into a collection that is slower than usual but still correct, and it is the parameter that a deployment sets when it knows the machine’s memory.

Pause time as a constraint rather than a consequence

On a machine with a latency requirement, the policy must be inverted: instead of sizing the heap and accepting the resulting pauses, the runtime fixes a pause target and sizes the work per collection to fit it.

For a copying young collector, the pause is proportional to the surviving bytes, so the policy is to keep the young region small enough that the survivor set is below the target. For a marking collector, the pause is proportional to the live set, so a fixed pause target forces the collector to make marking incremental or concurrent, which is what the tri-colour machinery in concurrent marking exists for. Once marking is concurrent, the pause is proportional to the root set and the dirty-card set, and the policy controls those instead.

There is a hard limit here that no policy can remove. A fully compacting collection over a live set of size L must move L bytes, and moving L bytes takes a time proportional to L. A pause target below that time cannot be met by a collector that compacts the whole heap in one stop; the collector must compact incrementally, which is why region-based collectors compact a subset of regions per cycle.

Allocation rate as the control variable

The allocation rate is the quantity the program controls and the collector measures. A program allocating at 500 MiB/s against a 64 MiB young generation triggers a young collection every 128 milliseconds or so, if the threshold is set at the whole region. Doubling the allocation rate halves the interval and doubles the collector’s share of the CPU, which is why the same collector behaves differently on two machines with different processors: the allocation rate is a property of the program and the hardware together.

Collectors that measure the allocation rate can use it to predict the next collection’s timing and to schedule concurrent marking so that it finishes before the heap fills. That is the central scheduling problem in a concurrent collector: marking must complete before the allocation that triggers the next collection, or the collector must start a new cycle on top of an unfinished one. The policy is to start marking when the free space falls below the amount that will be consumed during a mark, estimated from the recent allocation rate.

Getting that estimate wrong in the optimistic direction means the collector cannot finish marking before the heap is full, and it must either pause the program or fall back to a stop-the-world collection. Getting it wrong in the pessimistic direction means marking runs more often than necessary and the program pays the barrier cost plus the marking CPU for no benefit. The estimate is therefore the most consequential number in the collector, and it is a prediction, not a measurement.

When the policy cannot keep up

Three regimes defeat pacing.

The first is a live set that grows faster than the heap can be expanded. If the program retains 100 MiB per second and the machine can supply 1 GiB, the runtime has ten seconds before it must fail. No pacing policy avoids the failure; the best it can do is fail with a clear out-of-memory report rather than by thrashing.

The second is a program whose allocation is bursty. A batch job that allocates nothing for a minute and then allocates a gigabyte in a second defeats a policy tuned to the average rate. The collector either grows the heap during the burst, which may exceed the maximum, or collects repeatedly during the burst, which produces a cluster of pauses at exactly the moment the program is busiest.

The third is a program that holds a large live set and allocates slowly. Here the collection frequency is low, but each collection is expensive because it must traverse the live set, and the pause appears at long, unpredictable intervals. That pattern is the hardest to tune because the average cost is low and the worst case is high; the remedy is to make the expensive collection concurrent rather than to change the trigger.

Measuring the policy’s effect

The quantities that describe a collector’s behaviour to an operator are the pause distribution, the heap footprint over time, and the fraction of CPU spent collecting. All three are consequences of the pacing policy, and they trade against each other directly: a larger heap reduces collection frequency and CPU share while increasing footprint; a smaller heap does the reverse.

The distribution matters more than the average. A collector whose pauses are usually short but occasionally an order of magnitude longer violates a latency requirement that a collector with a uniformly longer but bounded pause satisfies, even though the second collector’s mean is worse. This is why pause histograms, not averages, are the right instrument, and why a policy tuned to the mean is usually tuned to the wrong statistic.

The heap footprint is likewise a distribution, and the maximum matters more than the mean, because it is the number that determines whether the process fits on the machine. A policy that grows the heap to 4 GiB during a burst and then shrinks it has a maximum of 4 GiB regardless of its steady state, and that maximum is what a deployment must provision.

The CPU share is the least visible and the most easily misattributed. A collector using 10 percent of the CPU on a machine with four cores is consuming 40 percent of one core, which shows up as reduced throughput rather than as a pause. Programs that are throughput-sensitive rather than latency-sensitive should be tuned for this number, which generally means a larger heap and less frequent collection.

The policy is part of the interface

The final point is that pacing is not an implementation detail hidden behind the collector. The heap maximum, the pause target, and the young generation size are visible to the program through the runtime’s configuration, and a program that ignores them is relying on defaults chosen for a different workload. A runtime that exposes no such controls has made the choice on the program’s behalf, which is defensible for a general-purpose language and indefensible for a runtime embedded in a system with a memory budget.

The measurements that make the policy work are also the ones worth exposing: live-set size after collection, allocation rate, pause durations. A runtime that reports them lets the program’s operators see the same numbers the collector used, which is the difference between tuning by evidence and tuning by guesswork.