Skip to content

Incremental "mark alive" pass for cyclic GC #126511

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
nascheme wants to merge 7 commits into from
Closed

Incremental "mark alive" pass for cyclic GC #126511

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
7 commits
Select commit Hold shift + click to select a range
bbbe019
wip: mark alive with list
nascheme Oct 19, 2024
4940097
wip: progress
nascheme Oct 20, 2024
84d4053
wip: working
nascheme Oct 20, 2024
4f69ead
wip: add timing stats
nascheme Oct 21, 2024
04c2dbf
wip: improve comments
nascheme Oct 21, 2024
ec98e57
wip: add timing stats for full collections
nascheme Oct 21, 2024
12ceba2
Add WITH_GC_MARK_ALIVE and WITH_GC_TIMING_STATS
nascheme Oct 23, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
wip: improve comments
  • Loading branch information
@nascheme
nascheme committed Oct 21, 2024
commit 04c2dbfc39ca972e50f99e03934b89cccb4c36bd
8 changes: 8 additions & 0 deletions Include/internal/pycore_gc.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -291,12 +291,19 @@ struct gc_mark_state {
Py_ssize_t old_size;
/* Number of alive objects found in oldest generation */
Py_ssize_t old_alive_size;
/* The phase of the mark process */
int mark_phase;
/* Number of incremental mark steps done */
int mark_steps;
/* Number of steps available before full collection */
int mark_steps_total;
/* Total time spent inside cyclic GC */
PyTime_t gc_total_time;
/* Time spent inside incremental mark part of cyclic GC */
PyTime_t gc_mark_time;
/* Maximum GC pause time */
PyTime_t gc_max_pause;
/* Total number of times GC was run */
PyTime_t gc_runs;
};

Expand All @@ -322,6 +329,7 @@ struct _gc_runtime_state {
PyObject *garbage;
/* a list of callbacks to be invoked when collection is performed */
PyObject *callbacks;
/* state for the incremental "mark alive" logic */
struct gc_mark_state mark_state;

/* This is the number of objects that survived the last full
Expand Down
24 changes: 13 additions & 11 deletions Python/gc.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -57,11 +57,11 @@ typedef struct _gc_runtime_state GCState;
#define GENERATION_AUTO (-1)

// phases of incremental mark alive process
#define MARK_PHASE_INIT 1
#define MARK_PHASE_STEP 2
#define MARK_PHASE_DONE 3
#define MARK_PHASE_INIT 1 // start of new marking pass
#define MARK_PHASE_STEP 2 // incremental marking steps (done on each gen 0 collection)
#define MARK_PHASE_DONE 3 // marking has finished, wait for next full collection

#if 1 // gc timing
#if 1 // gc timing statistics (needs cleanup)
//
#define QUANTILE_COUNT 5
#define MARKER_COUNT (QUANTILE_COUNT * 3 + 2)
Expand Down Expand Up @@ -248,6 +248,7 @@ P2Engine gc_timing;

#endif // gc timing

// return True if object is part of the old (gen2) set
static inline int gc_is_old(PyGC_Head *gc) {
return ((gc->_gc_prev & _PyGC_PREV_MASK_OLD) != 0);
}
Expand Down Expand Up @@ -1269,6 +1270,7 @@ show_stats_each_generations(GCState *gcstate)
buf, gc_list_size(&gcstate->permanent_generation.head));
}

// set the "old" flag on all objects in the old (gen 2) list
static Py_ssize_t
mark_old(PyGC_Head *head) {
Py_ssize_t n = 0;
Expand All @@ -1279,13 +1281,11 @@ mark_old(PyGC_Head *head) {
return n;
}

struct mark_state {
PyGC_Head todo;
Py_ssize_t alive; // number of objects found alive
};

static int visit_reachable_old(PyObject *op, PyGC_Head *todo);

// Called on objects known to be alive (due to being reachable from known
// roots). Move objects to the 'old_alive' list. They will be excluded
// from the next full collection of old.
static void
propogate_old_reachable(PyObject *op, PyGC_Head *todo)
{
Expand All @@ -1308,6 +1308,7 @@ visit_reachable_old(PyObject *op, PyGC_Head *todo)
return 0;
}

// do one step of incremental "mark alive" processing
static void
mark_alive_step(PyThreadState *tstate, PyGC_Head *old_head)
{
Expand Down Expand Up @@ -1377,6 +1378,7 @@ print_gc_times(GCState *gcstate)
);
}

// Run incremental "mark alive" process, as required.
static void
maybe_mark_alive(PyThreadState *tstate, int generation, _PyGC_Reason reason)
{
Expand Down Expand Up @@ -1406,8 +1408,8 @@ maybe_mark_alive(PyThreadState *tstate, int generation, _PyGC_Reason reason)
else {
if (generation == OLD_GENERATION) {
float f = ((float)gcstate->mark_state.old_alive_size) / gcstate->mark_state.old_size;
fprintf(stderr, "doing full auto collection %.2f\n", f);
fprintf(stderr, "steps %d %d\n", gcstate->mark_state.mark_steps, gcstate->mark_state.mark_steps_total);
fprintf(stderr, "gc full auto collection %.2f\n", f);
fprintf(stderr, "gc steps needed=%d available=%d\n", gcstate->mark_state.mark_steps, gcstate->mark_state.mark_steps_total);
print_gc_times(gcstate);
gcstate->mark_state.mark_phase = MARK_PHASE_INIT;
}
Expand Down
3 changes: 1 addition & 2 deletions Python/pylifecycle.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1151,6 +1151,7 @@ run_presite(PyThreadState *tstate)
}
#endif

extern void _PyGC_Freeze(PyInterpreterState *interp);

static PyStatus
init_interp_main(PyThreadState *tstate)
Expand Down Expand Up @@ -2217,8 +2218,6 @@ Py_Finalize(void)
(void)_Py_Finalize(&_PyRuntime);
}

extern void _PyGC_Freeze(PyInterpreterState *interp);

/* Create and initialize a new interpreter and thread, and return the
new thread. This requires that Py_Initialize() has been called
first.
Expand Down