back
43 comments
This was very interesting, but the ending was a bit abrupt. I was under the impression that there was something more that I was missing under the subscribe banner.

But to the point of the article - are there cases in which manually moving objects around to compact them in a specific area is done with golang? I don't use golang that much, and I'm sure that there are very strong arguments for not compacting the heap post-GC, but I've always wondered how it avoids crashing in the 0.0001% of cases in which heap is defragmented in such a way that there's no way to allocate a new large object

It's because of what's in the second paragraph, which I will paste here for convenience:

"Taking a step back, Go manages memory by allocating objects of the same size class (an object’s size is rounded up to the nearest size class) within a contiguous chunk (or span in Go terminology) of one or more 8KiB pages. Size-segregated allocation is common in some malloc implementations (like tcmalloc, which Go’s allocator descends from)."

(No passive-aggressive snark about reading the article intended; it's a good question and I really am just pasting it for our convenience.)

You can't get the inability to allocate some large object because there's a spray of small objects in its way, because the small objects don't share space with the large object. The large objects live in their own space, and the fragmented small objects can be efficiently utilized later by putting other small things in the empty space later.

In the 64-bit world, you also don't have to worry about how you arrange things in physical RAM so one size doesn't end up impacting another. You can always allocate some suitably-sized new chunk of ram that's incredibly distant in the virtual address space and let the OS map that back to the real RAM. It may do something more clever than that because there is still 32-bit Go and that trick is less freeing in that scenario, but the principle would still hold. You don't get the inability to allocate a large object by small objects because they don't live in the same place. You might still "run out of RAM" before you've quite literally run out of RAM, but you'll get closer.

And ultimately that's a problem shared by a lot of memory allocation schemes, not particular to GC or Go. For a lot of reasons, it's a good idea not to run resource usages right up to 100% if you can avoid it and you can expect across a wide range of resources types to encounter problems and expect to do a lot of careful work to make it possible to hit truly full utilization if you need it for some reason. Beyond computers, even... it's rarely a good idea to plan on 100% utilization of anything be it physical or electronic.

One of the drawbacks of relying on the virtual memory subsystem is large page tables, that the machine has to manage on your behalf, and that pollute (or at least occupy) caches. That is another reason why Go, like all other software, benefits significantly if you adjust your Linux boxes to use huge pages, or larger-than-default pages, or ARM contiguous page bits, or whatever other features your platform offers to make virtual address translation more efficient. It is unfortunate that Linux usually comes out of the box with all of these post-286 features disabled.
AFAIK, FreeBSD has been doing transparent superpages for decades (I think it was implemented in 2002 for x86 [1], and 2014 for arm [2]) and I don't know of any real issues with it? (I'm sure you could build a test case where it thrashes and causes trouble) Not sure why Linux wouldn't do the same??

[1] https://www.usenix.org/legacy/events/osdi02/tech/full_papers...

[2] https://www.bsdcan.org/2014/schedule/attachments/281_2014_ar...

Linux also has support for it but it is up to the distribution, or the user, to enable or disable it. The whole discourse was poisoned years ago when the author of Redis told everyone to disable THP on Linux, but this was caused by Redis being a poor program, not by THP being a poor feature. Unfortunately, even though the Redis project finally removed their document about this, many people still carry this bias.
> The whole discourse was poisoned years ago when the author of Redis told everyone to disable THP on Linux

What's the story behind that? Do normal programs really get affected by this?

Normal programs are most likely using glibc's memory allocator, and I'd be surprised if it was incapable of handling arbitrary page sizes. Only reason why I have to care is I implemented my own memory allocator.

Redis uses jemalloc by default, if I recall correctly, but its hostility to the way systems actually work arises from the way that it forks, then changes one bit on every page in the entire virtual space, which causes a lot of kernel work to support copy-on-write by blowing up huge pages into smaller pages. That's what happens when your program is antagonistic to the way the machine actually works.
There was also an issue with Linux about 8 years ago where the THP daemon would start busy-looping searching for pages to amalgamate, wasting loads of CPU time (and I believe freezing the processes it was inspecting), and so people were advising switching off THP for that reason until it was fixed. It hit our large Java processes quite badly.
> You can't get the inability to allocate some large object because there's a spray of small objects in its way ... The large objects live in their own space

Assume for the sake of argument that the large object space is for objects >=1MB.

Allocate lots of 1MB objects then free every other one (by address).

Unless you're willing to let the large object space grow without bounds....

There is a theorem that is often stated in operating system courses as "For any possible allocation algorithm, there exist streams of allocation and deallocation requests that defeat the allocator and force it into severe fragmentation.". You can ask your friendly local AI about "Bounds for Some Functions Concerning Dynamic Storage Allocation" by J. M. Robson in the July 1974 Journal of the ACM and some various follow-up papers. For any non-compacting memory management algorithm, including traditional malloc/free, there will always be a way of defeating it and forcing it to fragment.

However, consider that Go has been in production for 14 years now, and one of its bread-and-butter applications is network servers, which will collectively exercise quite a bit of the memory allocation pattern space, including some pathological aspects of it. You should expect to need to do better than that to really throw it for a loop.

While the theorem proves some such sequence exists, there's no guarantee that the sequences will be easy to describe in some sort of English sentence.

Large objects (≥ 32 KiB) does not use these categorized arenas, they instead allocate an integer number of 8KiB pages from a heap.
I haven’t read the article, but for allocations that large, chances are they get allocated as entire memory pages and the garbage collector returns that memory to the OS.

Also, even if it doesn’t, in a 64-bit address space it takes lots of 1MB objects to make that cause problems (there’s room for over 10¹⁶ of such objects)

Correction: over 10¹³. Still a lot.
Sounds like a challenge.
Are you sure that it doesn't just crash in that case?

Also, we have such a huge virtual memory space on 64 bit architectures that I can imagine that being involved somehow, but I don't know for sure.

For anyone interested in this - https://www.youtube.com/watch?v=gPJkM95KpKo
thank you for the link, great and well-explained talk.
Excellent optimization technique: manually copying objects to a new slice so they don't prevent the GC from releasing memory by sitting right in the middle of a page it intends to free.
That's what every "copying GC" does.

https://www.cs.cornell.edu/courses/cs312/2003fa/lectures/sec...

Of course, but Go's GC doesn't compact or relocate the objects still in use in the middle of a page (which means that page can't be released to the OS) until you manually copy those surviving objects out, freeing up the page they left behind.
Interesting and its noteworthy to observe that the new GC actually increases the rate of L3 misses slightly. For reference, L1 misses are quite fast, and often free since the CPU can cover up the empty slots with useful work, however L3 misses require a read from RAM which is an eternity in CPU cycles.

My theory is that Go programs cover up the wait for L3 via SMT (which is still kinda common on server CPUs) and schedule work from another hardware thread.

Such a technique might be less usable in less-threaded languages, or non-SMT CPUs and the new GC might end up being slower.

The heap visualization is a great way to make GC behavior less abstract. It's interesting to see how much impact memory layout and cache locality can have, not just the GC algorithm itself.
Tangential but this makes me think of a video about C# GC, and the developer switching to Swift to avoid it, in which the dev says they estimate the development of a pause-less GC to be 5B$ R&D away, does that ring the bell to anyone?
According to Cliff Click, compilers and JVM + some other systems programming guy, Azul has a JVM with microseconds pause times at very large heap sizes (10s, 100s of GB?) and allocation rates. That is "pauseless" for gaming purposes.
Ah it's from 2023, Miguel de Icaza : Swift Godot: Fixing the Multi-million dollar mistake: https://www.youtube.com/watch?v=tzt36EGKEZo

Highly recommend.

Can't say I totally agree with the claim that GC is a dealbreaker for games. There are trade-offs either way and games typically need to do things a bit differently to achieve high performance anyway. It is, however, a strong benefit of Godot over Unity because Unity is still stuck with the worst possible GC (Boehm) for the foreseeable future.
It isn't, some people managed to get quite rich with games written in GC languages.

There is an agenda there, the business did not go down well with Unity for Xamarin, and now there is the whole Swift for Godot that needs to be sold for adoption.

Unreal uses a GC for C++ code, yet the performance problem most people hit on Unreal is compiling shaders.

Finally from academia point of view, reference counting is a GC algorithm, as any book worth reading in CS curriculum will have it as such.

> Unity is still stuck with the worst possible GC (Boehm) for the foreseeable future.

How are we measuring "worst possible" here?

Unity's GC is unique in that it has an incremental marking phase. The most important thing in a unity application is frame latency, not raw GC throughput. If you are generating so much garbage every frame that the incremental collector falls behind, that's probably on you.

> How are we measuring "worst possible" here?

The garbage collectors used by both .NET and Mono (since 2013) are precise, concurrent, and compacting. They know exactly what memory locations are GC references, scans them while the game is still running, and moves objects in memory to fix fragmentation. Pause times are kept short because heavy work is done on a background that.

Unity's GC is conservative and incremental. It does not know what addresses are GC references so it has to scan everything that could be a GC reference. It's incremental which is nice but means you're expected to trade a few milliseconds of your frame budget for the GC to run. Being conservative means a chunk of your budget is spent scanning memory locations that aren't GC references. By default it uses the time spent waiting for vsync to run but not everyone plays with vsync enabled and lower spec systems have less room there so they end up running worse.

A Jurassic GC introduced in Mono, that due to Unity not wanting to pay Xamarin for updates, meant it was mostly frozen in the days of Unity/Xamarin early collaboration.

Unity preferred to go down the route of HPC#, Burst compiler and IL2CPP, and is still maybe one to two years to fully migrate to modern .NET.

Meanwhile in Redmond, Mono is almost gone, with CoreCLR already in preview for mobile platforms,

https://devblogs.microsoft.com/dotnet/dotnet-maui-moves-to-c...

Capcom's RE engine also uses their own fork CoreCLR, customised for consoles, Devil May Cry for PS 5 uses it.

> Unity preferred to go down the route of HPC#, Burst compiler and IL2CPP, and is still maybe one to two years to fully migrate to modern .NET.

They're replacing Mono with CoreCLR in Unity 7 which is Q1 2027. Somehow they're also doing this with no breaking changes too - even though they previously announced breaking changes due to the obvious differences between the two runtimes.

Also, they have already said there are no plans to change the GC used by IL2CPP builds so it will keep using Boehm.

Yeah, but will they deliver this time?

Apparently the team has been affected multiple times during the various layoffs.

Unity has been both a blessing for .NET adoption on the games industry, and also pain, given that many equate .NET with their Unity experience.

> Unity's GC is unique in that it has an incremental marking phase.

Does ZGC not also have an incremental marking phase?

Also, the default collector, G1, introduced more than 15 years ago. Most JVM GCs are concurrent, too.
I never did think much about why they called it a heap until now :)
that's very interesting with some blunt ending
But if the objects being scanned are already located on the same page, aren’t we just wasting time managing the page and tracking the objects within it?