Partially apply mark-first-gc patch

python · markshannon · Dec 2, 2024 · Nov 19, 2024 · Nov 20, 2024 · Nov 21, 2024
commit ac3ad26ad9a1f9668c1a8921e56358eb3c616221
diff --git a/Include/cpython/pystats.h b/Include/cpython/pystats.h
@@ -99,6 +99,8 @@ typedef struct _gc_stats {
    uint64_t collections;
    uint64_t object_visits;
    uint64_t objects_collected;
+    uint64_t objects_transitively_reachable;
+    uint64_t objects_not_transitively_reachable;
 } GCStats;

 typedef struct _uop_stats {

diff --git a/Include/internal/pycore_frame.h b/Include/internal/pycore_frame.h
@@ -75,6 +75,7 @@ typedef struct _PyInterpreterFrame {
    _PyStackRef *stackpointer;
    uint16_t return_offset;  /* Only relevant during a function call */
    char owner;
+    char visited;
    /* Locals and stack */
    _PyStackRef localsplus[1];
 } _PyInterpreterFrame;
@@ -207,6 +208,7 @@ _PyFrame_Initialize(
 #endif
    frame->return_offset = 0;
    frame->owner = FRAME_OWNED_BY_THREAD;
+    frame->visited = 0;

    for (int i = null_locals_from; i < code->co_nlocalsplus; i++) {
        frame->localsplus[i] = PyStackRef_NULL;
@@ -389,6 +391,7 @@ _PyFrame_PushTrampolineUnchecked(PyThreadState *tstate, PyCodeObject *code, int
    frame->instr_ptr = _PyCode_CODE(code);
 #endif
    frame->owner = FRAME_OWNED_BY_THREAD;
+    frame->visited = 0;
    frame->return_offset = 0;

 #ifdef Py_GIL_DISABLED

diff --git a/Include/internal/pycore_gc.h b/Include/internal/pycore_gc.h
@@ -10,11 +10,11 @@ extern "C" {

 /* GC information is stored BEFORE the object structure. */
 typedef struct {
-    // Pointer to next object in the list.
+    // Tagged pointer to next object in the list.
    // 0 means the object is not tracked
    uintptr_t _gc_next;

-    // Pointer to previous object in the list.
+    // Tagged pointer to previous object in the list.
    // Lowest two bits are used for flags documented later.
    uintptr_t _gc_prev;
 } PyGC_Head;
@@ -302,6 +302,11 @@ struct gc_generation_stats {
    Py_ssize_t uncollectable;
 };

+enum _GCPhase {
+    GC_PHASE_MARK = 0,
+    GC_PHASE_COLLECT = 1
+};
+
 struct _gc_runtime_state {
    /* List of objects that still need to be cleaned up, singly linked
     * via their gc headers' gc_prev pointers.  */
@@ -329,6 +334,7 @@ struct _gc_runtime_state {
    Py_ssize_t work_to_do;
    /* Which of the old spaces is the visited space */
    int visited_space;
+    int phase;

 #ifdef Py_GIL_DISABLED
    /* This is the number of objects that survived the last full

@@ -137,6 +137,7 @@ extern PyTypeObject _PyExc_MemoryError;
                { .threshold = 0, }, \
            }, \
            .work_to_do = -5000, \
+            .phase = GC_PHASE_MARK, \
        }, \
        .qsbr = { \
            .wr_seq = QSBR_INITIAL, \

@@ -484,6 +484,45 @@ specifically in a generation by calling `gc.collect(generation=NUM)`.
 ```


+Optimization: visiting reachable objects
+========================================
+
+An object cannot be garbage if it can be reached.
+
+To avoid having to identify reference cycles across the whole heap, we can
+reduce the amount of work done considerably by first moving most reachable objects
+to the `visited` space. Empirically, most reachable objects can be reached from a
+small set of global objects and local variables.
+This step does much less work per object, so reduces the time spent
+performing garbage collection by at least half.
+
+> [!NOTE]
+> Objects that are not determined to be reachable by this pass are not necessarily
+> unreachable. We still need to perform the main algorithm to determine which objects
+> are actually unreachable.
+We use the same technique of forming a transitive closure as the incremental
+collector does to find reachable objects, seeding the list with some global
+objects and the currently executing frames.
+
+This phase moves objects to the `visited` space, as follows:
+
+1. All objects directly referred to by any builtin class, the `sys` module, the `builtins`
+module and all objects directly referred to from stack frames are added to a working
+set of reachable objects.
+2. Until this working set is empty:
+   1. Pop an object from the set and move it to the `visited` space
+   2. For each object directly reachable from that object:
+      * If it is not already in `visited` space and it is a GC object,
+        add it to the working set
+
+
+Before each increment of collection is performed, the stacks are scanned
+to check for any new stack frames that have been created since the last
+increment. All objects directly referred to from those stack frames are
+added to the working set.
+Then the above algorithm is repeated, starting from step 2.
+
+
 Optimization: reusing fields to save memory
 ===========================================


diff --git a/Lib/test/test_gc.py b/Lib/test/test_gc.py
@@ -31,6 +31,11 @@ def __new__(cls, *args, **kwargs):
        return C
    ContainerNoGC = None

+try:
+    import _testinternalcapi
+except ImportError:
+    _testinternalcapi = None
+
 ### Support code
 ###############################################################################

@@ -1130,6 +1135,7 @@ def setUp(self):
    def tearDown(self):
        gc.disable()

+    @unittest.skipIf(_testinternalcapi is None, "requires _testinternalcapi")
    @requires_gil_enabled("Free threading does not support incremental GC")
    # Use small increments to emulate longer running process in a shorter time
    @gc_threshold(200, 10)
@@ -1167,20 +1173,15 @@ def make_ll(depth):
        enabled = gc.isenabled()
        gc.enable()
        olds = []
+        initial_heap_size = _testinternalcapi.get_heap_size()
        for i in range(20_000):
            newhead = make_ll(20)
            count += 20
            newhead.surprise = head
            olds.append(newhead)
            if len(olds) == 20:
-                stats = gc.get_stats()
-                young = stats[0]
-                incremental = stats[1]
-                old = stats[2]
-                collected = young['collected'] + incremental['collected'] + old['collected']
-                count += CORRECTION
-                live = count - collected
-                self.assertLess(live, 25000)
+                new_objects = _testinternalcapi.get_heap_size() - initial_heap_size
+                self.assertLess(new_objects, 25_000)
                del olds[:]
        if not enabled:
            gc.disable()
@@ -1322,7 +1323,8 @@ def test_refcount_errors(self):
            from test.support import gc_collect, SuppressCrashReport

            a = [1, 2, 3]
-            b = [a]
+            b = [a, a]
+            a.append(b)

            # Avoid coredump when Py_FatalError() calls abort()
            SuppressCrashReport().__enter__()
@@ -1332,6 +1334,8 @@ def test_refcount_errors(self):
            # (to avoid deallocating it):
            import ctypes
            ctypes.pythonapi.Py_DecRef(ctypes.py_object(a))
+            del a
+            del b

            # The garbage collector should now have a fatal error
            # when it reaches the broken object
@@ -1360,7 +1364,7 @@ def test_refcount_errors(self):
        self.assertRegex(stderr,
            br'object type name: list')
        self.assertRegex(stderr,
-            br'object repr     : \[1, 2, 3\]')
+            br'object repr     : \[1, 2, 3, \[\[...\], \[...\]\]\]')


 class GCTogglingTests(unittest.TestCase):

diff --git a/Modules/_testinternalcapi.c b/Modules/_testinternalcapi.c
@@ -2076,6 +2076,11 @@ has_deferred_refcount(PyObject *self, PyObject *op)
    return PyBool_FromLong(_PyObject_HasDeferredRefcount(op));
 }

+static PyObject *
+get_heap_size(PyObject *self, PyObject *Py_UNUSED(ignored))
+{
+    return PyLong_FromInt64(PyInterpreterState_Get()->gc.heap_size);
+}

 static PyMethodDef module_functions[] = {
    {"get_configs", get_configs, METH_NOARGS},
@@ -2174,6 +2179,7 @@ static PyMethodDef module_functions[] = {
    {"get_static_builtin_types", get_static_builtin_types, METH_NOARGS},
    {"identify_type_slot_wrappers", identify_type_slot_wrappers, METH_NOARGS},
    {"has_deferred_refcount", has_deferred_refcount, METH_O},
+    {"get_heap_size", get_heap_size, METH_NOARGS},
    {NULL, NULL} /* sentinel */
 };