Skip to content

Commit ebaca55

Browse files
Yhg1sAA-Turner
authored and
hugovk
committed
[3.13] pythonGH-124567: Revert the Incremental GC in 3.13 (python#124770)
Revert the incremental GC in 3.13, since it's not clear that without further turning, the benefits outweigh the costs. Co-authored-by: Adam Turner <9087854+AA-Turner@users.noreply.github.com>
1 parent 32e07fd commit ebaca55

9 files changed

Lines changed: 422 additions & 739 deletions

File tree

‎Doc/library/gc.rst‎

Lines changed: 14 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -40,18 +40,11 @@ The :mod:`gc` module provides the following functions:
4040

4141
.. function:: collect(generation=2)
4242

43-
Perform a collection. The optional argument *generation*
43+
With no arguments, run a full collection. The optional argument *generation*
4444
may be an integer specifying which generation to collect (from 0 to 2). A
4545
:exc:`ValueError` is raised if the generation number is invalid. The sum of
4646
collected objects and uncollectable objects is returned.
4747

48-
Calling ``gc.collect(0)`` will perform a GC collection on the young generation.
49-
50-
Calling ``gc.collect(1)`` will perform a GC collection on the young generation
51-
and an increment of the old generation.
52-
53-
Calling ``gc.collect(2)`` or ``gc.collect()`` performs a full collection
54-
5548
The free lists maintained for a number of built-in types are cleared
5649
whenever a full collection or collection of the highest generation (2)
5750
is run. Not all items in some free lists may be freed due to the
@@ -60,9 +53,6 @@ The :mod:`gc` module provides the following functions:
6053
The effect of calling ``gc.collect()`` while the interpreter is already
6154
performing a collection is undefined.
6255

63-
.. versionchanged:: 3.13
64-
``generation=1`` performs an increment of collection.
65-
6656

6757
.. function:: set_debug(flags)
6858

@@ -78,20 +68,13 @@ The :mod:`gc` module provides the following functions:
7868

7969
.. function:: get_objects(generation=None)
8070

81-
8271
Returns a list of all objects tracked by the collector, excluding the list
83-
returned. If *generation* is not ``None``, return only the objects as follows:
84-
85-
* 0: All objects in the young generation
86-
* 1: No objects, as there is no generation 1 (as of Python 3.13)
87-
* 2: All objects in the old generation
72+
returned. If *generation* is not ``None``, return only the objects tracked by
73+
the collector that are in that generation.
8874

8975
.. versionchanged:: 3.8
9076
New *generation* parameter.
9177

92-
.. versionchanged:: 3.13
93-
Generation 1 is removed
94-
9578
.. audit-event:: gc.get_objects generation gc.get_objects
9679

9780
.. function:: get_stats()
@@ -118,27 +101,19 @@ The :mod:`gc` module provides the following functions:
118101
Set the garbage collection thresholds (the collection frequency). Setting
119102
*threshold0* to zero disables collection.
120103

121-
The GC classifies objects into two generations depending on whether they have
122-
survived a collection. New objects are placed in the young generation. If an
123-
object survives a collection it is moved into the old generation.
124-
125-
In order to decide when to run, the collector keeps track of the number of object
104+
The GC classifies objects into three generations depending on how many
105+
collection sweeps they have survived. New objects are placed in the youngest
106+
generation (generation ``0``). If an object survives a collection it is moved
107+
into the next older generation. Since generation ``2`` is the oldest
108+
generation, objects in that generation remain there after a collection. In
109+
order to decide when to run, the collector keeps track of the number object
126110
allocations and deallocations since the last collection. When the number of
127111
allocations minus the number of deallocations exceeds *threshold0*, collection
128-
starts. For each collection, all the objects in the young generation and some
129-
fraction of the old generation is collected.
130-
131-
The fraction of the old generation that is collected is **inversely** proportional
132-
to *threshold1*. The larger *threshold1* is, the slower objects in the old generation
133-
are collected.
134-
For the default value of 10, 1% of the old generation is scanned during each collection.
135-
136-
*threshold2* is ignored.
137-
138-
See `Garbage collector design <https://devguide.python.org/garbage_collector>`_ for more information.
139-
140-
.. versionchanged:: 3.13
141-
*threshold2* is ignored
112+
starts. Initially only generation ``0`` is examined. If generation ``0`` has
113+
been examined more than *threshold1* times since generation ``1`` has been
114+
examined, then generation ``1`` is examined as well.
115+
With the third generation, things are a bit more complicated,
116+
see `Collecting the oldest generation <https://devguide.python.org/garbage_collector/#collecting-the-oldest-generation>`_ for more information.
142117

143118

144119
.. function:: get_count()

‎Include/internal/pycore_gc.h‎

Lines changed: 8 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -143,23 +143,8 @@ static inline void _PyObject_GC_SET_SHARED_INLINE(PyObject *op) {
143143
#define _PyGC_PREV_MASK_FINALIZED ((uintptr_t)1)
144144
/* Bit 1 is set when the object is in generation which is GCed currently. */
145145
#define _PyGC_PREV_MASK_COLLECTING ((uintptr_t)2)
146-
147-
/* Bit 0 in _gc_next is the old space bit.
148-
* It is set as follows:
149-
* Young: gcstate->visited_space
150-
* old[0]: 0
151-
* old[1]: 1
152-
* permanent: 0
153-
*
154-
* During a collection all objects handled should have the bit set to
155-
* gcstate->visited_space, as objects are moved from the young gen
156-
* and the increment into old[gcstate->visited_space].
157-
* When object are moved from the pending space, old[gcstate->visited_space^1]
158-
* into the increment, the old space bit is flipped.
159-
*/
160-
#define _PyGC_NEXT_MASK_OLD_SPACE_1 1
161-
162-
#define _PyGC_PREV_SHIFT 2
146+
/* The (N-2) most significant bits contain the real address. */
147+
#define _PyGC_PREV_SHIFT (2)
163148
#define _PyGC_PREV_MASK (((uintptr_t) -1) << _PyGC_PREV_SHIFT)
164149

165150
/* set for debugging information */
@@ -185,21 +170,18 @@ typedef enum {
185170
// Lowest bit of _gc_next is used for flags only in GC.
186171
// But it is always 0 for normal code.
187172
static inline PyGC_Head* _PyGCHead_NEXT(PyGC_Head *gc) {
188-
uintptr_t next = gc->_gc_next & _PyGC_PREV_MASK;
173+
uintptr_t next = gc->_gc_next;
189174
return (PyGC_Head*)next;
190175
}
191176
static inline void _PyGCHead_SET_NEXT(PyGC_Head *gc, PyGC_Head *next) {
192-
uintptr_t unext = (uintptr_t)next;
193-
assert((unext & ~_PyGC_PREV_MASK) == 0);
194-
gc->_gc_next = (gc->_gc_next & ~_PyGC_PREV_MASK) | unext;
177+
gc->_gc_next = (uintptr_t)next;
195178
}
196179

197180
// Lowest two bits of _gc_prev is used for _PyGC_PREV_MASK_* flags.
198181
static inline PyGC_Head* _PyGCHead_PREV(PyGC_Head *gc) {
199182
uintptr_t prev = (gc->_gc_prev & _PyGC_PREV_MASK);
200183
return (PyGC_Head*)prev;
201184
}
202-
203185
static inline void _PyGCHead_SET_PREV(PyGC_Head *gc, PyGC_Head *prev) {
204186
uintptr_t uprev = (uintptr_t)prev;
205187
assert((uprev & ~_PyGC_PREV_MASK) == 0);
@@ -285,13 +267,6 @@ struct gc_generation {
285267
generations */
286268
};
287269

288-
struct gc_collection_stats {
289-
/* number of collected objects */
290-
Py_ssize_t collected;
291-
/* total number of uncollectable objects (put into gc.garbage) */
292-
Py_ssize_t uncollectable;
293-
};
294-
295270
/* Running stats per generation */
296271
struct gc_generation_stats {
297272
/* total number of collections */
@@ -313,8 +288,8 @@ struct _gc_runtime_state {
313288
int enabled;
314289
int debug;
315290
/* linked lists of container objects */
316-
struct gc_generation young;
317-
struct gc_generation old[2];
291+
struct gc_generation generations[NUM_GENERATIONS];
292+
PyGC_Head *generation0;
318293
/* a permanent generation which won't be collected */
319294
struct gc_generation permanent_generation;
320295
struct gc_generation_stats generation_stats[NUM_GENERATIONS];
@@ -325,12 +300,6 @@ struct _gc_runtime_state {
325300
/* a list of callbacks to be invoked when collection is performed */
326301
PyObject *callbacks;
327302

328-
Py_ssize_t heap_size;
329-
Py_ssize_t work_to_do;
330-
/* Which of the old spaces is the visited space */
331-
int visited_space;
332-
333-
#ifdef Py_GIL_DISABLED
334303
/* This is the number of objects that survived the last full
335304
collection. It approximates the number of long lived objects
336305
tracked by the GC.
@@ -342,7 +311,6 @@ struct _gc_runtime_state {
342311
collections, and are awaiting to undergo a full collection for
343312
the first time. */
344313
Py_ssize_t long_lived_pending;
345-
#endif
346314
};
347315

348316
#ifdef Py_GIL_DISABLED
@@ -355,7 +323,8 @@ struct _gc_thread_state {
355323

356324
extern void _PyGC_InitState(struct _gc_runtime_state *);
357325

358-
extern Py_ssize_t _PyGC_Collect(PyThreadState *tstate, int generation, _PyGC_Reason reason);
326+
extern Py_ssize_t _PyGC_Collect(PyThreadState *tstate, int generation,
327+
_PyGC_Reason reason);
359328
extern void _PyGC_CollectNoFail(PyThreadState *tstate);
360329

361330
/* Freeze objects tracked by the GC and ignore them in future collections. */

‎Include/internal/pycore_object.h‎

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -462,12 +462,11 @@ static inline void _PyObject_GC_TRACK(
462462
filename, lineno, __func__);
463463

464464
PyInterpreterState *interp = _PyInterpreterState_GET();
465-
PyGC_Head *generation0 = &interp->gc.young.head;
465+
PyGC_Head *generation0 = interp->gc.generation0;
466466
PyGC_Head *last = (PyGC_Head*)(generation0->_gc_prev);
467467
_PyGCHead_SET_NEXT(last, gc);
468468
_PyGCHead_SET_PREV(gc, last);
469-
/* Young objects will be moved into the visited space during GC, so set the bit here */
470-
gc->_gc_next = ((uintptr_t)generation0) | (uintptr_t)interp->gc.visited_space;
469+
_PyGCHead_SET_NEXT(gc, generation0);
471470
generation0->_gc_prev = (uintptr_t)gc;
472471
#endif
473472
}

‎Include/internal/pycore_runtime_init.h‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -126,12 +126,12 @@ extern PyTypeObject _PyExc_MemoryError;
126126
}, \
127127
.gc = { \
128128
.enabled = 1, \
129-
.young = { .threshold = 2000, }, \
130-
.old = { \
129+
.generations = { \
130+
/* .head is set in _PyGC_InitState(). */ \
131+
{ .threshold = 2000, }, \
132+
{ .threshold = 10, }, \
131133
{ .threshold = 10, }, \
132-
{ .threshold = 0, }, \
133134
}, \
134-
.work_to_do = -5000, \
135135
}, \
136136
.qsbr = { \
137137
.wr_seq = QSBR_INITIAL, \

‎Lib/test/test_gc.py‎

Lines changed: 43 additions & 69 deletions
Original file line numberDiff line numberDiff line change
@@ -388,11 +388,19 @@ def test_collect_generations(self):
388388
# each call to collect(N)
389389
x = []
390390
gc.collect(0)
391-
# x is now in the old gen
391+
# x is now in gen 1
392392
a, b, c = gc.get_count()
393-
# We don't check a since its exact values depends on
393+
gc.collect(1)
394+
# x is now in gen 2
395+
d, e, f = gc.get_count()
396+
gc.collect(2)
397+
# x is now in gen 3
398+
g, h, i = gc.get_count()
399+
# We don't check a, d, g since their exact values depends on
394400
# internal implementation details of the interpreter.
395401
self.assertEqual((b, c), (1, 0))
402+
self.assertEqual((e, f), (0, 1))
403+
self.assertEqual((h, i), (0, 0))
396404

397405
def test_trashcan(self):
398406
class Ouch:
@@ -828,10 +836,42 @@ def test_get_objects_generations(self):
828836
self.assertTrue(
829837
any(l is element for element in gc.get_objects(generation=0))
830838
)
831-
gc.collect()
839+
self.assertFalse(
840+
any(l is element for element in gc.get_objects(generation=1))
841+
)
842+
self.assertFalse(
843+
any(l is element for element in gc.get_objects(generation=2))
844+
)
845+
gc.collect(generation=0)
832846
self.assertFalse(
833847
any(l is element for element in gc.get_objects(generation=0))
834848
)
849+
self.assertTrue(
850+
any(l is element for element in gc.get_objects(generation=1))
851+
)
852+
self.assertFalse(
853+
any(l is element for element in gc.get_objects(generation=2))
854+
)
855+
gc.collect(generation=1)
856+
self.assertFalse(
857+
any(l is element for element in gc.get_objects(generation=0))
858+
)
859+
self.assertFalse(
860+
any(l is element for element in gc.get_objects(generation=1))
861+
)
862+
self.assertTrue(
863+
any(l is element for element in gc.get_objects(generation=2))
864+
)
865+
gc.collect(generation=2)
866+
self.assertFalse(
867+
any(l is element for element in gc.get_objects(generation=0))
868+
)
869+
self.assertFalse(
870+
any(l is element for element in gc.get_objects(generation=1))
871+
)
872+
self.assertTrue(
873+
any(l is element for element in gc.get_objects(generation=2))
874+
)
835875
del l
836876
gc.collect()
837877

@@ -1082,72 +1122,6 @@ def __del__(self):
10821122
gc.collect()
10831123
self.assertTrue(collected)
10841124

1085-
1086-
class IncrementalGCTests(unittest.TestCase):
1087-
1088-
def setUp(self):
1089-
# Reenable GC as it is disabled module-wide
1090-
gc.enable()
1091-
1092-
def tearDown(self):
1093-
gc.disable()
1094-
1095-
@requires_gil_enabled("Free threading does not support incremental GC")
1096-
# Use small increments to emulate longer running process in a shorter time
1097-
@gc_threshold(200, 10)
1098-
def test_incremental_gc_handles_fast_cycle_creation(self):
1099-
1100-
class LinkedList:
1101-
1102-
#Use slots to reduce number of implicit objects
1103-
__slots__ = "next", "prev", "surprise"
1104-
1105-
def __init__(self, next=None, prev=None):
1106-
self.next = next
1107-
if next is not None:
1108-
next.prev = self
1109-
self.prev = prev
1110-
if prev is not None:
1111-
prev.next = self
1112-
1113-
def make_ll(depth):
1114-
head = LinkedList()
1115-
for i in range(depth):
1116-
head = LinkedList(head, head.prev)
1117-
return head
1118-
1119-
head = make_ll(1000)
1120-
count = 1000
1121-
1122-
# There will be some objects we aren't counting,
1123-
# e.g. the gc stats dicts. This test checks
1124-
# that the counts don't grow, so we try to
1125-
# correct for the uncounted objects
1126-
# This is just an estimate.
1127-
CORRECTION = 20
1128-
1129-
enabled = gc.isenabled()
1130-
gc.enable()
1131-
olds = []
1132-
for i in range(20_000):
1133-
newhead = make_ll(20)
1134-
count += 20
1135-
newhead.surprise = head
1136-
olds.append(newhead)
1137-
if len(olds) == 20:
1138-
stats = gc.get_stats()
1139-
young = stats[0]
1140-
incremental = stats[1]
1141-
old = stats[2]
1142-
collected = young['collected'] + incremental['collected'] + old['collected']
1143-
count += CORRECTION
1144-
live = count - collected
1145-
self.assertLess(live, 25000)
1146-
del olds[:]
1147-
if not enabled:
1148-
gc.disable()
1149-
1150-
11511125
class GCCallbackTests(unittest.TestCase):
11521126
def setUp(self):
11531127
# Save gc state and disable it.

‎Misc/NEWS.d/next/Core_and_Builtins/2024-09-30-21-02-10.gh-issue-124567.tv_B_C.rst‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
Revert the incremental GC (in 3.13), since it's not clear the benefits outweigh the costs at this point.

0 commit comments

Comments
 (0)