-
Notifications
You must be signed in to change notification settings - Fork 1.3k
[RFC] GC: Both Stop-the-World and On-the-fly #4158
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.
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
Comments
Cool, i think a synchronous version is a good start. |
I want to comment:
|
I think it's totally doable! I have build a simple gc(stop-the-world version, a cycle collector that rely on ref count) without mmtk(https://github.com/discord9/RustPython based on https://github.com/fitzgen/bacon-rajan-cc, still a WIP), but migrate to mmtk sound like a great idea! edit:current version basically replace |
Uh oh!
There was an error while loading. Please reload this page.
Draft PR: #4180
Summary
I propose we implement a cycle collector for our rustPython RefCount garbage collection system based on Bacon etc.'s work in this two paper:
Detailed Explanation
The synchronous cycle collector is easier to impl, I suggest we implement a synchronous verison of cycle collector for proof of Concept, then modfiy it to a On-the-Fly version.
Synchronous Cycle Collection
The algo in "Concurrent Cycle Collection in Reference Counted Systems" is O(N + E) wrost-case time for collection at most.
For an object T in its' header there need fields denoted buffered(T), color(T),and RC(T). Where:
Pseudocode and Explanation
In this section I just ref to paper because it explain much better than me, the basic idea is to first scan for possible cycles, then check for actual cycles:
There is also concurrent cycle collection, but that is not the main point today. Because the on-the-fly version is better both in performance and ease to implement.
Efficient On-the-Fly Cycle Collection
The basic idea is to use a "sliding view" method(which is a bit like "Copy on write"), and create a stable snapshot by adding a "LogPointer" to record the original status of object to create a virtual snapshot of the heap for cycle collection.
Data Struct
We can use work in #2908 for object layout, and add two new feature:
"gc"
and"on_the_fly_cc"
which depend on"gc"
feature:And add a
GcTrace
trait should be implement on every type require GC.edited: in#4180 add a field to PyInner instead which is clearer and easier to impl.
Drawbacks, Rationale, and Alternatives
Alternative: impl #2908's CPython GC.
The text was updated successfully, but these errors were encountered: