(READY FOR REVIEW)Garbage collect: A stop-the-world cycle collector#4180

discord9

That might be extend to be a on-the-fly version. Based on #4158

Summary of GC Algorithm

the algorithm store a buffer of object thats' "possible roots" of garbage cycles(i.e. if a object is decrement but not to zero, its a possible root) then, during gc, algorithm have three main phase:

iterate over this buffer, free objects of rc==0.
then in next phase tracing other object(whose rc>0) and do a "trial decrement" to all of its childrens, so to remove all the "internal reference" in the graph, so whats left is external reference, so by now,object with rc==0 is safe to be collected
restore everyone elses rc, only drop garbage found from previous phase, note in here we first do a drop in place for every garbage then dealloc everything to prevent UB from deref to deallocated objects

Progress

basic cycle collector algorithm(stop the world version)
necessary trait and cond comp flag and feature
impl GcTrace for all builtin types(Some type's trace() still need tweak, see below, still have some not impl)
rebase off the newest main(for rustc 1.64.0 update)
export gc() as a python function(in the stdlib), now invoke gc() in python will force a cycle collect to happen, return number of cyclic garbage collected(and freed)
test(especially for threading)
bug: I use wrong drop in collect_white, should drop PyInner<T>, but I drop PyInner<Erased>, need correct that.(Fixed)
bug: PyInner is deallocated early before PyWeak release
bug: gc in drop() sometimes seems to cause deadlock(Fix by putting gc() to instruction exec loop)
use PyObject directly instead of dyn dispatch in gc
move gc() to its' own module in stdlib
find out why stdlib::io::_io::BufferedReader(and other types in _io module) keeps double free
rewrite commits
drop header later to prevent UB
run __del__, drop, dealloc separately to prevent UB
change back to use PyMutex instead of PyRwLock(which is unacceptly slow)
use proc macro to impl trace for datatype
compact header's most field into one byte
bug with weak ref

future features for GC

use MemBalancer to determine when to gc(actually tried on a new branch, but I am having difficulty sampling memory usage&memory deallocate rate so not having a very good effect)
found out how to make optional trait bound without using typeid&macro(which make it hard to extend)

GC condition

gc will be triggered if the internal buffer(roots) have exceed 10007(Just a random reasonably large number) element and at least 100ms after last gc, that means after 10007 different objects get decref after last gc, a new gc will be trigger, gc() is only called in the loop of executing instruction, but also reexport a gc() to stdlib so one can call gc() from Python side(which will force a gc regardless of above conditon).
stop-the-world is impl by try to blocking on a pausing Mutex owned by gc whenever try to deref PyObjectRef/PyRef/Py

Basic ideas

cycle collector algorithm:

stop the world, and remove internal reference
found out those with zero ref(meaning they are cyclic garbage), mark them for later free, restore others' ref count.
free those marked object(also unpause the world), also for those marked object form a cycle, some check is done to make sure no double drop or deallocate happen

Data struct

#[repr(C)]
struct PyInner<T> {
    #[cfg(not(feature = "gc"))]
    ref_count: RefCount,
    #[cfg(feature = "gc")]
    header: GcHeader,
    ....

/// Garbage collect header, containing ref count and other info, using repr(C) to stay consistent with PyInner 's repr
#[repr(C)]
pub struct GcHeader {
    ref_cnt: PyAtomic<usize>,
    color: PyMutex<Color>,
    buffered: PyMutex<bool>,
    pub exclusive: PyMutex<()>,
    pub gc: PyRc<CcSync>
}

Example

for code as below:

tot = 0
runs = 16000
for i in range(runs):
    a = [0]
    b = [a]
    a[0] = b
    del a
    del b
    a = {}
    b = {}
    a[0] = b
    b[0] = a
    del a
    del b

With and without gc, the memory usage is(run on a win10(19044.2006) with rustc 1.64.0, might vary between different runs):

loop	mem with gc(MB)	without gc(MB)
0	13.29	8.82
1000	13.49	10.36
2000	13.76	11.76
3000	14.29	13.32
4000	14.29	14.45
5000	14.31	16.32
6000	14.31	17.24
7000	14.31	18.32
8000	14.31	19.45
9000	15.36	21.38
10000	15.36	22.45
11000	15.26	23.71
12000	15.26	24.63
13000	15.26	25.97
14000	15.26	27.36
15000	15.26	28.36

currently `GcTrace`d types are:

// builtin types
// PyRange, PyStr is acyclic
PyBoundMethod,
PyDict,
PyEnumerate,
PyFilter,
PyFunction,
PyList,
PyMappingProxy,
PyProperty,
PySet,
PySlice,
PyStaticMethod,
PySuper,
PyTraceback,
PyTuple,
// PyType, (strange bug, see PyType's trace() for detail)
PyZip,
// misc
PyCell,
// iter in iter.rs
PySequenceIterator,
PyCallableIterator,
// iter on types
// PyList's iter
PyListIterator,
PyListReverseIterator,
// PyTuple's iter
PyTupleIterator,
// PyEnumerate's iter
PyReverseSequenceIterator,
// PyMemory's iter
PyMemoryViewIterator,
// function/Arg protocol
ArgCallable,
ArgIterable,
ArgMapping,
ArgSequence,
// protocol
// struct like
PyBuffer,
PyIter,
// FIXME(discord9): confirm this is ok to do
PyIterIter<T>,
PyIterReturn,
PyMapping,
PyNumber,
PySequence

discord9

A simple example of collecting cycle ref of PyList(note the line of collect cyclic garbage composed of two object(a and b in this case)):

a= [0]
b = [a]
a[0] = b

fanninpm

Rust 1.64 came out a few hours ago, so there are some new compilation warnings and Clippy lints to deal with in a separate PR (#4182). Once that PR is merged, it might be a good idea to rebase this branch on top of a fresh copy of main.

discord9

Just realize I still need make some change to make gc adopt to threading, need to think about it.
edited: I am using a mutex to stop the world, which have serveal performance issue, considering changing to PyRwLock instead, too much todo, change to draft for now
edited1: done

discord9

bug: might need to store the number of PyWeak ref count to prevent premature dealloc in heap and access violation. Also PyWeak itself is storing a PyObjectRef which keep the object from drop, some change need to be made to change that
edited: still haven't fix those failed test case now
edited1: done (basically, see progress section

fanninpm

gc will be triggered if the internal buffer(roots) have exceed 100 element(could come up with better condition in the future)

CPython has a generational garbage collector with a total of three generations. The first generation has a threshold of 700 objects, and the next two have a threshold of 10 objects each. ¹ I imagine that bumping the current threshold from 100 up to 700 objects may mitigate some of the performance decrease you're currently observing.

https://devguide.python.org/internals/garbage-collector/index.html#optimization-generations ↩

discord9

Sorry for the messy commit logs, will reword them later.
edited: sort into six commits for the ease of code review

fanninpm

When happens when you compile this with the --no-default-features flag? I suspect there may be a few compilation errors with stdlib/src/gc.rs.

discord9

Yes, just realize that, gonna fix it, also still debugging on the dead lock&double dealloc issue, my code is still very faulty
edited: done, basically limit trace to those object that is GcTrace and dead lock disappear.

youknowone

@coolreader18 do you have advices?

discord9

Might found a bug related to the old ref count system: #4238 ,still trying to find a fix
Edited: solved

discord9

Using PyRwLock is indeed very slow, might need to found out a way to trace PyMutex properly

DimitrisJim

I've slightly taken a peak at the paper this is based on, I'm guessing the two improvements it mentions have been implemented, right? I.e, using the buffered flag to not re-add it to the collector list and checking the current items in the collector as a single graph and not as distinct components.

discord9

I've slightly taken a peak at the paper this is based on, I'm guessing the two improvements it mentions have been implemented, right? I.e, using the buffered flag to not re-add it to the collector list and checking the current items in the collector as a single graph and not as distinct components.

Yes, this is the main improvement here, I write a buffered field for every object and there is a roots vec, actually the name of methods is corresponding between paper and the actual code

coolreader18

Thank you so much for working on this! I started this a week or 2 ago and then it slipped my mind after I took a break about halfway through looking at stuff. I haven't looked at the actual gc code, and though I'd really like to, to be honest I'm not sure I'll have the bandwidth to do so. If no other maintainers feel able to either, worst case we mark it as a sort of experimental feature, but the test suite passing fine gives me confidence that it's working more or less as it should. It's not like there haven't already been multithreaded gc issues even without the tracing gc, lol.

DimitrisJim

Maybe we can create a separate CI check that runs the GC with a select few python test files? The idea is to at least have it in and running relevant tests on it while not slowing down the total runtime.

killme2008

Is this PR still in review? @youknowone @discord9

youknowone

I am really sorry for late review.
I am not understanding how this gc is working - and I seem to not have enough time to get it before finish review - but I'd like to merge it as an optional feature and a good starting point to enhance gc better in future.
But before merging this change, I hope to minimize changes of CPython-originated code because changed CPython code will be easily forgotten from future developers and it even might be broken when the future enhancement is correct but not compatible with this change.

discord9

I am really sorry for late review. I am not understanding how this gc is working - and I seem to not have enough time to get it before finish review - but I'd like to merge it as an optional feature and a good starting point to enhance gc better in future. But before merging this change, I hope to minimize changes of CPython-originated code because changed CPython code will be easily forgotten from future developers and it even might be broken when the future enhancement is correct but not compatible with this change.

I am thinking about update document on how this GC works, perhaps even add it to documents of RustPython?

youknowone

That will be great in future. I think separating gc feature and reduce effect to non-gc build as it was will be good enough for now.

youknowone

i rebased it on main branch

discord9

i rebased it on main branch

I will fix the CI

feat: add double drop check in debug mode fix: use Mutex instead of PyMutex in `ID2TYPE` refactor: cfg cond for `Drop` trait instead feat: add `Trace` trait feat: trace RwLock right&trace tuple feat: `Trace` for `PyDict` feat: `Trace` on `PyIter`&`PyIterReturn`&`PyIterIter` feat: `Trace` on PyEnumerate feat: `Trace` on `ArgCallable` `ArgIterable` `ArgMapping` `ArgSequence` feat: `Trace` on `IterStatus` `PySequenceIterator` `PyCallableIterator` `PositionIterInternal` feat: `Trace` on `PyReverseSequenceIterator` feat: `Trace` on `PyTuple` `PyTupleIterator` `PyTupleTyped` feat: `Trace` on `PyFilter` `PyFunction` `PyBoundMethod` feat: `Trace` on `PyCell` feat: `Trace` on `PyList` `PyListIterator` `PyListReverseIterator` feat: `Trace` on `PyMap` `PyMappingProxy` `MappingProxyInner` feat: `Trace` on PyMemoryViewNewArgs, PyMemoryViewIterator feat: `Trace` on PyProperty, PySet, PySetInner feat: `Trace` on PySlice, PyStaticMethod feat: `Trace` on FuncArgs, KwArgs, PosArgs, OptionalArg feat: `Trace` on PySuper, PySuperNewArgs feat: `Trace` on `PyTraceback` feat: `Trace` for PyBaseException, PyType, PyUnion feat: `Trace` on PyWeakProxy, PyZip, PyBuffer feat: `Trace` on PyMapping, PyNumber, PySequence feat: add `list_traceable` macro fix: right lifetime for `TracerFn` feat: `trace` PyObjectRef&PyRef feat: garbage cycle collector fix: put drop_only in different loop feat: core algorithm of garbage collect feat: add drop_only&dealloc_only to vtable feat: modify core.rs to use gc style: cargo fmt feat: add `try_gc`& gc per frame feat: add `collect` in gc module fix: set black when safe_inc fix: check if is gc-ing in `should_gc` refactor: cfg(gc) for `Drop` trait fix: not add to roots multiple times fix: add judge for if dropped doc: add TODO fix: prevent dealloc cycle garbage early fix: `partially_drop` header later fix: add dealloc guard for deref fix: run `__del__`&drop separately feat: more lock to gc&drop check feat: make gc less freq fix: cfg compile&support attr in partially_drop feat: `pytrace` macro feat: use `#[pytrace]` in some types feat: compact header feat: change gc cond to 10007 obj cnts fix: trace `PyRange` fix: drop ref vtable before dealloc to prevent UB fix: debug check&cfg cond&clippy fix: add ref only after `__del__` is done feat: trace(unsafely ) PyMutex feat: prevent trace PyMutex when not gc feat: change `PyRwlock` back to `PyMutex` fix: testcase test_reference_loop test_unique_composite refactor: early exit of collect_cycles fix: cfg cond feat: gc pause warn msg when wait too long fix: not run __del__ in cycles fix: expected failure for test_unique_composite fix: allow test_ioctl_signed_unsigned_code_param feat: split `drop` to `del`&`weakref` fix: lock cond fix: pause cond so high freq gc not halt all refactor: put impl Collector together feat: drop weak_list later feat: unlock gc pause lock fairly feat: print progress for two long test feat: adjust lock order&not panic fix: let obj handle its weakref's dealloc fix: check stack before pop fix: not leak weakref log: remove some false alarm fix: cfg flag for cond compile fix: cfg flag for no-default-feature fix: use non-block incref test: change gc to 1ms&exit all if wait too long fix: INCREF done right&not gc until last gc done feat: add `gc` feature to root crate doc: TODO for PEP442 del in cycle fix: temporaily add one more `gc.collect()` test: add gc feature in CI refactor: make `mark/scan_roots` associated fn refactor: `free_cycles` fn test: flush progress prompt docs: add TODO for modified testcases refactor: header state's type feat: drop_only log: gc info clippy: drop_only allow unused refactor: rename `gc` feature to `gc_bacon` refactor: remove `allow(unused)` feat: `MaybeTrace` trait feat: add `trace` Meta for `pyclass` proc macro feat: cfg cond flag for `MaybeTrace` feat: add `trace` in vtable fix: add`#[pyclass(trace)` for manual impl trace fix: elide null check in vtable&CR refactor fix: change name in CI tests feat: not use gc in wasm refactor: accord to Code Review doc&fix: explain gc&fix macro fix: test_sys_setprofile

tisonkun

@discord9 @youknowone do we have some blockers here? Or it's waiting for a rebase and we generally agree on its merge?

discord9

@discord9 @youknowone do we have some blockers here? Or it's waiting for a rebase and we generally agree on its merge?

Currently, an old bug stemming from code predating the implementation of garbage collection is causing memory corruption because the garbage collector is indeed collecting that memory. I will open a new pull request once I have fixed those bugs and can reliably pass continuous integration.

youknowone

@discord9 I am sorry miss the comment. I wish we finally could merge it. If there is any PyTraverse update, could we merge it first? Regardless how GC designed later, it will be useful.

killme2008

@discord9 I am sorry miss the comment. I wish we finally could merge it. If there is any PyTraverse update, could we merge it first? Regardless how GC designed later, it will be useful.

+1. It's a first step and it can be improved in future. cc @discord9

discord9 changed the title ~~feat: A simple stop-the-world cycle collector(Draft)~~ Sep 22, 2022

discord9 mentioned this pull request Sep 23, 2022

[RFC] GC: Both Stop-the-World and On-the-fly #4158

Open

fanninpm mentioned this pull request Sep 23, 2022

does gc implemented???? #4181

Closed

fanninpm reviewed Sep 23, 2022

View reviewed changes

discord9 changed the title ~~feat: A simple stop-the-world cycle collector~~ Sep 24, 2022

discord9 force-pushed the main branch from 711e5a2 to 6cf841b Compare September 24, 2022 14:28

discord9 marked this pull request as ready for review September 24, 2022 15:09

discord9 marked this pull request as draft September 25, 2022 14:45

lastmjs mentioned this pull request Oct 3, 2022

Garbage collection demergent-labs/kybra#35

Open

3 tasks

stephanemagnenat mentioned this pull request Oct 11, 2022

[RFC] Support embedding and sandboxing untrusted code #4210

Open

discord9 force-pushed the main branch from 4bc2d5f to 000aa85 Compare October 11, 2022 10:33

This comment was marked as resolved.

Sign in to view

discord9 force-pushed the main branch from befc7d2 to a70720c Compare October 19, 2022 15:14

discord9 force-pushed the main branch from f7cf348 to 3a79613 Compare November 4, 2022 02:47

discord9 changed the title ~~feat: Garbage collect: A simple stop-the-world cycle collector~~ Nov 4, 2022

discord9 changed the title ~~feat: Garbage collect: A simple stop-the-world cycle collector(Redraft)~~ Nov 4, 2022

discord9 changed the title ~~Garbage collect: A simple stop-the-world cycle collector(Redraft)~~ Nov 4, 2022

discord9 marked this pull request as ready for review November 4, 2022 11:57

discord9 changed the title ~~Garbage collect: A simple stop-the-world cycle collector(redrafted)~~ Nov 5, 2022

coolreader18 reviewed Dec 7, 2022

View reviewed changes

discord9 mentioned this pull request Dec 30, 2022

chore: Update RustPython(With GC) GreptimeTeam/greptimedb#809

Merged

2 tasks

youknowone reviewed Feb 13, 2023

View reviewed changes

youknowone force-pushed the main branch from 45e1bac to 185d167 Compare March 7, 2023 19:55

discord9 force-pushed the main branch from a98b40a to 234d5fe Compare March 23, 2023 06:01

youknowone force-pushed the main branch from c5f8841 to 5f802d2 Compare March 27, 2023 07:16

youknowone reviewed Mar 27, 2023

View reviewed changes

youknowone force-pushed the main branch 3 times, most recently from de08f82 to 0c11636 Compare March 28, 2023 15:36

discord9 and others added 4 commits April 17, 2023 22:03

minimize diff

6e88691

isolate gc from bare object module

823a80f

fix: check buf in drop_slow

9ed5137

discord9 force-pushed the main branch from 0c11636 to 9ed5137 Compare May 5, 2023 07:29

discord9 closed this Feb 20, 2024

tisonkun mentioned this pull request Apr 23, 2024

Python UDF Support GreptimeTeam/greptimedb#3777

Closed

3 tasks

arihant2math mentioned this pull request Jan 28, 2025

Partial Garbage Collection Implementation #5493

Draft

Conversation

discord9 commented Sep 22, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary of GC Algorithm

Progress

future features for GC

GC condition

Basic ideas

Data struct

Example

currently GcTraced types are:

Uh oh!

discord9 commented Sep 23, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

fanninpm commented Sep 23, 2022

Uh oh!

discord9 commented Sep 25, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

discord9 commented Sep 26, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

fanninpm commented Sep 27, 2022

Footnotes

Uh oh!

discord9 commented Oct 8, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

fanninpm commented Oct 11, 2022

Uh oh!

discord9 commented Oct 12, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

This comment was marked as resolved.

youknowone commented Oct 16, 2022

Uh oh!

discord9 commented Oct 22, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

discord9 commented Nov 7, 2022

Uh oh!

DimitrisJim commented Nov 17, 2022

Uh oh!

discord9 commented Nov 18, 2022

Uh oh!

coolreader18 left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

DimitrisJim commented Jan 1, 2023

Uh oh!

killme2008 commented Feb 8, 2023

Uh oh!

youknowone left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

discord9 commented Feb 20, 2023

Uh oh!

youknowone commented Feb 20, 2023

Uh oh!

youknowone commented Mar 7, 2023

Uh oh!

discord9 commented Mar 8, 2023

Uh oh!

tisonkun commented Feb 20, 2024

Uh oh!

discord9 commented Feb 20, 2024

Uh oh!

youknowone commented Apr 23, 2024

Uh oh!

killme2008 commented Apr 23, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

discord9 commented Sep 22, 2022 •

edited

Loading

currently `GcTrace`d types are:

discord9 commented Sep 23, 2022 •

edited

Loading

discord9 commented Sep 25, 2022 •

edited

Loading

discord9 commented Sep 26, 2022 •

edited

Loading

discord9 commented Oct 8, 2022 •

edited

Loading

discord9 commented Oct 12, 2022 •

edited

Loading

discord9 commented Oct 22, 2022 •

edited

Loading

coolreader18 left a comment •

edited

Loading

youknowone left a comment •

edited

Loading