Free-threaded GC improvements

I’ve been spending a little time investigating potential improvements to the free-threaded GC, using Claude Code to prototype and measure the effects. None of the code is in a state that I would be eager to merge into CPython, but I do think it shows some potential improvements, and some trade-offs we might want to consider (primarily memory vs. runtime). I’ll continue work on this (I have some time on my hands[1]), and I’m sharing all this in case other people are interested as well.

Benchmarks

First off, I started with some benchmarks (which may also be useful for other GC improvements being considered) because, well, you have to. They’re mostly tests for pathological behaviour, including some based on the problems that triggered the two reverts (in 3.14.5 and 3.13.0rc3) of the incremental GC. One of them, the Sphinx docs build, is near enough a real application that it makes a reasonable measurement, but I’m not sure it’s really a typical program. Even so, I think the benchmarks tell us something about GC performance, and that’s better than nothing. I’ve also included the GC-relevant benchmarks of pyperformance. The benchmarks are in cpython/Tools/gcbench at ftgc-benchmarks · Yhg1s/cpython · GitHub.

As a reminder (or if you’re not aware), the free-threaded collector is not generational. It only does full collections. Whichever thread triggers a collection stops the world, finds the objects by walking every thread’s mimalloc heaps, computes which are unreachable, starts the world again, and then frees the garbage. A collection runs once the number of new GC objects exceeds a quarter of the live heap.

That design has a few consequences the benchmarks below make visible:

  • Only full collections means much longer pauses on average.
  • Pause length grows with the heap, and on a fragmented heap with the free space too: walking a mimalloc page means following its free lists, which can involve a lot of cache misses. Also, the collector walks the heaps three times per collection.
  • There are two pauses, the second to re-traverse all the garbage to check for resurrection, even when nothing in it has a finalizer or a weakref (the only ways to get resurrection).
  • After the world is started again and the collecting thread is freeing objects, other threads can start allocating again right away. With the right (or wrong) circumstances in a multi-threaded workload, the other threads could be allocating faster than the collecting thread can free. (The ‘event_widgets’ benchmark shows this.)
  • Under some circumstances, specifically when deallocating on behalf of other threads, freed memory is not returned but left in the owning thread’s mimalloc heaps (until they allocate again).

Here’s some benchmark numbers for GIL vs. free-threaded (albeit not using optimized builds), where lower is better except when otherwise noted. (Not including most benchmarks for brevity. The full results are in EXAMPLE.md):

benchmark result gil ft change
doctree run time 8.12 s (8.11-8.13) 4.70 s (4.70-4.71) -42%
peak RSS 1,168 MB (1,167-1,168) 1,229 MB (1,229-1,229) +5.2%
longest collection 1,058 ms (1,057-1,059) 347 ms (347-348) -67%
migrations run time 10.2 s (10.2-10.2) 5.57 s (5.55-5.58) -46%
peak RSS 280 MB 320 MB (320-320) +14%
longest collection 242 ms (238-245) 107 ms (106-109) -56%
largest garbage backlog 11 objects 11 objects 0%
ext_buffers_pymem throughput (higher is better) 594,385 ops/s (592,992-595,778) 258,293 ops/s (257,662-258,924) -57%
side-buffer peak 127 MB (127-128) 323 MB (322-324) +153%
longest collection 0.74 ms (0.39-1.10) 14.1 ms (13.1-15.1) +1799%
peak RSS 194 MB (192-195) 469 MB (469-470) +143%
GC share 19.3% (19.3-19.4) 24.5% (24.3-24.7) +27%
py_globals throughput (higher is better) 285,087 ops/s (283,825-286,349) 244,817 ops/s (243,837-245,797) -14%
peak RSS 127 MB (127-127) 194 MB (194-194) +53%
longest collection 0.57 ms (0.53-0.61) 37.7 ms (37.7-37.8) +6484%
p99 collection 0.38 ms (0.38-0.38) 37.5 ms (37.5-37.6) +9869%
GC share 7.27% (7.27-7.27) 14.6% (14.6-14.6) +101%
web_service throughput (higher is better) 54,433 ops/s (54,363-54,502) 56,248 ops/s (56,081-56,414) +3.3%
peak RSS 374 MB (373-374) 516 MB (516-516) +38%
longest collection 279 ms (279-280) 227 ms (226-227) -19%
p99 collection 9.89 ms (9.86-9.92) 227 ms (226-227) +2191%
GC share 25.4% (25.4-25.4) 9.54% (9.53-9.56) -62%
orm_session mixed throughput (higher is better) 2,581 ops/s (2,576-2,586) 1,822 ops/s (1,818-1,825) -29%
peak RSS 87.3 MB (87.2-87.5) 147 MB (146-147) +68%
longest collection 7.81 ms (7.61-8.02) 20.6 ms (17.4-23.9) +164%
p99 collection 0.62 ms (0.62-0.62) 17.0 ms (16.7-17.2) +2632%
GC share 11.4% (11.4-11.4) 22.6% (22.4-22.7) +98%

Now, I’ll point out that the p99 collection time is not very useful when comparing FT against the GIL build (which is generational). There are typically hundreds of young collections per full collection in the GIL build so its p99 merely measures its young collections… But the other discrepancies do indicate some room for improvement, in particular the pause time (especially because every collection is a full one).

I will say these benchmarks have only been run on my development machine and it’s clear that some of the improvements and tweaks Claude came up with on its own are closely tied to that machine’s architecture. I suspect the same is true for some of the benchmarks, where they happen to sit in a sweet spot (for better or worse) because of my machine’s caches and CPU count.

Pause improvements

GitHub - Yhg1s/cpython at ftgc-pause-experiments · GitHub contains some experiments to reduce the pause in the FT GC (mostly written by Claude, and I can’t say I’m ready to merge them, especially the pretty invasive changes to mimalloc). Specifically:

  • Walk the heap once instead of three times, recording all visited objects in a new scratch space along the way, and skipping one traversal if nothing has finalizers or weakrefs.
  • Make mimalloc walk multiple heap freelists in lockstep to overlap cache misses, for memory-level parallelism.
  • When deallocating objects owned by other threads, do it in chunks to reduce the amount of synchronization that needs to happen.
  • Optionally trim the heaps/QSBR for all threads while the world is stopped, instead of waiting for threads to do it themselves on their next allocation.
  • Distribute deallocation of trash to other threads, triggered by them trying to allocate new objects. This avoids the problem of a multi-threaded workload with threads that allocate faster than the collecting thread can deallocate.

The changes move all of the benchmarks a bit, with some pretty significant changes in longest pause but also using more memory because of the scratch space used for trash. I’ve left out results that are not statistically significant. I wouldn’t call it a clear win except for a few pathological cases:

benchmark result free-threaded main pause fixes
gen_frag sparse run time 1.51 s 1.32 s (-13%)
final RSS 65.7 MB 69.0 MB (+5.1%)
longest collection 18.5 ms 15.3 ms (-17%)
doctree run time 5.54 s 5.44 s (-1.7%)
peak RSS 1,227 MB 1,336 MB (+8.9%)
longest collection 367 ms 342 ms (-6.8%)
event_widgets runaway peak RSS 2,778 MB 176 MB (-94%)
longest collection 2,148 ms 35.3 ms (-98%)
web_service 4t throughput (higher is better) 152k ops/s 162k ops/s (+6.3%)
peak RSS 549 MB 652 MB (+19%)
longest collection 292 ms 206 ms (-30%)
web_service 8t throughput (higher is better) 244k ops/s 269k ops/s (+10%)
peak RSS 619 MB 800 MB (+29%)
longest collection 357 ms 216 ms (-39%)

Docs build:

result free-threaded main pause fixes
time 54.4 s 53.4 s (-1.9%)
GC share 12.0% 10.7% (-10%)
p99 collection 598 ms 613 ms (+2.4%)
longest collection 1,137 ms 1,177 ms (+3.5%)
peak RSS 1,092 MB 1,175 MB (+7.6%)

Pyperformance:

benchmark free-threaded main pause fixes
async_tree_io 452 ms 440 ms (-2.8%)
async_tree_memoization 300 ms 276 ms (-7.8%)
async_tree_none 232 ms 225 ms (-3.2%)
django_template 23.8 ms 23.7 ms (-0.4%)
docutils 1,761 ms 1,663 ms (-5.5%)
networkx_connected_components 475 ms 482 ms (+1.5%)
networkx_k_core 2,054 ms 2,088 ms (+1.6%)
networkx_shortest_path 487 ms 500 ms (+2.8%)
sphinx 666 ms 643 ms (-3.5%)
sqlalchemy_declarative 87.0 ms 85.9 ms (-1.2%)
sqlalchemy_imperative 11.9 ms 11.7 ms (-1.8%)
xdsl_constant_fold 31.2 ms 29.8 ms (-4.5%)

Generational FT GC

The purpose of all this was to start looking at ways of doing generational GC for free-threading, under the assumption that the weak generational hypothesis still holds… which may actually not be the case for all workloads, because in CPython we use refcounting for a lot of the trash. It does hold for some of the GC benchmarks, but not all of them.

GitHub - Yhg1s/cpython at ftgc-combined · GitHub is my attempt at a generational design. (GitHub - Yhg1s/cpython at ftgc-gen-objage · GitHub is just the generational design without the pause fixes mentioned above.)

It involves having separate heaps for young objects, and doing a quick, partial collection over the young heaps without resolving buffered refcounts or references from outside the heaps. Pages from the young heaps that were scanned twice would then migrate to old heaps, which are only scanned on full collections. That worked pretty well for most benchmarks but did fragment memory quite a bit (which is usually reflected in higher RSS). To reduce fragmentation I added demotion of an old page back to a young heap once it’s sufficiently empty, and ran some experiments to find the right promotion/demotion values (80% for promotion and 50% for demotion seems pretty reliable), but that did mean scanning old objects a lot more often. Eventually I gave in and used an ob_gc_bit to indicate old objects, so the scan can skip them quickly.

It still uses more memory than main, and has more memory fragmentation, but for many cases that quick young collection really pays off. Unfortunately there are (of course) new pathological cases, like the deque benchmark, which keeps a bunch of cycles alive just long enough to become old. The young/full collection ratio is also very different from the GIL generational GC, depending on the workload, which shows in p99 times:

benchmark result pause fixes generational
gen_frag sparse run time 1.32 s 0.72 s (-45%)
final RSS 69.0 MB 65.7 MB (-4.8%)
longest collection 15.3 ms 13.3 ms (-13%)
p99 collection 14.5 ms 6.9 ms (-53%)
doctree run time 5.44 s 5.21 s (-4.4%)
peak RSS 1,336 MB 1,236 MB (-7.5%)
longest collection 342 ms 273 ms (-20%)
p99 collection 342 ms 215 ms (-37%)
migrations run time 6.13 s 5.67 s (-7.4%)
peak RSS 350 MB 373 MB (+6.4%)
longest collection 116 ms 165 ms (+43%)
p99 collection 115 ms 165 ms (+44%)
deque peak RSS 113 MB 175 MB (+55%)
p99 collection 1.4 ms 2.7 ms (+96%)
ext_buffers_pymem throughput (higher is better) 237k ops/s 273k ops/s (+15%)
side-buffer peak 323 MB 318 MB (-1.3%)
longest collection 17.0 ms 3.9 ms (-77%)
p99 collection 11.1 ms 1.8 ms (-84%)
hidden_refs throughput (higher is better) 372k ops/s 1,071k ops/s (+188%)
peak RSS 458 MB 369 MB (-19%)
longest collection 155 ms 102 ms (-34%)
p99 collection 143 ms 2.1 ms (-99%)
py_globals peak RSS 201 MB 189 MB (-5.8%)
p99 collection 34.5 ms 3.3 ms (-90%)
event_widgets runaway throughput (higher is better) 25k ops/s 35k ops/s (+43%)
peak RSS 176 MB 134 MB (-24%)
longest collection 35.3 ms 29.5 ms (-17%)
p99 collection 32.6 ms 6.7 ms (-79%)
web_service 4t throughput (higher is better) 162k ops/s 155k ops/s (-4.2%)
peak RSS 652 MB 507 MB (-22%)
longest collection 206 ms 167 ms (-19%)
p99 collection 199 ms 164 ms (-18%)
web_service 8t throughput (higher is better) 269k ops/s 254k ops/s (-5.4%)
peak RSS 800 MB 558 MB (-30%)
longest collection 216 ms 161 ms (-25%)
p99 collection 206 ms 160 ms (-22%)

Docs build:

result pause fixes generational
time 53.4 s 51.6 s (-3.4%)
GC share 10.7% 7.0% (-34%)
p99 collection 613 ms 73.5 ms (-88%)
longest collection 1,177 ms 736 ms (-37%)
peak RSS 1,175 MB 1,106 MB (-5.9%)

Pyperformance:

benchmark pause fixes generational
async_tree_io 440 ms 385 ms (-12%)
async_tree_memoization 276 ms 232 ms (-16%)
async_tree_none 225 ms 190 ms (-16%)
docutils 1,663 ms 1,563 ms (-6.0%)
networkx_connected_components 482 ms 486 ms (+0.8%)
networkx_k_core 2,088 ms 2,151 ms (+3.0%)
networkx_shortest_path 500 ms 507 ms (+1.4%)
sphinx 643 ms 623 ms (-3.0%)
sqlalchemy_declarative 85.9 ms 86.6 ms (+0.7%)
sqlalchemy_imperative 11.7 ms 11.4 ms (-2.5%)
xdsl_constant_fold 29.8 ms 28.5 ms (-4.2%)

This seems like a much clearer win, although there are certainly pathological cases we have to be careful of.

Parallel GC

Since I was experimenting anyway, I decided to try another approach: parallel GC, but not the way CinderX does it. Instead of starting new threads to help with scanning the heap, use threads we already have that are currently blocked in stop-the-world. This started as an experiment to see if I could have each thread do a non-STW scan of its own stack and heaps similar to a young generation scan, but that turned out to be impossible. There are too many cases where other threads can (and do) access a thread’s objects, so a thread can’t use its normal scratch spaces (like ob_tid) for the non-STW scan. I explored a few other approaches until I ended up re-inventing parallel GC, with dedicated helper threads and/or re-using existing threads. This is without the generational GC.

GitHub - Yhg1s/cpython at ftgc-coop · GitHub contains that work (even more vibe-coded than the other changes, I’ve barely reviewed it at this point). It can use dedicated helper threads (which borrow the collecting thread’s PyThreadState, which I do not think is safe), or use any threads blocked in STW (which I think is safe). Objects that need special handling (like generators and objects with deferred refcounts) are passed back to the collecting thread. Once trash is collected, the deallocation is distributed similarly to the pause improvements above.

With cooperative collection (not starting new threads), you only see the benefit when running multi-threaded benchmarks:

benchmark result pause fixes cooperative
event_widgets runaway throughput (higher is better) 25k ops/s 37k ops/s (+51%)
peak RSS 176 MB 154 MB (-12%)
longest collection 35.3 ms 26.5 ms (-25%)
p99 collection 32.6 ms 23.2 ms (-29%)
web_service 4t throughput (higher is better) 162k ops/s 173k ops/s (+7.0%)
peak RSS 652 MB 594 MB (-8.9%)
longest collection 206 ms 172 ms (-17%)
p99 collection 199 ms 161 ms (-19%)
web_service 8t throughput (higher is better) 269k ops/s 302k ops/s (+12%)
peak RSS 800 MB 650 MB (-19%)
longest collection 216 ms 158 ms (-27%)
p99 collection 206 ms 157 ms (-24%)
orm_session mixed 4t throughput (higher is better) 4.4k ops/s 5.0k ops/s (+14%)
peak RSS 171 MB 157 MB (-8.6%)
longest collection 32.6 ms 19.7 ms (-40%)
p99 collection 23.9 ms 18.6 ms (-22%)

With 4 dedicated helper threads (which, again, I don’t believe is safe as currently implemented, but which is more or less what CinderX does for collection), the benefits are pretty clear:

benchmark result pause fixes threads=4
gen_frag sparse run time 1.31 s 1.15 s (-12%)
final RSS 68.7 MB 66.0 MB (-3.9%)
longest collection 15.0 ms 11.7 ms (-22%)
p99 collection 14.4 ms 11.2 ms (-22%)
doctree run time 5.77 s 5.08 s (-12%)
peak RSS 1,328 MB 1,350 MB (+1.6%)
longest collection 368 ms 200 ms (-46%)
p99 collection 368 ms 200 ms (-46%)
migrations run time 6.25 s 5.22 s (-17%)
peak RSS 347 MB 341 MB (-1.7%)
longest collection 120 ms 89.5 ms (-26%)
p99 collection 118 ms 89.2 ms (-24%)
deque run time 1.65 s 1.59 s (-4.0%)
ext_buffers_pymem throughput (higher is better) 236k ops/s 255k ops/s (+8.0%)
longest collection 11.9 ms 8.6 ms (-27%)
p99 collection 11.2 ms 7.8 ms (-31%)
hidden_refs throughput (higher is better) 370k ops/s 534k ops/s (+45%)
longest collection 151 ms 77.0 ms (-49%)
p99 collection 146 ms 74.8 ms (-49%)
py_globals throughput (higher is better) 212k ops/s 223k ops/s (+5.0%)
longest collection 34.8 ms 24.5 ms (-30%)
p99 collection 34.5 ms 24.2 ms (-30%)
event_widgets runaway throughput (higher is better) 25k ops/s 38k ops/s (+54%)
peak RSS 175 MB 161 MB (-8.1%)
longest collection 33.2 ms 25.6 ms (-23%)
p99 collection 32.3 ms 22.1 ms (-32%)
web_service 4t throughput (higher is better) 160k ops/s 172k ops/s (+7.4%)
peak RSS 627 MB 588 MB (-6.3%)
p99 collection 206 ms 161 ms (-22%)
web_service 8t throughput (higher is better) 263k ops/s 297k ops/s (+13%)
peak RSS 760 MB 652 MB (-14%)
longest collection 214 ms 171 ms (-20%)
p99 collection 210 ms 166 ms (-21%)
orm_session mixed 4t throughput (higher is better) 4.4k ops/s 5.0k ops/s (+14%)
peak RSS 168 MB 159 MB (-5.5%)
p99 collection 23.3 ms 18.4 ms (-21%)

Docs build:

result pause fixes threads=4
time 54.4 s 52.9 s (-2.7%)
GC share 10.8% 8.7% (-20%)
p99 collection 633 ms 543 ms (-14%)
longest collection 1,205 ms 999 ms (-17%)
peak RSS 1,171 MB 1,196 MB (+2.1%)

Pyperformance:

benchmark pause fixes threads=4
async_tree_io 441 ms 421 ms (-4.7%)
async_tree_memoization 275 ms 264 ms (-3.8%)
async_tree_none 224 ms 213 ms (-5.2%)
docutils 1,661 ms 1,634 ms (-1.7%)
networkx_connected_components 483 ms 484 ms (+0.3%)
networkx_k_core 2,079 ms 2,091 ms (+0.6%)
sphinx 642 ms 619 ms (-3.6%)
sqlalchemy_declarative 86.0 ms 85.8 ms (-0.2%)
xdsl_constant_fold 29.9 ms 30.2 ms (+1.1%)

Going forward

The conclusions I’ve drawn from these numbers are that there’s quite a bit of headroom for GC improvements, but also that they’re quite situational. We need better benchmarks for GC (the code Claude wrote is… yikes) and representative workloads, but I also think we may need actual tunable GC, as the right approach is just different for different types of workloads/problems. I don’t think we need many knobs, but we need some signal from users (or the system) to tell us if we should expect a lot of circular reference trash or if we should try to collect more (or less) aggressively. I also think we should consider using parallel GC for programs that are already using threads, and for single-threaded programs that have a large heap (on systems with multiple cores). That is going to be a bit of a shift for users, I think.

I intend to spend some time trying to clean up the benchmarks, get them in a better state, and find more representative workloads, and then see if I can get any of these approaches to a reviewable state. I uuh, may have a few months to waste on that :stuck_out_tongue:


  1. ↩︎

12 Likes

There are a series of GC improvements from OpenAI fork these days. And now there are 8 PR in draft. We can also follow them
See Avoid redundant garbage collector traversals · Issue #159437 · python/cpython · GitHub