A way to stop GC wasting CPU time on long-lived objects (GC generations or something else)

[dktapps]

Description

PHP's GC is currently unsuited to long-running applications because of the lack of GC generations.

Any application which has long-lived objects with many descendents (such as PocketMine-MP's Server) will currently experience significant performance hits from GC runs due to the expense of repeatedly scanning complex dependencies of these objects.

I haven't dived deep into this problem, but I did verify that just the Server alone winding up in the GC root buffer in PocketMine-MP (which it should never do, being an object that stays alive for almost the entire process) costs 1.7 ms of GC time on a 12700k. An average GC run in PM during normal operation costs somewhere in the ballpark of 15ms, despite creating almost zero cycles.

This is a massive performance impact to PM on account of its update cycle taking place every 50 ms, so a 15ms GC pause is serious business.

Runtimes like .NET and Java have GC generations to avoid this problem, which avoid frequently scanning complex long-lived objects.

I understand that the benefit to PHP is relatively small, given that the primary use case is to serve short-lived web requests, but implementing generations in GC would positively affect performance of long-lived applications.

[arnaud-lb]

Do you have runable benchmarks to share? This would help to test GC improvements in the future.

The problem you describe is usually mitigated by the adaptive threshold: GC collections are triggered less often when they collect too few nodes. Basically the frequency of GC collections is a function of the frequency at which garbage cycles are created (and their size). However this a simple heuristic, and it doesn't take into account the cost of collections / the size of the scanned graph. Taking these into account would probably improve throughput in your case (but not pause time).

But I agree that switching to a generational GC may be worth a try.

Are you aware of generational cycle collection algorithms? I did some quick research in the past and wasn't able to find any.

There are systems with ref counting and a generational GC in the wild, but they use a tracing collector, not just a cycle collector (e.g. Python I believe).

Ref counting + generational tracing may still be beneficial compared to ref counting + non-generational cycle collector.

It would be nice if using a tracing collector allowed us to remove reference counting, but we can not as we rely on it for array CoW semantics (also structs potentially), at least, and people may rely on the predictable timing of destructor calls (in the absence of cycles) for RAII-like behaviors.

It should be noted that the implementation of a generational GC is not trivial as it requires to keep track of when inter-generational references are created, which potentially adds overhead to every write operation.

[dktapps]

Do you have runable benchmarks to share? This would help to test GC improvements in the future.

I haven't, no. Unfortunately I can only tell you about my experience with long-running server applications.

The problem you describe is usually mitigated by the adaptive threshold: GC collections are triggered less often when they collect too few nodes.

Yes, but there are still significant pauses whenever the GC does kick in.

In addition, since GC_THRESHOLD_TRIGGER is fixed, the threshold will not change if the collector collects more than 100 cycles. This is a very easy number to hit with short-lived objects.

This creates a big incentive to manually destroy cycles to avoid costly GC runs. IMO this shouldn't be necessary considering that most shortlived cycles are likely cheap to clean up.

Acyclic objects also cause unnecessary collections, although these don't count towards cycles collected, so the threshold does mitigate these.

A lower-effort alternative to GC generations which would still give some of the benefits would be to allow user code to explicitly declare objects for the GC to skip, either by something like #[IgnoredByGC] or perhaps a gc_ignore(object $object) function. I attempted to implement the latter in an extension, but it didn't produce the desired effect due to the GC not respecting GC_NOT_COLLECTABLE when scanning object referents.

[dktapps]

For posterity: I devised a workaround for this problem as an extension here: https://github.com/dktapps/ext-gcignore

I've restricted it to standard Zend objects for now (so extension classes are not supported, out of an abundance of caution), but this works by overriding the get_gc handler to an empty stub on objects for which gc_ignore($object) is called.

I considered that a tracing GC would also solve this problem and might work well for PHP. It seems obvious that any object referenced by a static property, global or local variable cannot be GC'd (as well as any of its descendents).

[arnaud-lb]

Thank you for sharing @dktapps! In 8.5 you will be able to rely on GC_NOT_COLLECTABLE directly, thanks to this change: e69317b (cc @iluuu1994)

It seems obvious that any object referenced by a static property, global or local variable cannot be GC'd (as well as any of its descendents).

@bwoebi is working on a solution to attempt to ignore such nodes in the cycle collector

I'm also planning to explore generational/incremental collection again.

[dktapps]

Thanks. I will say though that it's not as effective for heavily nested complex objects. I wasn't able to crack that and I don't see a sane way to do so. So I ended up having to gc_ignore() a lot of objects which I knew were part of the ownership chain of long-lived objects.

In 8.5 you will be able to rely on GC_NOT_COLLECTABLE directly, thanks to this change: e69317b (cc @iluuu1994)

Yup, I saw that. I was quite surprised to learn that strings find their way into the GC root buffer too.

@bwoebi is working on a solution to attempt to ignore such nodes in the cycle collector

I'm also planning to explore generational/incremental collection again.

I'm not too familiar with other GC techniques but it would be a big plus if this were to be solved 😃

[arnaud-lb]

Yup, I saw that. I was quite surprised to learn that strings find their way into the GC root buffer too.

To be precise, strings were not added to the root buffer, and didn't count towards the threshold. However, strings reachable from roots used to be added to the worklist during a GC run.