Skip to content

Commit 654be8f

Browse files
colesburycolesbury
committed
gc: make the garbage collector non-generational
This is going to be important once the GIL is removed for a few reasons: - We won't be maintaining the GC linked list. Scanning the heap is O(N), best to do it in proprotion to the number of live objects. - Frequent stop-the-world pauses will become a bottleneck in multi-threaded programs - Python programs don't realy adhere to the generational hypothesis, so there isn't much benefit to a generational collector. Most objects seen by the GC *don't* die young! (Most survive the GC cycles.)
1 parent e8c13ea commit 654be8f

6 files changed

Lines changed: 143 additions & 336 deletions

File tree

‎Include/internal/pycore_gc.h‎

Lines changed: 18 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -106,7 +106,7 @@ static inline void _PyGC_SET_FINALIZED(PyObject *op) {
106106

107107
/* If we change this, we need to change the default value in the
108108
signature of gc.collect. */
109-
#define NUM_GENERATIONS 3
109+
#define NUM_GENERATIONS 1
110110
/*
111111
NOTE: about untracking of mutable objects.
112112
@@ -176,17 +176,24 @@ struct _gc_runtime_state {
176176
int enabled;
177177
int debug;
178178
/* linked lists of container objects */
179-
struct gc_generation generations[NUM_GENERATIONS];
180-
PyGC_Head *generation0;
179+
PyGC_Head head;
181180
/* a permanent generation which won't be collected */
182-
struct gc_generation permanent_generation;
183-
struct gc_generation_stats generation_stats[NUM_GENERATIONS];
181+
struct gc_generation_stats stats;
184182
/* true if we are currently running the collector */
185183
int collecting;
186184
/* list of uncollectable objects */
187185
PyObject *garbage;
188186
/* a list of callbacks to be invoked when collection is performed */
189187
PyObject *callbacks;
188+
/* the number of live GC objects */
189+
Py_ssize_t gc_live;
190+
/* the threshold at which to trigger a collection */
191+
Py_ssize_t gc_threshold;
192+
/* The ratio used to compute gc_threshold:
193+
gc_threshold = (1 + gc_scale/100) * gc_live
194+
A value of 100 means to collect every time the number of live
195+
objects doubles. */
196+
int gc_scale;
190197
/* This is the number of objects that survived the last full
191198
collection. It approximates the number of long lived objects
192199
tracked by the GC.
@@ -205,6 +212,12 @@ extern void _PyGC_InitState(struct _gc_runtime_state *);
205212

206213
extern Py_ssize_t _PyGC_CollectNoFail(PyThreadState *tstate);
207214

215+
static inline int
216+
_PyGC_ShouldCollect(struct _gc_runtime_state *gcstate)
217+
{
218+
Py_ssize_t live = _Py_atomic_load_ssize_relaxed(&gcstate->gc_live);
219+
return live >= gcstate->gc_threshold && gcstate->enabled && gcstate->gc_threshold && !gcstate->collecting;
220+
}
208221

209222
// Functions to clear types free lists
210223
extern void _PyTuple_ClearFreeList(PyInterpreterState *interp);

‎Include/internal/pycore_object.h‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -146,12 +146,12 @@ static inline void _PyObject_GC_TRACK(
146146
filename, lineno, __func__);
147147

148148
PyInterpreterState *interp = _PyInterpreterState_GET();
149-
PyGC_Head *generation0 = interp->gc.generation0;
150-
PyGC_Head *last = (PyGC_Head*)(generation0->_gc_prev);
149+
PyGC_Head *head = &interp->gc.head;
150+
PyGC_Head *last = (PyGC_Head*)(head->_gc_prev);
151151
_PyGCHead_SET_NEXT(last, gc);
152152
_PyGCHead_SET_PREV(gc, last);
153-
_PyGCHead_SET_NEXT(gc, generation0);
154-
generation0->_gc_prev = (uintptr_t)gc;
153+
_PyGCHead_SET_NEXT(gc, head);
154+
head->_gc_prev = (uintptr_t)gc;
155155
}
156156

157157
/* Tell the GC to stop tracking this object.

‎Include/internal/pycore_runtime_init.h‎

Lines changed: 0 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -119,12 +119,6 @@ extern "C" {
119119
}, \
120120
.gc = { \
121121
.enabled = 1, \
122-
.generations = { \
123-
/* .head is set in _PyGC_InitState(). */ \
124-
{ .threshold = 700, }, \
125-
{ .threshold = 10, }, \
126-
{ .threshold = 10, }, \
127-
}, \
128122
}, \
129123
.static_objects = { \
130124
.singletons = { \

‎Lib/test/audit-tests.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -359,7 +359,7 @@ def hook(event, args):
359359

360360
sys.addaudithook(hook)
361361

362-
gc.get_objects(generation=1)
362+
gc.get_objects()
363363

364364
x = object()
365365
y = [x]

‎Lib/test/test_gc.py‎

Lines changed: 26 additions & 101 deletions
Original file line numberDiff line numberDiff line change
@@ -356,47 +356,25 @@ def __del__(self):
356356
gc.disable()
357357
gc.set_threshold(*thresholds)
358358

359-
# The following two tests are fragile:
360-
# They precisely count the number of allocations,
361-
# which is highly implementation-dependent.
362-
# For example, disposed tuples are not freed, but reused.
363-
# To minimize variations, though, we first store the get_count() results
364-
# and check them at the end.
359+
# The following test is implementation-dependent because it
360+
# counts the number of allocations.
365361
@refcount_test
366362
def test_get_count(self):
367363
gc.collect()
368364
a, b, c = gc.get_count()
369-
x = []
365+
# Note: get_count() isn't precise. To enable faster allocations,
366+
# it is only updated when mimalloc "pages" become full or are no
367+
# longer full.
368+
tmp = []
369+
for _ in range(2048):
370+
tmp.append([''])
370371
d, e, f = gc.get_count()
371372
self.assertEqual((b, c), (0, 0))
372373
self.assertEqual((e, f), (0, 0))
373-
# This is less fragile than asserting that a equals 0.
374-
self.assertLess(a, 5)
375-
# Between the two calls to get_count(), at least one object was
376-
# created (the list).
374+
# Between the two calls to get_count(), enough objects were
375+
# created to increase the count.
377376
self.assertGreater(d, a)
378377

379-
@refcount_test
380-
def test_collect_generations(self):
381-
gc.collect()
382-
# This object will "trickle" into generation N + 1 after
383-
# each call to collect(N)
384-
x = []
385-
gc.collect(0)
386-
# x is now in gen 1
387-
a, b, c = gc.get_count()
388-
gc.collect(1)
389-
# x is now in gen 2
390-
d, e, f = gc.get_count()
391-
gc.collect(2)
392-
# x is now in gen 3
393-
g, h, i = gc.get_count()
394-
# We don't check a, d, g since their exact values depends on
395-
# internal implementation details of the interpreter.
396-
self.assertEqual((b, c), (1, 0))
397-
self.assertEqual((e, f), (0, 1))
398-
self.assertEqual((h, i), (0, 0))
399-
400378
def test_trashcan(self):
401379
class Ouch:
402380
n = 0
@@ -784,7 +762,7 @@ def __del__(self):
784762

785763
def test_get_stats(self):
786764
stats = gc.get_stats()
787-
self.assertEqual(len(stats), 3)
765+
self.assertEqual(len(stats), 1)
788766
for st in stats:
789767
self.assertIsInstance(st, dict)
790768
self.assertEqual(set(st),
@@ -797,20 +775,14 @@ def test_get_stats(self):
797775
self.addCleanup(gc.enable)
798776
gc.disable()
799777
old = gc.get_stats()
800-
gc.collect(0)
801-
new = gc.get_stats()
802-
self.assertEqual(new[0]["collections"], old[0]["collections"] + 1)
803-
self.assertEqual(new[1]["collections"], old[1]["collections"])
804-
self.assertEqual(new[2]["collections"], old[2]["collections"])
805-
gc.collect(2)
778+
gc.collect()
806779
new = gc.get_stats()
807780
self.assertEqual(new[0]["collections"], old[0]["collections"] + 1)
808-
self.assertEqual(new[1]["collections"], old[1]["collections"])
809-
self.assertEqual(new[2]["collections"], old[2]["collections"] + 1)
810781

811782
def test_freeze(self):
783+
# freeze no longer does anything, so count is always zero :(
812784
gc.freeze()
813-
self.assertGreater(gc.get_freeze_count(), 0)
785+
self.assertEqual(gc.get_freeze_count(), 0)
814786
gc.unfreeze()
815787
self.assertEqual(gc.get_freeze_count(), 0)
816788

@@ -819,52 +791,17 @@ def test_get_objects(self):
819791
l = []
820792
l.append(l)
821793
self.assertTrue(
822-
any(l is element for element in gc.get_objects(generation=0))
823-
)
824-
self.assertFalse(
825-
any(l is element for element in gc.get_objects(generation=1))
826-
)
827-
self.assertFalse(
828-
any(l is element for element in gc.get_objects(generation=2))
829-
)
830-
gc.collect(generation=0)
831-
self.assertFalse(
832-
any(l is element for element in gc.get_objects(generation=0))
833-
)
834-
self.assertTrue(
835-
any(l is element for element in gc.get_objects(generation=1))
836-
)
837-
self.assertFalse(
838-
any(l is element for element in gc.get_objects(generation=2))
839-
)
840-
gc.collect(generation=1)
841-
self.assertFalse(
842-
any(l is element for element in gc.get_objects(generation=0))
843-
)
844-
self.assertFalse(
845-
any(l is element for element in gc.get_objects(generation=1))
846-
)
847-
self.assertTrue(
848-
any(l is element for element in gc.get_objects(generation=2))
849-
)
850-
gc.collect(generation=2)
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))
794+
any(l is element for element in gc.get_objects())
856795
)
796+
gc.collect()
857797
self.assertTrue(
858-
any(l is element for element in gc.get_objects(generation=2))
798+
any(l is element for element in gc.get_objects())
859799
)
860800
del l
861801
gc.collect()
862802

863803
def test_get_objects_arguments(self):
864-
gc.collect()
865-
self.assertEqual(len(gc.get_objects()),
866-
len(gc.get_objects(generation=None)))
867-
804+
self.assertGreater(len(gc.get_objects()), 0)
868805
self.assertRaises(ValueError, gc.get_objects, 1000)
869806
self.assertRaises(ValueError, gc.get_objects, -1000)
870807
self.assertRaises(TypeError, gc.get_objects, "1")
@@ -1147,10 +1084,10 @@ def test_collect(self):
11471084

11481085
def test_collect_generation(self):
11491086
self.preclean()
1150-
gc.collect(2)
1087+
gc.collect(0)
11511088
for v in self.visit:
11521089
info = v[2]
1153-
self.assertEqual(info["generation"], 2)
1090+
self.assertEqual(info["generation"], 0)
11541091

11551092
@cpython_only
11561093
def test_collect_garbage(self):
@@ -1304,15 +1241,9 @@ def callback(ignored):
13041241

13051242
# We want to let gc happen "naturally", to preserve the distinction
13061243
# between generations.
1307-
junk = []
1308-
i = 0
1309-
detector = GC_Detector()
1310-
while not detector.gc_happened:
1311-
i += 1
1312-
if i > 10000:
1313-
self.fail("gc didn't happen after 10000 iterations")
1314-
self.assertEqual(len(ouch), 0)
1315-
junk.append([]) # this will eventually trigger gc
1244+
# TODO(sgross): revisit this. no guaranteed "natural" collection, so trigger
1245+
# a collection manually.
1246+
gc.collect()
13161247

13171248
self.assertEqual(len(ouch), 1) # else the callback wasn't invoked
13181249
for x in ouch:
@@ -1371,15 +1302,9 @@ def __del__(self):
13711302

13721303
# We want to let gc happen "naturally", to preserve the distinction
13731304
# between generations.
1374-
detector = GC_Detector()
1375-
junk = []
1376-
i = 0
1377-
while not detector.gc_happened:
1378-
i += 1
1379-
if i > 10000:
1380-
self.fail("gc didn't happen after 10000 iterations")
1381-
self.assertEqual(len(ouch), 0)
1382-
junk.append([]) # this will eventually trigger gc
1305+
# TODO(sgross): revisit this. no guaranteed "natural" collection, so trigger
1306+
# a collection manually.
1307+
gc.collect()
13831308

13841309
self.assertEqual(len(ouch), 1) # else __del__ wasn't invoked
13851310
for x in ouch:

0 commit comments

Comments
 (0)