Incremental garbage collection

[Gregor Mückl]

On Thursday, 20 January 2022 at 23:56:42 UTC, Chris Katko wrote:
> I just found out that Unity has incremental garbage collection. 
> I didn't know that was a possibility for GCs.
>
> https://docs.unity3d.com/Manual/performance-incremental-garbage-collection.html
>
> I'm just curious what the D language community's thoughts are 
> on it. The tradeoff is: For
> a longer total time / lower throughput, you reduce stress on 
> individual frames which prevents hiccups. That's pretty darn 
> important for games and soft/hard real-time systems.
>
> Is that an option on a hypothetical level, for D? Or does D's 
> language design preclude that. I recall some sort of issue with 
> using Java/C#/whatever's garbage collector because it would 
> have to insert memory barriers into D to work or something like 
> that.
>
> Also, it's hard to find one specific place for "news" regarding 
> D's garbage collector development and "omg we deleted 
> everything GC from the standard library" projects. Are there 
> any major updates on those fronts?

Just to add to this for completeness sake: a while ago I spent a 
few hours digging through Uneal Engine source code to understand 
their GC algorithm. It's a peculiar and interesting take on 
iterative, precise, conservative garbage collection:

- First of all, UE4 has precise runtime reflection information 
for all data types that are handled via the GC (everything 
derived from UObject - which is mostly game logic code). Heap 
scans are optimized aggressively based on this data. Pointers are 
regular naked C++ pointers without any additional magic. They 
need to be annotated for the custom preprocessor that generates 
the reflection data, but that's it. The C++ code touching these 
pointers is plain old code using naked pointers. No hidden 
wrappers there.

- The algorithm is basically mark and sweep with a couple of 
awful situational hacks that stem from weird engine subsystem 
interactions. I'll gloss over those. The GC performs a multistep 
GC process. Each frame, the engine prompts the GC to run one step 
in a stop-the-world fashion.

- Each step, the GC can either run an *entire* mark phase or a 
single step of the sweep phase. The mark step is always run in 
its entirety, never in multiple steps. The sweep phase is broken 
up into steps that free a limited number of marked objects in 
each step. The rest is deferred to the next step. When sweep 
phase is done, the next GC step will be a new mark phase.

IMO, this is a very pragmatic approach. But for the runtime to be 
truly bounded, the heap size needs to be bounded, too. I assume 
that this works for UE4 because for most games using the engine, 
the number of objects involved in the game logic at any point is 
fairly small (mostly ~ a few hundred). Stopping the world for the 
mark phase is also a major simplification. This avoids the 
overhead typically incurred by GC algorithms that do incremental 
marking. Also, GC references can be treated just like regular 
pointers.

I don't know how the D garbage collector runtime is split between 
mark and sweep phases. If the sweep phase is indeed the slower 
phase, an option to have that run iteratively might be enticing. 
I would naively assume that this would be lower hanging fruit 
compared to a generational and/or concurrent GC. But then again, 
I don't have a need for any of that at the moment.