Incremental cycle GC

[markshannon]

The current GC is both inefficient and can have very long pause times.
The efficiency can be improved by tweaking thresholds or by using fewer generations (see #100403), but that does nothing to shorten pause times.

We should use an incremental collector, it can improve efficiency and hugely reduce maximum pause times.

See #100403 for more details on the general idea and the algorithm.

Linked PRs

• GH-108362: Incremental GC implementation #108038
• GH-108362: Set old space for objects in finalizer list before adding to old space #115084
• GH-108362: Revert "GH-108362: Incremental GC implementation (GH-108038)" #115132
• GH-108362: Incremental GC implementation #116199
• GH-108362: Incremental GC implementation #116206
• gh-108362: Retarget incremental GC changes to 3.14 #125453

[encukou]

Several stable buildbots fail on the new assertion:

test_thread_safety (test.test_multiprocessing_forkserver.test_processes.WithProcessesTestFinalize.test_thread_safety) ... Assertion failed: (gc_list_is_empty(to) || gc_old_space(to_tail) == gc_old_space(from_tail)), function gc_list_merge, file gc.c, line 320.
Fatal Python error: Aborted
Current thread 0x0000000170977000 (most recent call first):
  Garbage-collecting
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/multiprocessing/util.py", line 189 in __init__
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/test/_test_multiprocessing.py", line 4595 in __init__
  File "__init__", line ??? in __init__
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/test/_test_multiprocessing.py", line 4618 in make_finalizers
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/threading.py", line 1026 in run
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/threading.py", line 1089 in _bootstrap_inner
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/threading.py", line 1046 in _bootstrap
Thread 0x000000016f96b000 (most recent call first):
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/multiprocessing/util.py", line 214 in __call__
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/multiprocessing/util.py", line 296 in _run_finalizers
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/test/_test_multiprocessing.py", line 4607 in run_finalizers
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/threading.py", line 1026 in run
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/threading.py", line 1089 in _bootstrap_inner
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/threading.py", line 1046 in _bootstrap
Thread 0x00000001e2c35ec0 (most recent call first):
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/test/_test_multiprocessing.py", line 4631 in test_thread_safety
  File "/Users/buildbot/buildarea/3.x.pablogsal-macos-m1.macos-with-brew/build/Lib/unittest/case.py", line 589 in _callTestMethod
  ...

Do you have a quick fix that can be added today? If not, please revert first and then investigate.
(I can help, but not today.)

[markshannon]

I'll take a look. I can't reproduce the failure locally and it will be tricky to diagnose without a C backtrace.

[markshannon]

@encukou
I can't fix it now.
I'll do a revert PR tomorrow, unless you beat me to it.

[encukou]

Thank you for the revert.

The bigmem buildbot also failed on the change. For next PR fix, please run the bigmem tests (./python -m test test_bigmem -v -M 20G or however much RAM you can spare) and/or the bigmem buildbot.