From a8dd821d5b25b42c0adeae6642e9b3f9228580f9 Mon Sep 17 00:00:00 2001 From: Mark Shannon Date: Mon, 2 Dec 2024 10:12:17 +0000 Subject: GH-126491: GC: Mark objects reachable from roots before doing cycle collection (GH-127110) * Mark almost all reachable objects before doing collection phase * Add stats for objects marked * Visit new frames before each increment * Update docs * Clearer calculation of work to do. --- Include/cpython/pystats.h | 2 + Include/internal/pycore_frame.h | 3 + Include/internal/pycore_gc.h | 10 +- Include/internal/pycore_object.h | 4 +- Include/internal/pycore_runtime_init.h | 1 + InternalDocs/garbage_collector.md | 39 +++ Lib/test/libregrtest/refleak.py | 2 +- Lib/test/test_gc.py | 24 +- .../2024-11-21-16-13-52.gh-issue-126491.0YvL94.rst | 4 + Modules/_testinternalcapi.c | 6 + Python/ceval.c | 1 + Python/gc.c | 355 ++++++++++++++++----- Python/specialize.c | 2 + Tools/scripts/summarize_stats.py | 5 +- 14 files changed, 355 insertions(+), 103 deletions(-) create mode 100644 Misc/NEWS.d/next/Core_and_Builtins/2024-11-21-16-13-52.gh-issue-126491.0YvL94.rst diff --git a/Include/cpython/pystats.h b/Include/cpython/pystats.h index f1ca548..2ae4800 100644 --- 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 index 8c01003..b786c5f 100644 --- 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 index 479fe10..4ff34bf 100644 --- 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; @@ -284,6 +284,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. */ @@ -311,6 +316,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 diff --git a/Include/internal/pycore_object.h b/Include/internal/pycore_object.h index 34d835a..c52ed8f 100644 --- a/Include/internal/pycore_object.h +++ b/Include/internal/pycore_object.h @@ -471,8 +471,8 @@ static inline void _PyObject_GC_TRACK( PyGC_Head *last = (PyGC_Head*)(generation0->_gc_prev); _PyGCHead_SET_NEXT(last, gc); _PyGCHead_SET_PREV(gc, last); - /* Young objects will be moved into the visited space during GC, so set the bit here */ - gc->_gc_next = ((uintptr_t)generation0) | (uintptr_t)interp->gc.visited_space; + uintptr_t not_visited = 1 ^ interp->gc.visited_space; + gc->_gc_next = ((uintptr_t)generation0) | not_visited; generation0->_gc_prev = (uintptr_t)gc; #endif } diff --git a/Include/internal/pycore_runtime_init.h b/Include/internal/pycore_runtime_init.h index 9f67489..1260b95 100644 --- a/Include/internal/pycore_runtime_init.h +++ b/Include/internal/pycore_runtime_init.h @@ -137,6 +137,7 @@ extern PyTypeObject _PyExc_MemoryError; { .threshold = 0, }, \ }, \ .work_to_do = -5000, \ + .phase = GC_PHASE_MARK, \ }, \ .qsbr = { \ .wr_seq = QSBR_INITIAL, \ diff --git a/InternalDocs/garbage_collector.md b/InternalDocs/garbage_collector.md index 9e01a58..08db080 100644 --- a/InternalDocs/garbage_collector.md +++ b/InternalDocs/garbage_collector.md @@ -477,6 +477,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/libregrtest/refleak.py b/Lib/test/libregrtest/refleak.py index e783475..d0d1c8c 100644 --- a/Lib/test/libregrtest/refleak.py +++ b/Lib/test/libregrtest/refleak.py @@ -123,9 +123,9 @@ def runtest_refleak(test_name, test_func, xml_filename = 'refleak-xml.tmp' result = None dash_R_cleanup(fs, ps, pic, zdc, abcs) - support.gc_collect() for i in rep_range: + support.gc_collect() current = refleak_helper._hunting_for_refleaks refleak_helper._hunting_for_refleaks = True try: diff --git a/Lib/test/test_gc.py b/Lib/test/test_gc.py index 0372815..b514005 100644 --- a/Lib/test/test_gc.py +++ b/Lib/test/test_gc.py @@ -31,6 +31,11 @@ except ImportError: return C ContainerNoGC = None +try: + import _testinternalcapi +except ImportError: + _testinternalcapi = None + ### Support code ############################################################################### @@ -1130,6 +1135,7 @@ class IncrementalGCTests(unittest.TestCase): 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 @@ class IncrementalGCTests(unittest.TestCase): enabled = gc.isenabled() gc.enable() olds = [] + initial_heap_size = _testinternalcapi.get_tracked_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_tracked_heap_size() - initial_heap_size + self.assertLess(new_objects, 27_000, f"Heap growing. Reached limit after {i} iterations") del olds[:] if not enabled: gc.disable() @@ -1322,7 +1323,8 @@ class GCCallbackTests(unittest.TestCase): 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 @@ class GCCallbackTests(unittest.TestCase): # (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 @@ class GCCallbackTests(unittest.TestCase): 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/Misc/NEWS.d/next/Core_and_Builtins/2024-11-21-16-13-52.gh-issue-126491.0YvL94.rst b/Misc/NEWS.d/next/Core_and_Builtins/2024-11-21-16-13-52.gh-issue-126491.0YvL94.rst new file mode 100644 index 0000000..9ef2b8d --- /dev/null +++ b/Misc/NEWS.d/next/Core_and_Builtins/2024-11-21-16-13-52.gh-issue-126491.0YvL94.rst @@ -0,0 +1,4 @@ +Add a marking phase to the GC. All objects that can be transitively reached +from builtin modules or the stacks are marked as reachable before cycle +detection. This reduces the amount of work done by the GC by approximately +half. diff --git a/Modules/_testinternalcapi.c b/Modules/_testinternalcapi.c index a925191..1bb71a3 100644 --- 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_tracked_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_tracked_heap_size", get_tracked_heap_size, METH_NOARGS}, {NULL, NULL} /* sentinel */ }; diff --git a/Python/ceval.c b/Python/ceval.c index eba0f23..f9514a6 100644 --- a/Python/ceval.c +++ b/Python/ceval.c @@ -818,6 +818,7 @@ _PyEval_EvalFrameDefault(PyThreadState *tstate, _PyInterpreterFrame *frame, int entry_frame.instr_ptr = (_Py_CODEUNIT *)_Py_INTERPRETER_TRAMPOLINE_INSTRUCTIONS + 1; entry_frame.stackpointer = entry_frame.localsplus; entry_frame.owner = FRAME_OWNED_BY_CSTACK; + entry_frame.visited = 0; entry_frame.return_offset = 0; /* Push frame */ entry_frame.previous = tstate->current_frame; diff --git a/Python/gc.c b/Python/gc.c index 63adecf..5b9588c 100644 --- a/Python/gc.c +++ b/Python/gc.c @@ -106,7 +106,7 @@ gc_old_space(PyGC_Head *g) } static inline int -flip_old_space(int space) +other_space(int space) { assert(space == 0 || space == 1); return space ^ _PyGC_NEXT_MASK_OLD_SPACE_1; @@ -430,24 +430,32 @@ validate_list(PyGC_Head *head, enum flagstates flags) #endif #ifdef GC_EXTRA_DEBUG + + static void -validate_old(GCState *gcstate) +gc_list_validate_space(PyGC_Head *head, int space) { + PyGC_Head *gc = GC_NEXT(head); + while (gc != head) { + assert(gc_old_space(gc) == space); + gc = GC_NEXT(gc); + } +} + +static void +validate_spaces(GCState *gcstate) { + int visited = gcstate->visited_space; + int not_visited = other_space(visited); + gc_list_validate_space(&gcstate->young.head, not_visited); for (int space = 0; space < 2; space++) { - PyGC_Head *head = &gcstate->old[space].head; - PyGC_Head *gc = GC_NEXT(head); - while (gc != head) { - PyGC_Head *next = GC_NEXT(gc); - assert(gc_old_space(gc) == space); - gc = next; - } + gc_list_validate_space(&gcstate->old[space].head, space); } + gc_list_validate_space(&gcstate->permanent_generation.head, visited); } static void validate_consistent_old_space(PyGC_Head *head) { - PyGC_Head *prev = head; PyGC_Head *gc = GC_NEXT(head); if (gc == head) { return; @@ -457,23 +465,13 @@ validate_consistent_old_space(PyGC_Head *head) PyGC_Head *truenext = GC_NEXT(gc); assert(truenext != NULL); assert(gc_old_space(gc) == old_space); - prev = gc; gc = truenext; } - assert(prev == GC_PREV(head)); } -static void -gc_list_validate_space(PyGC_Head *head, int space) { - PyGC_Head *gc = GC_NEXT(head); - while (gc != head) { - assert(gc_old_space(gc) == space); - gc = GC_NEXT(gc); - } -} #else -#define validate_old(g) do{}while(0) +#define validate_spaces(g) do{}while(0) #define validate_consistent_old_space(l) do{}while(0) #define gc_list_validate_space(l, s) do{}while(0) #endif @@ -494,7 +492,7 @@ update_refs(PyGC_Head *containers) next = GC_NEXT(gc); PyObject *op = FROM_GC(gc); if (_Py_IsImmortal(op)) { - gc_list_move(gc, &get_gc_state()->permanent_generation.head); + _PyObject_GC_UNTRACK(op); gc = next; continue; } @@ -733,13 +731,25 @@ move_unreachable(PyGC_Head *young, PyGC_Head *unreachable) unreachable->_gc_next &= _PyGC_PREV_MASK; } +/* In theory, all tuples should be younger than the +* objects they refer to, as tuples are immortal. +* Therefore, untracking tuples in oldest-first order in the +* young generation before promoting them should have tracked +* all the tuples that can be untracked. +* +* Unfortunately, the C API allows tuples to be created +* and then filled in. So this won't untrack all tuples +* that can be untracked. It should untrack most of them +* and is much faster than a more complex approach that +* would untrack all relevant tuples. +*/ static void untrack_tuples(PyGC_Head *head) { - PyGC_Head *next, *gc = GC_NEXT(head); + PyGC_Head *gc = GC_NEXT(head); while (gc != head) { PyObject *op = FROM_GC(gc); - next = GC_NEXT(gc); + PyGC_Head *next = GC_NEXT(gc); if (PyTuple_CheckExact(op)) { _PyTuple_MaybeUntrack(op); } @@ -1293,8 +1303,10 @@ gc_collect_young(PyThreadState *tstate, struct gc_collection_stats *stats) { GCState *gcstate = &tstate->interp->gc; + validate_spaces(gcstate); PyGC_Head *young = &gcstate->young.head; PyGC_Head *visited = &gcstate->old[gcstate->visited_space].head; + untrack_tuples(young); GC_STAT_ADD(0, collections, 1); #ifdef Py_STATS { @@ -1308,39 +1320,21 @@ gc_collect_young(PyThreadState *tstate, PyGC_Head survivors; gc_list_init(&survivors); + gc_list_set_space(young, gcstate->visited_space); gc_collect_region(tstate, young, &survivors, stats); - Py_ssize_t survivor_count = 0; - if (gcstate->visited_space) { - /* objects in visited space have bit set, so we set it here */ - survivor_count = gc_list_set_space(&survivors, 1); - } - else { - PyGC_Head *gc; - for (gc = GC_NEXT(&survivors); gc != &survivors; gc = GC_NEXT(gc)) { -#ifdef GC_DEBUG - assert(gc_old_space(gc) == 0); -#endif - survivor_count++; - } - } - (void)survivor_count; // Silence compiler warning gc_list_merge(&survivors, visited); - validate_old(gcstate); + validate_spaces(gcstate); gcstate->young.count = 0; gcstate->old[gcstate->visited_space].count++; - Py_ssize_t scale_factor = gcstate->old[0].threshold; - if (scale_factor < 1) { - scale_factor = 1; - } - gcstate->work_to_do += gcstate->heap_size / SCAN_RATE_DIVISOR / scale_factor; add_stats(gcstate, 0, stats); + validate_spaces(gcstate); } #ifndef NDEBUG static inline int IS_IN_VISITED(PyGC_Head *gc, int visited_space) { - assert(visited_space == 0 || flip_old_space(visited_space) == 0); + assert(visited_space == 0 || other_space(visited_space) == 0); return gc_old_space(gc) == visited_space; } #endif @@ -1348,7 +1342,7 @@ IS_IN_VISITED(PyGC_Head *gc, int visited_space) struct container_and_flag { PyGC_Head *container; int visited_space; - uintptr_t size; + intptr_t size; }; /* A traversal callback for adding to container) */ @@ -1371,7 +1365,7 @@ visit_add_to_container(PyObject *op, void *arg) return 0; } -static uintptr_t +static intptr_t expand_region_transitively_reachable(PyGC_Head *container, PyGC_Head *gc, GCState *gcstate) { struct container_and_flag arg = { @@ -1385,6 +1379,7 @@ expand_region_transitively_reachable(PyGC_Head *container, PyGC_Head *gc, GCStat * have been marked as visited */ assert(IS_IN_VISITED(gc, gcstate->visited_space)); PyObject *op = FROM_GC(gc); + assert(_PyObject_GC_IS_TRACKED(op)); if (_Py_IsImmortal(op)) { PyGC_Head *next = GC_NEXT(gc); gc_list_move(gc, &get_gc_state()->permanent_generation.head); @@ -1402,22 +1397,191 @@ expand_region_transitively_reachable(PyGC_Head *container, PyGC_Head *gc, GCStat /* Do bookkeeping for a completed GC cycle */ static void -completed_cycle(GCState *gcstate) -{ -#ifdef Py_DEBUG - PyGC_Head *not_visited = &gcstate->old[gcstate->visited_space^1].head; - assert(gc_list_is_empty(not_visited)); -#endif - gcstate->visited_space = flip_old_space(gcstate->visited_space); - /* Make sure all young objects have old space bit set correctly */ - PyGC_Head *young = &gcstate->young.head; - PyGC_Head *gc = GC_NEXT(young); - while (gc != young) { - PyGC_Head *next = GC_NEXT(gc); - gc_set_old_space(gc, gcstate->visited_space); - gc = next; +completed_scavenge(GCState *gcstate) +{ + /* We must observe two invariants: + * 1. Members of the permanent generation must be marked visited. + * 2. We cannot touch members of the permanent generation. */ + int visited; + if (gc_list_is_empty(&gcstate->permanent_generation.head)) { + /* Permanent generation is empty so we can flip spaces bit */ + int not_visited = gcstate->visited_space; + visited = other_space(not_visited); + gcstate->visited_space = visited; + /* Make sure all objects have visited bit set correctly */ + gc_list_set_space(&gcstate->young.head, not_visited); } + else { + /* We must move the objects from visited to pending space. */ + visited = gcstate->visited_space; + int not_visited = other_space(visited); + assert(gc_list_is_empty(&gcstate->old[not_visited].head)); + gc_list_merge(&gcstate->old[visited].head, &gcstate->old[not_visited].head); + gc_list_set_space(&gcstate->old[not_visited].head, not_visited); + } + assert(gc_list_is_empty(&gcstate->old[visited].head)); gcstate->work_to_do = 0; + gcstate->phase = GC_PHASE_MARK; +} + +static intptr_t +move_to_reachable(PyObject *op, PyGC_Head *reachable, int visited_space) +{ + if (op != NULL && !_Py_IsImmortal(op) && _PyObject_IS_GC(op)) { + PyGC_Head *gc = AS_GC(op); + if (_PyObject_GC_IS_TRACKED(op) && + gc_old_space(gc) != visited_space) { + gc_flip_old_space(gc); + gc_list_move(gc, reachable); + return 1; + } + } + return 0; +} + +static intptr_t +mark_all_reachable(PyGC_Head *reachable, PyGC_Head *visited, int visited_space) +{ + // Transitively traverse all objects from reachable, until empty + struct container_and_flag arg = { + .container = reachable, + .visited_space = visited_space, + .size = 0 + }; + while (!gc_list_is_empty(reachable)) { + PyGC_Head *gc = _PyGCHead_NEXT(reachable); + assert(gc_old_space(gc) == visited_space); + gc_list_move(gc, visited); + PyObject *op = FROM_GC(gc); + traverseproc traverse = Py_TYPE(op)->tp_traverse; + (void) traverse(op, + visit_add_to_container, + &arg); + } + gc_list_validate_space(visited, visited_space); + return arg.size; +} + +static intptr_t +mark_stacks(PyInterpreterState *interp, PyGC_Head *visited, int visited_space, bool start) +{ + PyGC_Head reachable; + gc_list_init(&reachable); + Py_ssize_t objects_marked = 0; + // Move all objects on stacks to reachable + _PyRuntimeState *runtime = &_PyRuntime; + HEAD_LOCK(runtime); + PyThreadState* ts = PyInterpreterState_ThreadHead(interp); + HEAD_UNLOCK(runtime); + while (ts) { + _PyInterpreterFrame *frame = ts->current_frame; + while (frame) { + if (frame->owner == FRAME_OWNED_BY_CSTACK) { + frame = frame->previous; + continue; + } + _PyStackRef *locals = frame->localsplus; + _PyStackRef *sp = frame->stackpointer; + objects_marked += move_to_reachable(frame->f_locals, &reachable, visited_space); + PyObject *func = PyStackRef_AsPyObjectBorrow(frame->f_funcobj); + objects_marked += move_to_reachable(func, &reachable, visited_space); + while (sp > locals) { + sp--; + if (PyStackRef_IsNull(*sp)) { + continue; + } + PyObject *op = PyStackRef_AsPyObjectBorrow(*sp); + if (!_Py_IsImmortal(op) && _PyObject_IS_GC(op)) { + PyGC_Head *gc = AS_GC(op); + if (_PyObject_GC_IS_TRACKED(op) && + gc_old_space(gc) != visited_space) { + gc_flip_old_space(gc); + objects_marked++; + gc_list_move(gc, &reachable); + } + } + } + if (!start && frame->visited) { + // If this frame has already been visited, then the lower frames + // will have already been visited and will not have changed + break; + } + frame->visited = 1; + frame = frame->previous; + } + HEAD_LOCK(runtime); + ts = PyThreadState_Next(ts); + HEAD_UNLOCK(runtime); + } + objects_marked += mark_all_reachable(&reachable, visited, visited_space); + assert(gc_list_is_empty(&reachable)); + return objects_marked; +} + +static intptr_t +mark_global_roots(PyInterpreterState *interp, PyGC_Head *visited, int visited_space) +{ + PyGC_Head reachable; + gc_list_init(&reachable); + Py_ssize_t objects_marked = 0; + objects_marked += move_to_reachable(interp->sysdict, &reachable, visited_space); + objects_marked += move_to_reachable(interp->builtins, &reachable, visited_space); + objects_marked += move_to_reachable(interp->dict, &reachable, visited_space); + struct types_state *types = &interp->types; + for (int i = 0; i < _Py_MAX_MANAGED_STATIC_BUILTIN_TYPES; i++) { + objects_marked += move_to_reachable(types->builtins.initialized[i].tp_dict, &reachable, visited_space); + objects_marked += move_to_reachable(types->builtins.initialized[i].tp_subclasses, &reachable, visited_space); + } + for (int i = 0; i < _Py_MAX_MANAGED_STATIC_EXT_TYPES; i++) { + objects_marked += move_to_reachable(types->for_extensions.initialized[i].tp_dict, &reachable, visited_space); + objects_marked += move_to_reachable(types->for_extensions.initialized[i].tp_subclasses, &reachable, visited_space); + } + objects_marked += mark_all_reachable(&reachable, visited, visited_space); + assert(gc_list_is_empty(&reachable)); + return objects_marked; +} + +static intptr_t +mark_at_start(PyThreadState *tstate) +{ + // TO DO -- Make this incremental + GCState *gcstate = &tstate->interp->gc; + PyGC_Head *visited = &gcstate->old[gcstate->visited_space].head; + Py_ssize_t objects_marked = mark_global_roots(tstate->interp, visited, gcstate->visited_space); + objects_marked += mark_stacks(tstate->interp, visited, gcstate->visited_space, true); + gcstate->work_to_do -= objects_marked; + gcstate->phase = GC_PHASE_COLLECT; + validate_spaces(gcstate); + return objects_marked; +} + +static intptr_t +assess_work_to_do(GCState *gcstate) +{ + /* The amount of work we want to do depends on three things. + * 1. The number of new objects created + * 2. The growth in heap size since the last collection + * 3. The heap size (up to the number of new objects, to avoid quadratic effects) + * + * For a steady state heap, the amount of work to do is three times the number + * of new objects added to the heap. This ensures that we stay ahead in the + * worst case of all new objects being garbage. + * + * This could be improved by tracking survival rates, but it is still a + * large improvement on the non-marking approach. + */ + intptr_t scale_factor = gcstate->old[0].threshold; + if (scale_factor < 2) { + scale_factor = 2; + } + intptr_t new_objects = gcstate->young.count; + intptr_t max_heap_fraction = new_objects*3/2; + intptr_t heap_fraction = gcstate->heap_size / SCAN_RATE_DIVISOR / scale_factor; + if (heap_fraction > max_heap_fraction) { + heap_fraction = max_heap_fraction; + } + gcstate->young.count = 0; + return new_objects + heap_fraction; } static void @@ -1425,18 +1589,30 @@ gc_collect_increment(PyThreadState *tstate, struct gc_collection_stats *stats) { GC_STAT_ADD(1, collections, 1); GCState *gcstate = &tstate->interp->gc; + gcstate->work_to_do += assess_work_to_do(gcstate); + untrack_tuples(&gcstate->young.head); + if (gcstate->phase == GC_PHASE_MARK) { + Py_ssize_t objects_marked = mark_at_start(tstate); + GC_STAT_ADD(1, objects_transitively_reachable, objects_marked); + gcstate->work_to_do -= objects_marked; + validate_spaces(gcstate); + return; + } PyGC_Head *not_visited = &gcstate->old[gcstate->visited_space^1].head; PyGC_Head *visited = &gcstate->old[gcstate->visited_space].head; PyGC_Head increment; gc_list_init(&increment); - Py_ssize_t scale_factor = gcstate->old[0].threshold; - if (scale_factor < 1) { - scale_factor = 1; - } + int scale_factor = gcstate->old[0].threshold; + if (scale_factor < 2) { + scale_factor = 2; + } + intptr_t objects_marked = mark_stacks(tstate->interp, visited, gcstate->visited_space, false); + GC_STAT_ADD(1, objects_transitively_reachable, objects_marked); + gcstate->work_to_do -= objects_marked; + gc_list_set_space(&gcstate->young.head, gcstate->visited_space); gc_list_merge(&gcstate->young.head, &increment); - gcstate->young.count = 0; gc_list_validate_space(&increment, gcstate->visited_space); - Py_ssize_t increment_size = 0; + Py_ssize_t increment_size = gc_list_size(&increment); while (increment_size < gcstate->work_to_do) { if (gc_list_is_empty(not_visited)) { break; @@ -1444,54 +1620,56 @@ gc_collect_increment(PyThreadState *tstate, struct gc_collection_stats *stats) PyGC_Head *gc = _PyGCHead_NEXT(not_visited); gc_list_move(gc, &increment); increment_size++; + assert(!_Py_IsImmortal(FROM_GC(gc))); gc_set_old_space(gc, gcstate->visited_space); increment_size += expand_region_transitively_reachable(&increment, gc, gcstate); } + GC_STAT_ADD(1, objects_not_transitively_reachable, increment_size); validate_list(&increment, collecting_clear_unreachable_clear); gc_list_validate_space(&increment, gcstate->visited_space); PyGC_Head survivors; gc_list_init(&survivors); gc_collect_region(tstate, &increment, &survivors, stats); - gc_list_validate_space(&survivors, gcstate->visited_space); gc_list_merge(&survivors, visited); assert(gc_list_is_empty(&increment)); gcstate->work_to_do += gcstate->heap_size / SCAN_RATE_DIVISOR / scale_factor; gcstate->work_to_do -= increment_size; - validate_old(gcstate); add_stats(gcstate, 1, stats); if (gc_list_is_empty(not_visited)) { - completed_cycle(gcstate); + completed_scavenge(gcstate); } + validate_spaces(gcstate); } - static void gc_collect_full(PyThreadState *tstate, struct gc_collection_stats *stats) { GC_STAT_ADD(2, collections, 1); GCState *gcstate = &tstate->interp->gc; - validate_old(gcstate); + validate_spaces(gcstate); PyGC_Head *young = &gcstate->young.head; PyGC_Head *pending = &gcstate->old[gcstate->visited_space^1].head; PyGC_Head *visited = &gcstate->old[gcstate->visited_space].head; + untrack_tuples(young); /* merge all generations into visited */ - gc_list_validate_space(young, gcstate->visited_space); - gc_list_set_space(pending, gcstate->visited_space); gc_list_merge(young, pending); + gc_list_validate_space(pending, 1-gcstate->visited_space); + gc_list_set_space(pending, gcstate->visited_space); gcstate->young.count = 0; gc_list_merge(pending, visited); + validate_spaces(gcstate); gc_collect_region(tstate, visited, visited, stats); + validate_spaces(gcstate); gcstate->young.count = 0; gcstate->old[0].count = 0; gcstate->old[1].count = 0; - - gcstate->work_to_do = - gcstate->young.threshold * 2; + completed_scavenge(gcstate); _PyGC_ClearAllFreeLists(tstate->interp); - validate_old(gcstate); + validate_spaces(gcstate); add_stats(gcstate, 2, stats); } @@ -1733,20 +1911,23 @@ void _PyGC_Freeze(PyInterpreterState *interp) { GCState *gcstate = &interp->gc; - /* The permanent_generation has its old space bit set to zero */ - if (gcstate->visited_space) { - gc_list_set_space(&gcstate->young.head, 0); - } + /* The permanent_generation must be visited */ + gc_list_set_space(&gcstate->young.head, gcstate->visited_space); gc_list_merge(&gcstate->young.head, &gcstate->permanent_generation.head); gcstate->young.count = 0; PyGC_Head*old0 = &gcstate->old[0].head; PyGC_Head*old1 = &gcstate->old[1].head; + if (gcstate->visited_space) { + gc_list_set_space(old0, 1); + } + else { + gc_list_set_space(old1, 0); + } gc_list_merge(old0, &gcstate->permanent_generation.head); gcstate->old[0].count = 0; - gc_list_set_space(old1, 0); gc_list_merge(old1, &gcstate->permanent_generation.head); gcstate->old[1].count = 0; - validate_old(gcstate); + validate_spaces(gcstate); } void @@ -1754,8 +1935,8 @@ _PyGC_Unfreeze(PyInterpreterState *interp) { GCState *gcstate = &interp->gc; gc_list_merge(&gcstate->permanent_generation.head, - &gcstate->old[0].head); - validate_old(gcstate); + &gcstate->old[gcstate->visited_space].head); + validate_spaces(gcstate); } Py_ssize_t @@ -1860,7 +2041,7 @@ _PyGC_Collect(PyThreadState *tstate, int generation, _PyGC_Reason reason) _Py_stats->object_stats.object_visits = 0; } #endif - validate_old(gcstate); + validate_spaces(gcstate); _Py_atomic_store_int(&gcstate->collecting, 0); return stats.uncollectable + stats.collected; } diff --git a/Python/specialize.c b/Python/specialize.c index d03310d..504eef4 100644 --- a/Python/specialize.c +++ b/Python/specialize.c @@ -231,6 +231,8 @@ print_gc_stats(FILE *out, GCStats *stats) fprintf(out, "GC[%d] collections: %" PRIu64 "\n", i, stats[i].collections); fprintf(out, "GC[%d] object visits: %" PRIu64 "\n", i, stats[i].object_visits); fprintf(out, "GC[%d] objects collected: %" PRIu64 "\n", i, stats[i].objects_collected); + fprintf(out, "GC[%d] objects reachable from roots: %" PRIu64 "\n", i, stats[i].objects_transitively_reachable); + fprintf(out, "GC[%d] objects not reachable from roots: %" PRIu64 "\n", i, stats[i].objects_not_transitively_reachable); } } diff --git a/Tools/scripts/summarize_stats.py b/Tools/scripts/summarize_stats.py index abfdea7..bc7ccfe 100644 --- a/Tools/scripts/summarize_stats.py +++ b/Tools/scripts/summarize_stats.py @@ -1118,6 +1118,8 @@ def gc_stats_section() -> Section: Count(gen["collections"]), Count(gen["objects collected"]), Count(gen["object visits"]), + Count(gen["objects reachable from roots"]), + Count(gen["objects not reachable from roots"]), ) for (i, gen) in enumerate(gc_stats) ] @@ -1127,7 +1129,8 @@ def gc_stats_section() -> Section: "GC collections and effectiveness", [ Table( - ("Generation:", "Collections:", "Objects collected:", "Object visits:"), + ("Generation:", "Collections:", "Objects collected:", "Object visits:", + "Reachable from roots:", "Not reachable from roots:"), calc_gc_stats, ) ], -- cgit v0.12