Performance regression with cyclic GC vs 3.13

[nascheme]

Bug report

Bug description:

While working on the free-threaded GC, I noticed this performance regression with the default build GC. Running the attached script (bm_gc_collect.py) with the main branch of Python shows much worse performance vs 3.13. I get 20.8 seconds for the main branch and 3.3 seconds for 3.13. Adding gc.disable() before calling benchmark_collection() seems to fix it.

bm_gc_collect.py.txt

CPython versions tested on:

CPython main branch

Operating systems tested on:

Linux

Linked PRs

• gh-129210: GC optimisations for case where no objects being collected have finalizers #132488

[markshannon]

With a default build (.configure -C) I get the following:

Version	Fastest of 10
3.13	3.9s
Main	4.7s

Definitely slower, but not the dramatic slowdown you are seeing.

[nascheme]

Try removing the gc.disable() line on the first line inside benchmark_collection(). That makes "main" a lot slower for me.

[duaneg]

I tried to bisect this, which was a bit messy, but the upshot is that the slow-down is caused by the introduction of the incremental GC. In my environment the test script runs ~3x slower overall (with gc enabled).

The script's reported time is for the manual collection after creation & unreferencing of the cycle, elapsed time is the overall runtime of the script. Profiling confirms the script is dominated by gc. The script is creating many objects that cannot be immediately GCed, scheduling a bunch of fruitless young generation/incremental collections. If we increase the generation 0 gc threshold to CYCLES * 1.2 (rows labelled "ht" below) that eliminates most of the scheduled collections and leaves just the manually triggered full collections:

Version	total reported time (s)	elapsed time (s)	collections (0)	collections (1)	collections (2)
v3.13.0	2.35	9.39	9353	845	55
v3.13.0 (ht)	2.33	5.95	163	10	10
main	21.4	34.6	0	10161	10
main (ht)	8.70	12.5	0	161	10
optimised	12.1	25.3	0	10161	10
optimised (ht)	4.99	8.67	0	161	10

Note avoiding the scheduled collections gives a ~35% speed improvement in v3.13.0, but the full manual collection time is unaffected. However, in main, increasing the youngest generation threshold not only avoids wasting time on incremental collections that cannot collect anything, it also seems to drastically improve the reported full collection time! I'm not sure what is going on there, but it seems unexpected and potentially worth digging into.

This microbenchmark is unlikely to reflect real-world workloads, which probably won't be dominated by gc, and probably will have collectable objects if/when they are. Having said that, obviously speeding up gc is very worthwhile, and even relatively small performance improvements will add up to significant saved CPU time globally. Looking at the code there does seem to be some relatively easy optimisations (results labelled "optimised" in the table above):

• After finalizers are run the gc needs to recompute reachability for collection candidates, as they may have been resurrected. Unless I'm missing something (quite likely!) this can be skipped if there were no finalizers, since then no objects could have been resurrected. This gives a ~25% speed improvement in my testing compared to baseline.
• The count of collected items is added to statistics by getting the size of the list, which ofc requires a traversal. If no objects could have been resurrected we can track the unreachable count as a free side-effect of previous operations, avoiding the extra traversal. This gives an additional ~5% speed improvement on top of the above.

If those optimisations sound useful, let me know, and I'll open a PR.

[nascheme]

However, in main, increasing the youngest generation threshold not only avoids wasting time on incremental collections that cannot collect anything, it also seems to drastically improve the reported full collection time! I'm not sure what is going on there, but it seems unexpected and potentially worth digging into.

It's only a guess but I think the problem could be due to "shuffling" of the GC linked list. That would explain why doing gc.disable() while creating the object graph makes the full collection so much faster. As you create objects, they get linked into the GC generation double linked list in the order they are created.

When you later traverse those lists, the hardware prefetch should work well since you are essentially iterating over memory locations in order. If you let small incremental collections happen, I think the order of objects in the linked list are shuffled. However, it's surprising to me that the slowdown from that could be so big. So maybe this theory is wrong.

The fix could be as simple as adding objects to the tail of the list or to the head after the incremental collection is done. When you are creating a bunch of objects and have small incremental collections as you create them, ideally (if it's not too hard to do) the old generation GC linked list should be ordered by object creation time.

[nascheme]

• After finalizers are run the gc needs to recompute reachability for collection candidates, as they may have been resurrected. Unless I'm missing something (quite likely!) this can be skipped if there were no finalizers, since then no objects could have been resurrected. This gives a ~25% speed improvement in my testing compared to baseline.
• The count of collected items is added to statistics by getting the size of the list, which ofc requires a traversal. If no objects could have been resurrected we can track the unreachable count as a free side-effect of previous operations, avoiding the extra traversal. This gives an additional ~5% speed improvement on top of the above.

If those optimisations sound useful, let me know, and I'll open a PR.

Those both sound worth doing to me, assuming they don't add too much code complexity.

[duaneg]

I had overlooked the case where running finalizers dec-refed-to-zero and hence removed objects from the unreachable list. Given that possibility it doesn't seem feasible to track the unreachable count reliably, so I'll drop that second commit.