Move GC to a separate thread

[iritkatriel]

Antoine started working on this in PEP 556.
@pitrou, can you update us where you are with this idea?

[pitrou]

I abandoned work on it. The implementation worked, but there was an obscure crash that I didn't manage to diagnose.
I believe @pablogsal was interested at some point, but he probably got distracted :-)
You should feel free to take it up.

[pitrou]

Note the challenge is to run the test suite with threaded GC enabled:

diff --git a/Python/pylifecycle.c b/Python/pylifecycle.c
index 1467527da3..d6e8129849 100644
--- a/Python/pylifecycle.c
+++ b/Python/pylifecycle.c
@@ -901,7 +901,7 @@ _Py_InitializeMainInterpreter(PyInterpreterState *interp,
     }
 
     /* XXX allow setting GC mode with an env var? */
-    if (_PyGC_SetThreaded(0)) {
+    if (_PyGC_SetThreaded(1)) {
         Py_FatalError("_PyGC_SetThreaded failed");
     }
 

[iritkatriel]

Thanks. I see the crash in test__xxsubinterpreters. Also a few other tests are failing due to what looks like finalizers not being called. I'll try to understand what you did.

[pablogsal]

Thanks. I see the crash in test__xxsubinterpreters. Also a few other tests are failing due to what looks like finalizers not being called. I'll try to understand what you did.

I actually ended fixing some of the finalizer bugs, but I need to find where i stored that work 😅

In any case, is interesting to note that my benchmarks showed a little slowdown in general (although not much). I suspect this is due to the extra context switching, but in any case I don't think this will actually end giving us any speedups, although it will potentially help with the problems described in PEP 556

[pitrou]

Speedups were not the goal indeed, but to make the GC context more predictable (instead of GC-induced code such as finalizers running at potentially any point). Even latency would probably not be improved very much, because of the GIL (I don't know how workable it would be to release the GIL at some points of garbage collection).

[pitrou]

Note that this GC execution context issue is actually extremely serious for real-world code (anything with complex finalizers with side effects). It also motivated the creation of the SimpleQueue object, which can help alleviate the problem, but at the cost of additional complexity (and potential bugs or performance issues as well).

[pablogsal]

Note that this GC execution context issue is actually extremely serious for real-world code (anything with complex finalizers with side effects).

Yep, that's why I was interested in pushing it in the first place but got side-tracked by the parser work and extinguish the fires of the 3.9 release :(

[gvanrossum]

OTOH in the context of "Faster CPython" the idea was to make things faster by letting a second core handle (most of) the GC work -- this is what some other languages do. But it would require something like the Gilectomy first.

[pitrou]

Right, but those "other languages" are generally fully GC-based. In CPython, much of the cost of reclaiming memory is born by regular reference counting.

[markshannon]

Regardless of where we run the "GC", i.e. the cycle finder and breaker, it would make sense to improve the general decref/dealloc code.

We want to:

• maintain the invariant that all live objects have refcount > 0
• not blow the C stack
• make dealloc as efficient as we reasonably can.

To keep dealloc efficient we want to free memory for simple objects without having to chase function pointers, and not to have to worry about finalizers and weakrefs when clearing internal references.
We also want to handle the "trashcan" mechanism in dealloc, so that we don't need to handle it repeatedly in an ad-hoc fashion in many different places.

Something like this (in C flavoured Python):

@inline
def Py_DECREF(obj):
    # Refcount never reaches 0 unless object is genuinely unreachable.
    if obj.refcount == 1:
        dealloc(obj)
    else:
        obj.refcount -= 1

def dealloc(obj):
    if has_weakrefs(obj) or needs_finalizing(obj):
        finalizer_list.append(obj)
    elif has_internal_references(obj):
        recursive_clear_and_free(obj)
    else:
        # Objects that cannot refer to other objects e.g. ints, strs.
        # Implicitly reduce refcount to zero.
        free(obj)

def recursive_clear_and_free(obj):
     # obj cannot be "resurrected" as there are no references to it; strong or weak.
    if tstate.recursive_dealloc > TRASHCAN_LIMIT: # Currently limit is 50?
        trashcan_list.append(obj)
        return
    tstate.recursive_dealloc += 1
    for offset in obj.__class__.layout:
        item = obj[offset]
        obj[offset] = NULL
        Py_DECREF(item)
    assert obj.refcount == 1
    # Implicitly reduce refcount to zero.
    free(obj)
    tstate.recursive_dealloc -= 1
    if tstate.recursive_dealloc == 0:
        while trashcan_list:
            obj = trashcan_list.pop()
            Py_DECREF(obj)
        if finalizer_list and not RUN_FINALIZERS_IN_THREAD:
             clear_finalizer_list()

def clear_finalizer_list():
    while finalizer_list:
        item = finalizer_list.pop()
        if has_weak_refs(item):
            do_weak_ref_callbacks(item)
        if has_finalizer(item):
            finalize(item)
        Py_DECREF(item)
    

if RUN_FINALIZERS_IN_THREAD:
    def thread_run_clear_finalizer_list():
        while True:
            clear_finalizer_list()
            #sleep until there is something to do

I have done absolutely no testing on the above. So it will be incorrect. Hopefully the general idea is clear though.

[iritkatriel]

@markshannon Arranging gc like that would make it more predictable but could slow it down, right? (I’m assuming that trashcan only kicks in after 50 because it’s slower so not worth it for small chains.)

[markshannon]

I think it should be quicker as type-specific dealloc code doesn't need worry about trashcans, finalizers or resurrection.

Maintaining a stack of objects, and making deallocation iterative rather than recursive should be even quicker. Pushing a single pointer is going to faster than making a C call.

[iritkatriel]

I'm assuming you meant that the last line of clear_finalizer_list is obj.refcount -= 1 rather than Py_DECREF(item) recursively.

I think this can get complicated because we need to make sure that we don't add the same object twice to the finalizer_list (right?), and I don't see how we do that here - for instance, if it gets resurrected and then decreffed twice during do_weak_ref_callbacks/finalize.

Another question - if we consume the finalizer_list on a separate thread then it's on the interpreter state rather than the thread state? Or the separate thread looks at the different thread's lists? In either case, doesn't this require locking?

[pablogsal]

I'm assuming you meant that the last line of clear_finalizer_list is obj.refcount -= 1 rather than Py_DECREF(item) recursively.

I think this can get complicated because we need to make sure that we don't add the same object twice to the finalizer_list (right?), and I don't see how we do that here - for instance, if it gets resurrected and then decreffed twice during do_weak_ref_callbacks/finalize.

This is indeed an extremely delicate area of the GC where very obscure bugs have been found over the years. I would be very careful to introduce any changes of that part of the GC machinery without a very good reason, because causing obscure regressions is super easy, and even more dangerous when you involve weak references with types that have tp_clear.

[markshannon]

Why is this fragile? It shouldn't be. I believe the reason it is so fragile is that we break the most important invariant of refcounting, that refcount != 0 for any object that is live. Weakrefs and finalizers keep objects live until they are cleared. The concept of "resurrection" is fundamentally broken.

The algorithm above #58 (comment) should maintain that invariant, so weakref callbacks and finalizers can do as they please.
An object should be deallocated iff its reference count is about to hit 0 and there are no remaining finalizers or weakrefs.

I think this can get complicated because we need to make sure that we don't add the same object twice to the finalizer_list

Yes. The code should be:

def dealloc(obj):
    if has_weakrefs(obj) or obj.needs_finalizing:
        obj.needs_finalizing = False
        finalizer_list.append(obj)
   ...

[nanjekyejoannah]

Am personally interested in making some headway to realize PEP 556, other than @pitrou 's progress, has anyone made any more changes, if so is there a fork I can access? I have planned to work on this during the sprint to also abate other things related to the Python GC research I do. @pablogsal do you have any additional progress you made in addition to @pitrou's work?

[pablogsal]

@pablogsal do you have any additional progress you made in addition to @pitrou's work?

(Sorry for the delay, I just returned from vacation)

Yeah, I did some work on top of it (see #58 (comment)) (mainly fixing some obscure edge cases and bugs) but I need to search for it. Otherwise, I think I mostly remember where the problems were so I will be happy to collaborate in the sprint :)

[nanjekyejoannah]

Good, @pablogsal , when you are successful in the search, please let me know. @pitrou where is your fork, I can lurk at that too. I don't plan to work on it much before the sprint anyway, so let's plan to work on it then.

[pablogsal]

@pitrou where is your fork,

The initial work by @pitrou can be found here:

https://github.com/pitrou/cpython/tree/threaded_gc

[nanjekyejoannah]

Noted and thanks @pablogsal

[iritkatriel]

Mark:

So let's not have resurrection. Once an object is dead, it is dead.

Pablo:

Removing resurrection is not possible: there is a lot of code our there that relies on that.

What if resurrection was not done in __del__ but in a new dunder function that just resurrects or not, but doesn't do any finalization. Then we still support resurrection, and it is clear when an object is alive or dead. Could we then simplify GC along the lines of Mark's proposal?

@nanjekyejoannah - I'd like to join you in the sprint as well.

[pablogsal]

What if resurrection was not done in __del__ but in a new dunder function that just resurrects or not, but doesn't do any finalization. Then we still support resurrection, and it is clear when an object is alive or dead. Could we then simplify GC along the lines of Mark's proposal?

That's is unfortunately still backwards incompatible because current code that resurrects on purpose (or not) is doing it in __del__ and we cannot change that.

Notice that currently is clear when an object is alive or death, and also when has been finalized or resurrected. The problem is that resurrections affect the GC and finalizes, and those semantics are guaranteed.

[iritkatriel]

That's is unfortunately still backwards incompatible because current code that resurrects on purpose (or not) is doing it in del and we cannot change that.

Sure, it would take several versions to deprecate resurrection in __del__. But would it help simplify gc?

IIUC the complication with resurrection is that you can't call finalise twice so you can have an object which is still alive after being finalised.

[pablogsal]

That's is unfortunately still backwards incompatible because current code that resurrects on purpose (or not) is doing it in del and we cannot change that.

Sure, it would take several versions to deprecate resurrection in __del__. But would it help simplify gc?

Not by a lot. There is some complexity in resurrection but it is not one of the biggest pain points of the GC, like for instance weak references and tp_clear. The code that handles resurrection is quite contained and since some changes I worked in Python 3.9, it doesn't even abort the full collection anymore.

IIUC the complication with resurrection is that you can't call finalise twice so you can have an object which is still alive after being finalised

Yeah but those effects are almost non problematic. We just set a flag that says "this object had been already finalized" and to all purposes the resurrected object is alive like any other object.

[tiran]

If you move GC to a separate thread, then please include an API to run functions in that thread, too. Language bindings like JCC or PythonNet must be able to register the thread with Java JVM and .NET CLR. Otherwise GC of a Python object with Java reference can lead to a segfault.

[njsmith]

Async generators are built-in objects whose semantics fundamentally rely on resurrection. Their __del__ just resurrects the object and passes it to asyncio (or whatever async loop is running) to run the real finalizer. I don't love this fact; it definitely makes other things awkward. But I don't see any realistic alternatives.

[markshannon]

@njsmith
Objects can do whatever they like in their __del__ methods.
It is up to the VM to prevent resurrection by calling the __del__ method before the ref-count drops to zero.
You can't resurrect an object if it isn't dead.

The problem is C code that resurrects objects during deallocation.

[markshannon]

One other thing we could do, is to run finalizers in a more restricted environment.
Running them in the current thread might be OK, provided we restricted their access to the current thread, and prevent them changing certain state.
E.g. finalizers should not be allowed to:

• Turn on/off tracing or profiling.
• Interact with the frame stack (no calls to sys._getframe())
• Modify the class of an object obj.__class__ = ...
• Other things, so that we can rely on Py_DECREF() not having weird side effects.

[pablogsal]

E.g. finalizers should not be allowed to:

I agree with this, but notice we need some deprecation period as currently all of these is allowed.

[gvanrossum]

I also agree, but wonder how these could be enforced? Do we need a per-thread flag saying "finalizer is running" that we check for specific operations? (It would have a counter that is incremented when a finalizer is called and decremented when it returns.)

[njsmith]

I think "resurrection" has usually been used to mean "__del__ method creates new reachable references to the object so that it is no longer a candidate for collection"? If you mean a more specific thing like "objects never transition from refcount 0 to 1" then that makes sense to me as a concept, but to avoid confusion you should spell that out instead of just saying "resurrection" and assuming everyone knows what you mean :-)

…

On Mon, Mar 7, 2022, 04:43 Mark Shannon ***@***.***> wrote: @njsmith <https://github.com/njsmith> Objects can do whatever they like in their __del__ methods. It is up to the VM to prevent resurrection by calling the __del__ method *before* the ref-count drops to zero. You can't resurrect an object if it isn't dead. The problem is C code that resurrects objects during deallocation. — Reply to this email directly, view it on GitHub <#120 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAEU42EZ5QY3Q2W6AUJ5NU3U6X2WPANCNFSM5QDFYIAA> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you were mentioned.Message ID: ***@***.***>