The Pause That Wasn't Incremental

Python 3.14.0 shipped a new incremental cycle collector. Its selling point was shorter pauses: instead of now and then scanning every long-lived object at once, it scans the old objects a slice at a time. In April, after reports of memory blowing up in production, the core team did something unusual for a patch release: 3.14.5 swapped it back for the generational collector from 3.13. The discussion treated it as a trade: the incremental collector uses more memory, but it does have shorter pauses.

I read the 3.14.4 collector to see where the memory went, and measured it against 3.14.8. The memory story is real. The pause story depends on the workload. With a few million live objects and garbage that dies young, the incremental collector had by far the longest pauses: 214 ms against 0.2 ms.

How the incremental collector budgets

Both collectors start a collection when about 2,000 more container objects have been created than destroyed. The generational one then collects the young objects, and only occasionally the older generations. The incremental one (gc_collect_increment in 3.14.4's Python/gc.c) keeps a running budget, work_to_do. Each collection adds the number of new objects plus a slice proportional to the heap, capped at twice the new objects: about three units of work per new object. Scanning an object spends one unit. The young objects plus enough old ones to use up the budget make an increment, which is collected like a small generation.

A pass over the old objects starts with mark_at_start, which marks everything reachable from module globals and from the stacks of running frames, so the slices don't have to scan those. Its first line is a comment: // TO DO -- Make this incremental. It isn't. It walks the whole reachable heap in one go, and in a long-running program that's most of the heap. The marked objects are then subtracted from the budget, twice: once inside mark_at_start and once by its caller. (A 2024 change notes that the initial mark is counted twice and calls that beneficial.)

Then this, at the top of each collection:

gcstate->work_to_do += assess_work_to_do(gcstate);
if (gcstate->work_to_do < 0) {
    return;
}

While the budget is negative, a collection does nothing at all, not even the young objects. Sergey Miryanov described this early return in December, and Tim Peters watched young garbage go uncollected in the revert thread. They framed it as a memory problem. It's also a pause problem.

What a pass looks like

The test program holds a linked list of L small lists that stays alive the whole run. It then creates 10 million pairs of lists that point at each other, so each pair can only be freed by the cycle collector. With K = 0, each pair is dropped at once. With K = 1,000,000, a ring buffer keeps each pair alive for a million steps before dropping it, so it outlives several collections first. I timed every collection with gc.callbacks and sampled resident memory. Runs were one at a time on Linux arm64 using python-build-standalone builds, and figures are medians of three runs.

A trace with 4 million live objects and garbage that dies young (K = 0) on 3.14.4. This was a separate, instrumented run. Its pauses came out shorter than in the timed runs below (whose biggest were 182–216 ms), but the pattern was the same, four pauses over 10 ms per pass:

• The pass starts with a 37 ms collection that frees nothing. That's the mark.
• The next 1,332 collections each return at once, paying off the debt.
• Then one collection takes 133 ms and frees 2,670,660 objects: every young object created while the debt was being paid off.
• Freeing those cost budget too, so the next pile is a third the size (890,888 objects, 43 ms), then a third again (296,294, 14 ms).
• Then the next pass starts with another mark, about 2 million steps after the first.

The numbers follow from the code. Counting the mark twice puts the budget about 2 × 4M = 8M in debt. At three units per new object, that takes about 2.67M new objects to pay off, and those objects are the pile. Out of 9,990 collections in the run, 9,953 did nothing. The collector had stopped being incremental. It was a stop-the-world collector that ran every couple of million allocations, and its pause grew with the live heap.

Max pause vs live heap

Garbage that dies young (K = 0). This is the easy case for a generational collector: nothing gets promoted, so it never has to scan the old objects.

The generational collector's worst pause stays flat at 0.2 ms. The incremental collector's grows with the live heap, and so does its memory, by about 70 bytes per live object: the uncollected young pile. Total run time was about the same for both (2.2–2.6 s).

Where it does win

Garbage that outlives several collections (K = 1,000,000) is the case the incremental design is for. The generational collector has to promote these pairs and then do full collections to find them dead.

Here the incremental collector is nearly twice as fast and has shorter pauses, at about three times the memory (3.0–3.7×). That's the trade the revert discussion described, and it's real. But even here, its pause grows with the live heap (27 ms to 135 ms), because the mark at the start of each pass is still one piece.

One check: in a parallel sweep of 20 configurations at three runs each, 3.14.8 matched 3.13.16 within noise (for example, 358.7 vs 358.4 MB extra at 4M live objects). The revert really did restore the old behavior. Both have a default first threshold of 2,000.

What I take from it

• "Incremental" described the scan of the old objects, not the whole collector. The mark that starts each pass was a single pause over everything reachable, and the source said so.
• Charging that mark to the budget, and then skipping whole collections while in debt, turned the mark's cost into a second, bigger pause: freeing everything that piled up in the meantime. Both pauses scale with the live heap. A long-running program with a big live heap and mostly short-lived garbage is a common shape, and for it this design gave the longest pauses. With longer-lived garbage the incremental collector still paused less than the generational one, but its pauses grew with the live heap there too.
• I suspect the same debt is part of how memory piled up in the production reports from the revert discussion, but I haven't reproduced those workloads (see Adam Johnson's Django migrations post). Tim Peters' proposed fix in a follow-up thread, never letting the budget fall below the size of the young generation, should remove the second pause too. The first would remain until the mark is made incremental.

Limits: one synthetic workload shape (pairs of lists, one linked-list live heap), one platform, and three runs per point. A live heap held mostly in objects that aren't reachable from globals or stacks would behave differently. Pause times are wall-clock per gc.callbacks start/stop, so they include callback overhead (tiny next to these numbers). All of this is about a collector that is no longer shipped. If the incremental collector comes back through a PEP, as the revert thread suggested, a non-incremental mark and a budget that can skip young collections are the two things I'd test first.