Improving Python Garbage Collection Performance by Providing Unreachable Cycles Hints

Ideas
1

Overview

This suggestion calls for adding a way to help developers and code analysis software to hint the garbage collector that a group of objects may no longer be reachable. Such hints would reduce the time spent on the garbage collection cycles and improve system CPU utilization. Those hints would never be taken as a commitment, and will always be checked before being used to deallocate objects.

Methodology

The solution would be based on two components:

  1. A new package, gchint, which will allow the developer to hint that a collection of objects is no longer reachable.

  2. A code in the garbage collector which would analyze such hints, verify that each hinted collection of objects is indeed unreachable and deallocates them if so

Example

#Web request initialization
request = request_factory()
request.status = status_create()
request.status.request_backpointer = request

/*** request and status point to each other *****/
gchint.hint_manager.define_cycle(request, “request”, request.id)
gchint.hint_manager.define_cycle(request.status, “request”, request.id)
.
.
.
# request and status are no longer reachable, and can be 
# deallocated but they will not be deallocated by simple reference 
# count #math since they point to each other and form a cycle

gchint.hint_manager.cycle_unreachable(“request”, request.id)
.
.
# GC Code 

Iterate on hints
    Iterate on all objects of a specific hint
        Count total reference count of the object
        Count number of references between members of the objects to other
            objects in the hinted cycle
        If both counts are identical, deallocate

In the above example, we have a hint for two objects, request and status, each has a reference count of 1, and each has one reference to the other object, and hence they are not referenced by any other reference and can be safely deallocated.

Effect

Effective usage of this package would allow a fast object deallocation and reduce the time spent in the full generation scan of the garbage collection, by increasing the number of times the GC process is skipped due to the small number of objects allocated.

Correctness

Note that this is a hint only, and the deallocated object cycle is always verified to have no external references. Furthermore, if the system identifies a number of false hints above a certain threshold from a certain category it can ignore that category.

Cycle Hint Extension

If a hint for a collection of cycles proves wrong, it can be considered to attempt to add more objects using a simple heuristics. For example, if one of these objects contains a reference to an object with reference count being one, this object can be added to the tested cycle. In case such object contains references to other hinted objects a cycle can be detected.

Logging

An optional API for logging cycle detection, which will provide insights to how many of the hints in cycles were indeed deallocated per each category can be provided, especially for debug/test environment. Such statistics can help humans and code pre-processing tools to improve and re-iterate.

2

In the example cycle, it would seem easier to just break the cycle. How common are situations where this is not possible.

3

Do you have an algorithm that can do this is in less time than just performing a full garbage collection?

4

I assume that “just break the cycle” means a developer engineering work which would understand that an unreachable cycle was created and eliminate some of the references. This is indeed always better, but with the huge amount of complex code with multiple layers and many contributors, and the lack of highly skilled developers who know the code inside-out will make it impractical in many cases.

The suggested approach, either by human developer or Claude-Code based is much easier and safer as it will deallocate only opportunistically.

5

Yes. What we need to do is scan the group of objects, and sum all their reference counts. After that scan all these objects for references to other objects in that group. If the total number of references to objects in this group from within the group equals the total of their reference counts, they can be all deallocated safely.

In the above example, both sum of the reference counts and total number of references is 2.

The algorithm is linear in the group size, unlike the garbage collection process is depends on the total amount of objects and references in the whole runtime environment. This is not only a CPU time reduction, but also will reduce the amount of time the Python GC stops all other threads and created latency in handling requests. This would not eliminate GC scans, but can in some cases reduced their number significantly.

6

I hope I did not overlooked something, but these hints could need an update after code modificaton and thus would need a test to verify they are doing what is expected. But if a test is required, I think it is easier to have a test for existence of reference cycles (not sure how to do that with gc debugging, but I guess it is possible). And once they are found, they can be broken as already suggested.

7

I’ve seen similar discussions in the Java community — manually managing the lifetime of some objects like in C/C++, instead of relying on GC. But that tends to make the GC implementation much more complicated and easier to get wrong. What scenario led you to want this kind of manual control? Is GC taking too long in your case?

8

I assume that any data structure code update would require an update of the hints as well, as is true for every aspect of code change. I am not 100% I understand what you meant but the key advantage here is that cycle hint verification is done in time proportional to the hint group size, while other cycle finding schemes take take proportional to the total size of memory. I hope I answered all your questions

9

This is complementary to the existing GC implementation and not replacing it, The current Python GC code would be in effect (reference counting, and search for unreachable objects), but the Stop-The-World memory scans would be less frequent, Hence the CPU utilization will be better and there will be less cases of high latency induced by GC scan,

Java to the best of my knowledge does not have reference counts, so the whole system is difference.

10

I see. Yes, in theory the hint will help with latency (response time in P99).

11

There seems to be a lot of “in theory” involved in this proposal. Does
anyone have any real-world use cases and a way of estimating the amount
of benefit that would result?

There needs to be a case in which we know we’ve just created a
potentially unreached cycle, we have ready access to all the objects
involved in it, and we can’t deal with it by just breaking the cycle. I
can’t remember ever having encountered a situation like that in my code.

1 Like
12

Two comments, one about the implementation and another about the benefit.

The implementation will based on storing the objects as weka references, where the grouping of the objects would be by some identifier (string or integer) which identifies the business process common to all of them. There will be no need to call the hint function just before an object is not needed, but while the reference is active. Instead, we will just need to say the equivalent of “balancing process identifier AA1234 is no longer in effect, please try to deallocate all associated objects.”. I am aware the my example above is flawed since the hint it provided using the request object. I will fix the example.

On the benefit side, there has been quite some cases where the GC process became very consuming (most famous was the Instagram one, where the team disabled the GC and just restarted the machines when running out of memory, assigning the processing to other machines. I can not tell how many of the real life cases are such, but I have seen statistics of GC consuming 5%-30% of CPU time. The big unknown is how many of the cycles where indeed be identified and hinted by a human developer or by Claude Code. A short scan of Claude Code on public open source projects seems promising, but we can’t know their effectiveness without implementing this feature. If Claude Code would be able to identify cycles from code analysis, the CPU time dedicated to GC would be reduced and P99 latency would improve. This is not a game changer, but it can be very significant in some cases, and I think is worth a not very complicated implementation.

With the addition of GenAI based programming we would have on one hand a much less efficient memory handling, but on the other hand, a simple prompt would guide the GenAI to provide the right hint,

I hope I answered the questions above.