> Can we make “the simplest form” of tracing garbage collection work for systems programming?
No. 24 bytes per allocation and having to perform a copy and point fixup is too expensive.
The problem with GC is that it’s fine until it’s not. And when it becomes not fine you need to radically change your entire architecture. There is no incremental fix.
That said, Unreal Engine does in fact use a mark-and-sweep GC for certain types of objects. Which could be something for the author to look into.
Where do you get 24 bytes of overhead from? A mark-sweep collector only needs a bitmap of 1 bit per alignment granule.
edit: oh, that's what the article uses - the tracing function and size function can be per-heap and the forwarding pointers can overwrite the start of objects, to just have enough header to support tracing and sizing, which could be one word.
Hi Hayley, could you explain how the tracing function and size info can be packaged into one word?
Since the GC Arena is meant as a default heap, the size should be allowed to be pretty big (> 32 bits). And doesn't the tracing function need to support a full pointer size? since they're not allocated but rather stored in the executable I guess they'll be placed in some predictable place in the address space, so I could take advantage of that.
We're going to put just a type ID in the word - you could probably get away with much smaller than a 64-bit ID, but padding will round it up to 64 bits in any case. The heap has exactly one tracing function and size function for all objects, and the functions check the type ID to determine what type they're looking at.
Ah I get what you mean now. Yeah that would totally work. Having a custom tracing function per type lets the host language (C in this case) also store its own types in the GC Heap if so desired quite easily though, since all the programmer has to do is call gc_move(...) once per struct field in that function.
Writing out a typeinfo struct of some sort by hand is not as simple.
Maybe a good middle ground would be to register the tracing function separately with the GC Heap, which would return an ID for later use with gc_alloc.
I could also make the size just be the return value of the same function. The question is then what's worse, an extra 8 bytes in the header of every allocation, or the time spent in the function calculating the size. Since the function has to be called anyway, I'm guessing there's no point in storing it.
That would mean even the ID is not necessary, since an 8byte header is about as good as you can get due to padding.
Are 16/24 bytes that much worse than 8/16 (with weak refs) for ref counting?
The copying can be too expensive yes, though hopefully the ability to use non-garbage collected arenas would mitigate that issue (just don't put huge live data in the default, GCed arena)
> Are 16/24 bytes that much worse than 8/16 (with weak refs) for ref counting?
No, but that's not the right question. Most allocations in languages like C/C++/Rust aren't using ref counts. In fact excessive use of std::shared_ptr is a well known footgun in C++!
> the ability to use non-garbage collected arenas would mitigate that issue
I agree that not using GC is a way to mitigate GC issues! But if you're only able to performantly use GC for a limited number of allocations you also aren't getting much benefit from GC.
Note that you can allocate as much temp data as you want to the GC heap without incurring any performance issues (in fact allocation will be faster than malloc), because copying collectors only ever care about live objects.
So the question is, how much of an issue it is to "contort" the program to not allocate large, live objects to the GC heap, vs contorting it to have a tree-like structure for RAII-style memory management.
Honestly, I have no idea, one of the reasons I really want to make a toy language to try it out and actually measure the runtime costs vs convenience etc.
Note: For my particular C implementation, which is admittedly cobbled together with spit and ducktape, you can easily add support for individually managed allocations to the GC heap, since it already uses buckets anyway.
If a bucket contains only 1 allocation, there's no need to copy, you can just keep that bucket somewhere in the linked list. This does require the programmer to explicitly request that kind of allocation though.
For the "huge amount of small objects" case, GC and RAII/RC are complete opposites. If most of those small objects die, the GC will be a lot faster since it drops them by not copying them. But if most of the objects are live, then the GC will spend a brutal amount of time copying, while RAII/RC will barely do any work.
Having memory management options is a good thing ;)
Yes, and Unity is famously known for having a bad GC implementation from Mono stone age, that they never updated due to license disagrements with Xamarin, they never invested into having one of their own, rather HPC# instead, and apparently are still years away of adopting .NET Core.
Capcom doesn't seem to suffer the same issues, with their .NET based engine for Playstation, based on .NET Core fork.
Unity has been both a bless, and a curse to the use of C# in the games industry.
Burst is also capable of auto-vectorization. It is effectively using a subset of C# as DSL but nonetheless a tool that serves its purpose. It also has various assertions to ensure that the performance does not regress, like failing the build if the code change breaks auto-vectorization, something I have not seen in C++ lands (please do correct me if there is a comparable tool).
With the ongoing move to CoreCLR, Unity's own intrinsics and SIMD/Math abstractions will be replaced by in many ways identical ones that are present in .NET's CoreLib. As for Burst, I suppose we'll just have to wait and see.
I am most interested in what Unity will do in regards to GC implementation - .NET supports custom GCs and it is high time someone implemented one, particularly for consistent latency sensitive scenarios. The existing implementation is good, but games really do love determinism and relatively few developers can do what PPY did to achieve 1000hz game loop in OSU!.
Yes, they have done a ton, but perceptions are also hard to change.
I am looking forward to their ongoing efforts.
Regarding custom GCs, although CLR offers similar extension points as the JVM, maybe due to the usual way Microsoft was traditionally seen, very few people ever bothered to play with custom GCs, or pluggable debug interfaces, or JIT code rewritting.
Skepticism is good. You should not be convinced until I can provide some actual evidence. Sadly I don't know when I'll find the time.
I don't think GC is a good fit for games, so there I wouldn't recommend using this or any other existing GC really. Maybe if I find a way to make collect incremental so you can call it only once per frame with a time budget, then it could work.
No. 24 bytes per allocation and having to perform a copy and point fixup is too expensive.
The problem with GC is that it’s fine until it’s not. And when it becomes not fine you need to radically change your entire architecture. There is no incremental fix.
That said, Unreal Engine does in fact use a mark-and-sweep GC for certain types of objects. Which could be something for the author to look into.