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 8893cf5

Browse filesBrowse files
markshannonmarkshannon
committed
Assume that increments are 50% garbage for work done calculation
1 parent 68fc90b commit 8893cf5
Copy full SHA for 8893cf5

File tree

3 files changed

+27
-35
lines changed
Filter options

3 files changed

+27
-35
lines changed

‎Lib/test/test_gc.py

Copy file name to clipboardExpand all lines: Lib/test/test_gc.py
+3-11Lines changed: 3 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1161,27 +1161,19 @@ def make_ll(depth):
11611161
return head
11621162

11631163
head = make_ll(1000)
1164-
count = 1000
1165-
1166-
# There will be some objects we aren't counting,
1167-
# e.g. the gc stats dicts. This test checks
1168-
# that the counts don't grow, so we try to
1169-
# correct for the uncounted objects
1170-
# This is just an estimate.
1171-
CORRECTION = 20
11721164

11731165
enabled = gc.isenabled()
11741166
gc.enable()
11751167
olds = []
11761168
initial_heap_size = _testinternalcapi.get_tracked_heap_size()
1177-
for i in range(20_000):
1169+
iterations = max(20_000, initial_heap_size)
1170+
for i in range(iterations):
11781171
newhead = make_ll(20)
1179-
count += 20
11801172
newhead.surprise = head
11811173
olds.append(newhead)
11821174
if len(olds) == 20:
11831175
new_objects = _testinternalcapi.get_tracked_heap_size() - initial_heap_size
1184-
self.assertLess(new_objects, 27_000, f"Heap growing. Reached limit after {i} iterations")
1176+
self.assertLess(new_objects, initial_heap_size/2, f"Heap growing. Reached limit after {i} iterations")
11851177
del olds[:]
11861178
if not enabled:
11871179
gc.disable()

‎Objects/typeobject.c

Copy file name to clipboardExpand all lines: Objects/typeobject.c
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4156,7 +4156,7 @@ type_new_descriptors(const type_new_ctx *ctx, PyTypeObject *type)
41564156
assert((type->tp_flags & Py_TPFLAGS_MANAGED_DICT) == 0);
41574157
type->tp_flags |= Py_TPFLAGS_MANAGED_DICT;
41584158
type->tp_dictoffset = -1;
4159-
if (type->tp_basicsize == sizeof(PyObject *)) {
4159+
if (type->tp_basicsize == sizeof(PyObject)) {
41604160
type->tp_traverse = plain_object_traverse;
41614161
}
41624162
}

‎Python/gc.c

Copy file name to clipboardExpand all lines: Python/gc.c
+23-23Lines changed: 23 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -1277,17 +1277,12 @@ gc_list_set_space(PyGC_Head *list, int space)
12771277
* space faster than objects are added to the old space.
12781278
*
12791279
* Each young or incremental collection adds a number of
1280-
* objects, S (for survivors) to the old space, and
1281-
* incremental collectors scan I objects from the old space.
1282-
* I > S must be true. We also want I > S * N to be where
1283-
* N > 1. Higher values of N mean that the old space is
1280+
* new objects (N) to the heap, and incremental collectors
1281+
* scan I objects from the old space.
1282+
* I > N must be true. We also want I > N * K to be where
1283+
* K > 2. Higher values of K mean that the old space is
12841284
* scanned more rapidly.
1285-
* The default incremental threshold of 10 translates to
1286-
* N == 1.4 (1 + 4/threshold)
12871285
*/
1288-
1289-
/* Divide by 10, so that the default incremental threshold of 10
1290-
* scans objects at 1% of the heap size */
12911286
#define SCAN_RATE_DIVISOR 10
12921287

12931288
static void
@@ -1335,6 +1330,7 @@ typedef struct work_stack {
13351330
int visited_space;
13361331
} WorkStack;
13371332

1333+
/* Remove gc from the list it is currently in and push it to the stack */
13381334
static inline void
13391335
push_to_stack(PyGC_Head *gc, WorkStack *stack)
13401336
{
@@ -1346,6 +1342,14 @@ push_to_stack(PyGC_Head *gc, WorkStack *stack)
13461342
stack->top = gc;
13471343
}
13481344

1345+
static inline PyGC_Head *
1346+
pop_from_stack(WorkStack *stack)
1347+
{
1348+
PyGC_Head *gc = stack->top;
1349+
stack->top = _PyGCHead_PREV(gc);
1350+
return gc;
1351+
}
1352+
13491353
/* append list `from` to `stack`; `from` becomes an empty list */
13501354
static void
13511355
move_list_to_stack(PyGC_Head *from, WorkStack *stack)
@@ -1418,7 +1422,6 @@ completed_scavenge(GCState *gcstate)
14181422
gc_list_set_space(&gcstate->old[not_visited].head, not_visited);
14191423
}
14201424
assert(gc_list_is_empty(&gcstate->old[visited].head));
1421-
gcstate->work_to_do = 0;
14221425
gcstate->phase = GC_PHASE_MARK;
14231426
}
14241427

@@ -1450,9 +1453,7 @@ move_all_transitively_reachable(WorkStack *stack, PyGC_Head *visited, int visite
14501453
// Transitively traverse all objects from reachable, until empty
14511454
Py_ssize_t objects_marked = 0;
14521455
while (stack->top != NULL) {
1453-
/* Pop from the stack, to do depth first traversal */
1454-
PyGC_Head *gc = stack->top;
1455-
stack->top = _PyGCHead_PREV(gc);
1456+
PyGC_Head *gc = pop_from_stack(stack);
14561457
assert(gc_old_space(gc) == visited_space);
14571458
gc_list_append(gc, visited);
14581459
objects_marked++;
@@ -1513,7 +1514,6 @@ mark_global_roots(PyInterpreterState *interp, PyGC_Head *visited, int visited_sp
15131514
WorkStack stack;
15141515
stack.top = NULL;
15151516
stack.visited_space = visited_space;
1516-
Py_ssize_t objects_marked = 0;
15171517
MOVE_UNVISITED(interp->sysdict, &stack, visited_space);
15181518
MOVE_UNVISITED(interp->builtins, &stack, visited_space);
15191519
MOVE_UNVISITED(interp->dict, &stack, visited_space);
@@ -1526,7 +1526,7 @@ mark_global_roots(PyInterpreterState *interp, PyGC_Head *visited, int visited_sp
15261526
MOVE_UNVISITED(types->for_extensions.initialized[i].tp_dict, &stack, visited_space);
15271527
MOVE_UNVISITED(types->for_extensions.initialized[i].tp_subclasses, &stack, visited_space);
15281528
}
1529-
objects_marked += move_all_transitively_reachable(&stack, visited, visited_space);
1529+
Py_ssize_t objects_marked = move_all_transitively_reachable(&stack, visited, visited_space);
15301530
assert(stack.top == NULL);
15311531
return objects_marked;
15321532
}
@@ -1547,12 +1547,11 @@ mark_at_start(PyThreadState *tstate)
15471547
static intptr_t
15481548
assess_work_to_do(GCState *gcstate)
15491549
{
1550-
/* The amount of work we want to do depends on three things.
1550+
/* The amount of work we want to do depends on two things.
15511551
* 1. The number of new objects created
1552-
* 2. The growth in heap size since the last collection
1553-
* 3. The heap size (up to the number of new objects, to avoid quadratic effects)
1552+
* 2. The heap size (up to twice the number of new objects, to avoid quadratic effects)
15541553
*
1555-
* For a steady state heap, the amount of work to do is three times the number
1554+
* For a large, steady state heap, the amount of work to do is three times the number
15561555
* of new objects added to the heap. This ensures that we stay ahead in the
15571556
* worst case of all new objects being garbage.
15581557
*
@@ -1564,13 +1563,13 @@ assess_work_to_do(GCState *gcstate)
15641563
scale_factor = 2;
15651564
}
15661565
intptr_t new_objects = gcstate->young.count;
1567-
intptr_t max_heap_fraction = new_objects*3/2;
1566+
intptr_t max_heap_fraction = new_objects*2;
15681567
intptr_t heap_fraction = gcstate->heap_size / SCAN_RATE_DIVISOR / scale_factor;
15691568
if (heap_fraction > max_heap_fraction) {
15701569
heap_fraction = max_heap_fraction;
15711570
}
15721571
gcstate->young.count = 0;
1573-
return new_objects + heap_fraction * 2;
1572+
return new_objects + heap_fraction;
15741573
}
15751574

15761575
static void
@@ -1606,7 +1605,7 @@ gc_collect_increment(PyThreadState *tstate, struct gc_collection_stats *stats)
16061605
Py_ssize_t increment_size = move_all_transitively_reachable(&working, &increment, gcstate->visited_space);
16071606
gc_list_validate_space(&increment, gcstate->visited_space);
16081607
assert(working.top == NULL);
1609-
while (increment_size < gcstate->work_to_do) {
1608+
while (increment_size < gcstate->work_to_do * 2) {
16101609
if (gc_list_is_empty(not_visited)) {
16111610
break;
16121611
}
@@ -1626,7 +1625,7 @@ gc_collect_increment(PyThreadState *tstate, struct gc_collection_stats *stats)
16261625
gc_collect_region(tstate, &increment, &survivors, stats);
16271626
gc_list_merge(&survivors, visited);
16281627
assert(gc_list_is_empty(&increment));
1629-
gcstate->work_to_do -= increment_size;
1628+
gcstate->work_to_do -= increment_size/2;
16301629

16311630
add_stats(gcstate, 1, stats);
16321631
if (gc_list_is_empty(not_visited)) {
@@ -1661,6 +1660,7 @@ gc_collect_full(PyThreadState *tstate,
16611660
gcstate->old[0].count = 0;
16621661
gcstate->old[1].count = 0;
16631662
completed_scavenge(gcstate);
1663+
gcstate->work_to_do = -gcstate->young.threshold;
16641664
_PyGC_ClearAllFreeLists(tstate->interp);
16651665
validate_spaces(gcstate);
16661666
add_stats(gcstate, 2, stats);

0 commit comments

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