René's URL Explorer Experiment

Title: (READY FOR REVIEW)Garbage collect: A stop-the-world cycle collector by discord9 · Pull Request #4180 · RustPython/RustPython · GitHub

Open Graph Title: (READY FOR REVIEW)Garbage collect: A stop-the-world cycle collector by discord9 · Pull Request #4180 · RustPython/RustPython

X Title: (READY FOR REVIEW)Garbage collect: A stop-the-world cycle collector by discord9 · Pull Request #4180 · RustPython/RustPython

Description: 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, but I drop PyInner, 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¯o(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 { #[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, color: PyMutex, buffered: PyMutex, pub exclusive: PyMutex<()>, pub gc: PyRc } 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 GcTraced 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, PyIterReturn, PyMapping, PyNumber, PySequence

Open Graph Description: 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 obje...

X Description: 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&#39; &quot;possible roots&quot; of garbage cycles(i....

Opengraph URL: https://github.com/RustPython/RustPython/pull/4180

X: @github

direct link

Domain: github.com

Links:

Viewport: width=device-width