Incremental GC does not collect garbage as soon as expected

[nascheme]

Bug report

Bug description:

This was found by @Yhg1s . If you run tests with this command:

./python -m test --randseed=3169227856 --no-randomize --single-process test_pyclbr test_trace test_pdb test_iter test_ordered_dict test_urllib2_localnet test_array test_generated_cases test_typing test_fnmatch test_tools test_descr test___all__ test_xml_dom_xmlbuilder test_nturl2path test_hmac test_pickle test_android test_ipaddress test_modulefinder test_interpreters test_zoneinfo test_runpy test_sqlite3 test_bdb test_zipfile test_crossinterp test_pulldom test_pkgutil test_re test_dbm_sqlite3 test_venv test_pyrepl test_xml_etree_c test_gc

The test_gc unit test fails with:

  File "/home/thomas/python/python/main/Lib/contextlib.py", line 85, in inner
    return func(*args, **kwds)
  File "/home/thomas/python/python/main/Lib/test/test_gc.py", line 1573, in test_bug1055820d
    self.fail("gc didn't happen after 50000 iterations")
    ~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError: gc didn't happen after 50000 iterations

Reverting GH-140262 seems to fix this. It is possible this is related to GH-141890 as well.

CPython versions tested on:

CPython main branch

Operating systems tested on:

Linux

Linked PRs

• GH-142002: Revert GC changes to "work_to_do" logic. #142001

[markshannon]

What is "expected" in this case?
Since the test in question produces no cycles, an optimal cycle collector would always fail this test regardless of how large we set the threshold.

It is the test that is broken here.
We should either increase the threshold or, better still, change the test to produce cycles.

[nascheme]

What is "expected" in this case? Since the test in question produces no cycles, an optimal cycle collector would always fail this test regardless of how large we set the threshold.

It is the test that is broken here. We should either increase the threshold or, better still, change the test to produce cycles.

The test creates 50,000 new list objects. Are you saying the GC somehow knows these are not reference cycles without running? Changing the test to create lists that reference themselves (and be cycles) would fail in the same way. This is a strange argument in how the test is broken to my mind.

[sergey-miryanov]

This test, and I believe other tests that rely on the GC_Detector, depends heavily on the size of the global roots.

For incremental GC, there are two phases: MARK and COLLECT.

In this test, we call gc.collect before the loop, it runs completed_scavenge, sets the work_to_do value to zero and switchs GC to the MARK phase. In the loop the garbage collection runs when we create 2000 objects in the young generation. Then, we go to the MARK phase. In this phase, we mark all live roots and adjust value of the work_to_do, which becomes negative (I suppose a large negative). Then we switch phase to the COLLECT and stop this collection iteration. Afterwards, we repeatedly create objects in the young generation. This leads to GC runs. We check the work_to_do value, which is still negative, so we return early from GC. It seems that we cannot reach a positive work_to_do value in 50_000 iterations, and the test fails.