Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 1530932

Browse filesBrowse files
markshannonmarkshannon
authored
GH-108362: Incremental Cycle GC (GH-116206)
1 parent d5ebf8b commit 1530932
Copy full SHA for 1530932

File tree

14 files changed

+684
-388
lines changed
Filter options

14 files changed

+684
-388
lines changed

‎Doc/whatsnew/3.13.rst

Copy file name to clipboardExpand all lines: Doc/whatsnew/3.13.rst
+30Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -111,6 +111,14 @@ Improved Error Messages
111111
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^
112112
TypeError: split() got an unexpected keyword argument 'max_split'. Did you mean 'maxsplit'?
113113

114+
Incremental Garbage Collection
115+
------------------------------
116+
117+
* The cycle garbage collector is now incremental.
118+
This means that maximum pause times are reduced
119+
by an order of magnitude or more for larger heaps.
120+
121+
114122
Other Language Changes
115123
======================
116124

@@ -350,6 +358,28 @@ fractions
350358
sign handling, minimum width and grouping. (Contributed by Mark Dickinson
351359
in :gh:`111320`.)
352360

361+
gc
362+
--
363+
364+
* The cyclic garbage collector is now incremental, which changes the meanings
365+
of the results of :meth:`gc.get_threshold` and :meth:`gc.get_threshold` as
366+
well as :meth:`gc.get_count` and :meth:`gc.get_stats`.
367+
* :meth:`gc.get_threshold` returns a three-tuple for backwards compatibility,
368+
the first value is the threshold for young collections, as before, the second
369+
value determines the rate at which the old collection is scanned; the
370+
default is 10 and higher values mean that the old collection is scanned more slowly.
371+
The third value is meangless and is always zero.
372+
* :meth:`gc.set_threshold` ignores any items after the second.
373+
* :meth:`gc.get_count` and :meth:`gc.get_stats`.
374+
These functions return the same format of results as before.
375+
The only difference is that instead of the results refering to
376+
the young, aging and old generations, the results refer to the
377+
young generation and the aging and collecting spaces of the old generation.
378+
379+
In summary, code that attempted to manipulate the behavior of the cycle GC may
380+
not work exactly as intended, but it is very unlikely to harmful.
381+
All other code will work just fine.
382+
353383
glob
354384
----
355385

‎Include/internal/pycore_gc.h

Copy file name to clipboardExpand all lines: Include/internal/pycore_gc.h
+30-11Lines changed: 30 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -109,11 +109,14 @@ static inline void _PyObject_GC_SET_SHARED_INLINE(PyObject *op) {
109109

110110
/* Bit flags for _gc_prev */
111111
/* Bit 0 is set when tp_finalize is called */
112-
#define _PyGC_PREV_MASK_FINALIZED (1)
112+
#define _PyGC_PREV_MASK_FINALIZED 1
113113
/* Bit 1 is set when the object is in generation which is GCed currently. */
114-
#define _PyGC_PREV_MASK_COLLECTING (2)
115-
/* The (N-2) most significant bits contain the real address. */
116-
#define _PyGC_PREV_SHIFT (2)
114+
#define _PyGC_PREV_MASK_COLLECTING 2
115+
116+
/* Bit 0 is set if the object belongs to old space 1 */
117+
#define _PyGC_NEXT_MASK_OLD_SPACE_1 1
118+
119+
#define _PyGC_PREV_SHIFT 2
117120
#define _PyGC_PREV_MASK (((uintptr_t) -1) << _PyGC_PREV_SHIFT)
118121

119122
/* set for debugging information */
@@ -139,18 +142,21 @@ typedef enum {
139142
// Lowest bit of _gc_next is used for flags only in GC.
140143
// But it is always 0 for normal code.
141144
static inline PyGC_Head* _PyGCHead_NEXT(PyGC_Head *gc) {
142-
uintptr_t next = gc->_gc_next;
145+
uintptr_t next = gc->_gc_next & _PyGC_PREV_MASK;
143146
return (PyGC_Head*)next;
144147
}
145148
static inline void _PyGCHead_SET_NEXT(PyGC_Head *gc, PyGC_Head *next) {
146-
gc->_gc_next = (uintptr_t)next;
149+
uintptr_t unext = (uintptr_t)next;
150+
assert((unext & ~_PyGC_PREV_MASK) == 0);
151+
gc->_gc_next = (gc->_gc_next & ~_PyGC_PREV_MASK) | unext;
147152
}
148153

149154
// Lowest two bits of _gc_prev is used for _PyGC_PREV_MASK_* flags.
150155
static inline PyGC_Head* _PyGCHead_PREV(PyGC_Head *gc) {
151156
uintptr_t prev = (gc->_gc_prev & _PyGC_PREV_MASK);
152157
return (PyGC_Head*)prev;
153158
}
159+
154160
static inline void _PyGCHead_SET_PREV(PyGC_Head *gc, PyGC_Head *prev) {
155161
uintptr_t uprev = (uintptr_t)prev;
156162
assert((uprev & ~_PyGC_PREV_MASK) == 0);
@@ -236,6 +242,13 @@ struct gc_generation {
236242
generations */
237243
};
238244

245+
struct gc_collection_stats {
246+
/* number of collected objects */
247+
Py_ssize_t collected;
248+
/* total number of uncollectable objects (put into gc.garbage) */
249+
Py_ssize_t uncollectable;
250+
};
251+
239252
/* Running stats per generation */
240253
struct gc_generation_stats {
241254
/* total number of collections */
@@ -257,8 +270,8 @@ struct _gc_runtime_state {
257270
int enabled;
258271
int debug;
259272
/* linked lists of container objects */
260-
struct gc_generation generations[NUM_GENERATIONS];
261-
PyGC_Head *generation0;
273+
struct gc_generation young;
274+
struct gc_generation old[2];
262275
/* a permanent generation which won't be collected */
263276
struct gc_generation permanent_generation;
264277
struct gc_generation_stats generation_stats[NUM_GENERATIONS];
@@ -268,6 +281,12 @@ struct _gc_runtime_state {
268281
PyObject *garbage;
269282
/* a list of callbacks to be invoked when collection is performed */
270283
PyObject *callbacks;
284+
285+
Py_ssize_t work_to_do;
286+
/* Which of the old spaces is the visited space */
287+
int visited_space;
288+
289+
#ifdef Py_GIL_DISABLED
271290
/* This is the number of objects that survived the last full
272291
collection. It approximates the number of long lived objects
273292
tracked by the GC.
@@ -279,6 +298,7 @@ struct _gc_runtime_state {
279298
collections, and are awaiting to undergo a full collection for
280299
the first time. */
281300
Py_ssize_t long_lived_pending;
301+
#endif
282302
};
283303

284304
#ifdef Py_GIL_DISABLED
@@ -291,9 +311,8 @@ struct _gc_thread_state {
291311

292312
extern void _PyGC_InitState(struct _gc_runtime_state *);
293313

294-
extern Py_ssize_t _PyGC_Collect(PyThreadState *tstate, int generation,
295-
_PyGC_Reason reason);
296-
extern Py_ssize_t _PyGC_CollectNoFail(PyThreadState *tstate);
314+
extern Py_ssize_t _PyGC_Collect(PyThreadState *tstate, int generation, _PyGC_Reason reason);
315+
extern void _PyGC_CollectNoFail(PyThreadState *tstate);
297316

298317
/* Freeze objects tracked by the GC and ignore them in future collections. */
299318
extern void _PyGC_Freeze(PyInterpreterState *interp);

‎Include/internal/pycore_object.h

Copy file name to clipboardExpand all lines: Include/internal/pycore_object.h
+4-14Lines changed: 4 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -125,19 +125,8 @@ static inline void _Py_RefcntAdd(PyObject* op, Py_ssize_t n)
125125
}
126126
#define _Py_RefcntAdd(op, n) _Py_RefcntAdd(_PyObject_CAST(op), n)
127127

128-
static inline void _Py_SetImmortal(PyObject *op)
129-
{
130-
if (op) {
131-
#ifdef Py_GIL_DISABLED
132-
op->ob_tid = _Py_UNOWNED_TID;
133-
op->ob_ref_local = _Py_IMMORTAL_REFCNT_LOCAL;
134-
op->ob_ref_shared = 0;
135-
#else
136-
op->ob_refcnt = _Py_IMMORTAL_REFCNT;
137-
#endif
138-
}
139-
}
140-
#define _Py_SetImmortal(op) _Py_SetImmortal(_PyObject_CAST(op))
128+
extern void _Py_SetImmortal(PyObject *op);
129+
extern void _Py_SetImmortalUntracked(PyObject *op);
141130

142131
// Makes an immortal object mortal again with the specified refcnt. Should only
143132
// be used during runtime finalization.
@@ -325,11 +314,12 @@ static inline void _PyObject_GC_TRACK(
325314
filename, lineno, __func__);
326315

327316
PyInterpreterState *interp = _PyInterpreterState_GET();
328-
PyGC_Head *generation0 = interp->gc.generation0;
317+
PyGC_Head *generation0 = &interp->gc.young.head;
329318
PyGC_Head *last = (PyGC_Head*)(generation0->_gc_prev);
330319
_PyGCHead_SET_NEXT(last, gc);
331320
_PyGCHead_SET_PREV(gc, last);
332321
_PyGCHead_SET_NEXT(gc, generation0);
322+
assert((gc->_gc_next & _PyGC_NEXT_MASK_OLD_SPACE_1) == 0);
333323
generation0->_gc_prev = (uintptr_t)gc;
334324
#endif
335325
}

‎Include/internal/pycore_runtime_init.h

Copy file name to clipboardExpand all lines: Include/internal/pycore_runtime_init.h
+4-4Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -168,12 +168,12 @@ extern PyTypeObject _PyExc_MemoryError;
168168
}, \
169169
.gc = { \
170170
.enabled = 1, \
171-
.generations = { \
172-
/* .head is set in _PyGC_InitState(). */ \
173-
{ .threshold = 700, }, \
174-
{ .threshold = 10, }, \
171+
.young = { .threshold = 2000, }, \
172+
.old = { \
175173
{ .threshold = 10, }, \
174+
{ .threshold = 0, }, \
176175
}, \
176+
.work_to_do = -5000, \
177177
}, \
178178
.qsbr = { \
179179
.wr_seq = QSBR_INITIAL, \

‎Lib/test/test_gc.py

Copy file name to clipboardExpand all lines: Lib/test/test_gc.py
+52-20Lines changed: 52 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -384,19 +384,11 @@ def test_collect_generations(self):
384384
# each call to collect(N)
385385
x = []
386386
gc.collect(0)
387-
# x is now in gen 1
387+
# x is now in the old gen
388388
a, b, c = gc.get_count()
389-
gc.collect(1)
390-
# x is now in gen 2
391-
d, e, f = gc.get_count()
392-
gc.collect(2)
393-
# x is now in gen 3
394-
g, h, i = gc.get_count()
395-
# We don't check a, d, g since their exact values depends on
389+
# We don't check a since its exact values depends on
396390
# internal implementation details of the interpreter.
397391
self.assertEqual((b, c), (1, 0))
398-
self.assertEqual((e, f), (0, 1))
399-
self.assertEqual((h, i), (0, 0))
400392

401393
def test_trashcan(self):
402394
class Ouch:
@@ -847,16 +839,6 @@ def test_get_objects_generations(self):
847839
self.assertFalse(
848840
any(l is element for element in gc.get_objects(generation=2))
849841
)
850-
gc.collect(generation=1)
851-
self.assertFalse(
852-
any(l is element for element in gc.get_objects(generation=0))
853-
)
854-
self.assertFalse(
855-
any(l is element for element in gc.get_objects(generation=1))
856-
)
857-
self.assertTrue(
858-
any(l is element for element in gc.get_objects(generation=2))
859-
)
860842
gc.collect(generation=2)
861843
self.assertFalse(
862844
any(l is element for element in gc.get_objects(generation=0))
@@ -1076,6 +1058,56 @@ class Z:
10761058
callback.assert_not_called()
10771059
gc.enable()
10781060

1061+
@unittest.skipIf(Py_GIL_DISABLED, "Free threading does not support incremental GC")
1062+
def test_incremental_gc_handles_fast_cycle_creation(self):
1063+
1064+
class LinkedList:
1065+
1066+
#Use slots to reduce number of implicit objects
1067+
__slots__ = "next", "prev", "surprise"
1068+
1069+
def __init__(self, next=None, prev=None):
1070+
self.next = next
1071+
if next is not None:
1072+
next.prev = self
1073+
self.prev = prev
1074+
if prev is not None:
1075+
prev.next = self
1076+
1077+
def make_ll(depth):
1078+
head = LinkedList()
1079+
for i in range(depth):
1080+
head = LinkedList(head, head.prev)
1081+
return head
1082+
1083+
head = make_ll(10000)
1084+
count = 10000
1085+
1086+
# We expect the counts to go negative eventually
1087+
# as there will some objects we aren't counting,
1088+
# e.g. the gc stats dicts. The test merely checks
1089+
# that the counts don't grow.
1090+
1091+
enabled = gc.isenabled()
1092+
gc.enable()
1093+
olds = []
1094+
for i in range(1000):
1095+
newhead = make_ll(200)
1096+
count += 200
1097+
newhead.surprise = head
1098+
olds.append(newhead)
1099+
if len(olds) == 50:
1100+
stats = gc.get_stats()
1101+
young = stats[0]
1102+
incremental = stats[1]
1103+
old = stats[2]
1104+
collected = young['collected'] + incremental['collected'] + old['collected']
1105+
live = count - collected
1106+
self.assertLess(live, 25000)
1107+
del olds[:]
1108+
if not enabled:
1109+
gc.disable()
1110+
10791111

10801112
class GCCallbackTests(unittest.TestCase):
10811113
def setUp(self):

‎Misc/NEWS.d/next/Core and Builtins/2024-01-07-04-22-51.gh-issue-108362.oB9Gcf.rst

Copy file name to clipboard
+12Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
Implement an incremental cyclic garbage collector. By collecting the old
2+
generation in increments, there is no need for a full heap scan. This can
3+
hugely reduce maximum pause time for programs with large heaps.
4+
5+
Reduce the number of generations from three to two. The old generation is
6+
split into two spaces, "visited" and "pending".
7+
8+
Collection happens in two steps::
9+
* An increment is formed from the young generation and a small part of the pending space.
10+
* This increment is scanned and the survivors moved to the end of the visited space.
11+
12+
When the collecting space becomes empty, the two spaces are swapped.

‎Modules/gcmodule.c

Copy file name to clipboardExpand all lines: Modules/gcmodule.c
+10-15Lines changed: 10 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -158,17 +158,12 @@ gc_set_threshold_impl(PyObject *module, int threshold0, int group_right_1,
158158
{
159159
GCState *gcstate = get_gc_state();
160160

161-
gcstate->generations[0].threshold = threshold0;
161+
gcstate->young.threshold = threshold0;
162162
if (group_right_1) {
163-
gcstate->generations[1].threshold = threshold1;
163+
gcstate->old[0].threshold = threshold1;
164164
}
165165
if (group_right_2) {
166-
gcstate->generations[2].threshold = threshold2;
167-
168-
/* generations higher than 2 get the same threshold */
169-
for (int i = 3; i < NUM_GENERATIONS; i++) {
170-
gcstate->generations[i].threshold = gcstate->generations[2].threshold;
171-
}
166+
gcstate->old[1].threshold = threshold2;
172167
}
173168
Py_RETURN_NONE;
174169
}
@@ -185,9 +180,9 @@ gc_get_threshold_impl(PyObject *module)
185180
{
186181
GCState *gcstate = get_gc_state();
187182
return Py_BuildValue("(iii)",
188-
gcstate->generations[0].threshold,
189-
gcstate->generations[1].threshold,
190-
gcstate->generations[2].threshold);
183+
gcstate->young.threshold,
184+
gcstate->old[0].threshold,
185+
0);
191186
}
192187

193188
/*[clinic input]
@@ -207,14 +202,14 @@ gc_get_count_impl(PyObject *module)
207202
struct _gc_thread_state *gc = &tstate->gc;
208203

209204
// Flush the local allocation count to the global count
210-
_Py_atomic_add_int(&gcstate->generations[0].count, (int)gc->alloc_count);
205+
_Py_atomic_add_int(&gcstate->young.count, (int)gc->alloc_count);
211206
gc->alloc_count = 0;
212207
#endif
213208

214209
return Py_BuildValue("(iii)",
215-
gcstate->generations[0].count,
216-
gcstate->generations[1].count,
217-
gcstate->generations[2].count);
210+
gcstate->young.count,
211+
gcstate->old[gcstate->visited_space].count,
212+
gcstate->old[gcstate->visited_space^1].count);
218213
}
219214

220215
/*[clinic input]

‎Objects/object.c

Copy file name to clipboardExpand all lines: Objects/object.c
+21Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2401,6 +2401,27 @@ _Py_NewReferenceNoTotal(PyObject *op)
24012401
new_reference(op);
24022402
}
24032403

2404+
void
2405+
_Py_SetImmortalUntracked(PyObject *op)
2406+
{
2407+
#ifdef Py_GIL_DISABLED
2408+
op->ob_tid = _Py_UNOWNED_TID;
2409+
op->ob_ref_local = _Py_IMMORTAL_REFCNT_LOCAL;
2410+
op->ob_ref_shared = 0;
2411+
#else
2412+
op->ob_refcnt = _Py_IMMORTAL_REFCNT;
2413+
#endif
2414+
}
2415+
2416+
void
2417+
_Py_SetImmortal(PyObject *op)
2418+
{
2419+
if (PyObject_IS_GC(op) && _PyObject_GC_IS_TRACKED(op)) {
2420+
_PyObject_GC_UNTRACK(op);
2421+
}
2422+
_Py_SetImmortalUntracked(op);
2423+
}
2424+
24042425
void
24052426
_Py_ResurrectReference(PyObject *op)
24062427
{

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.