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.
> 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.
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)
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??
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.
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.
> 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.
> then changes one bit on every page in the entire virtual space
Yeah that sucks. Naively implemented garbage collectors have the same problem: they put the live and mark bits in the object itself which spreads those bits all over the address space. This leads to the garbage collector touching every single page when it scans and writes all of those bits.
The proper solution is to allocate separate bitmap pages. This dramatically improves cache efficiency. Machines always want a structure of arrays.
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.
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.
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.
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.
> 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.
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,
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.
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?
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
"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.
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....
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.
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)
[1] https://www.usenix.org/legacy/events/osdi02/tech/full_papers...
[2] https://www.bsdcan.org/2014/schedule/attachments/281_2014_ar...
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.
Yeah that sucks. Naively implemented garbage collectors have the same problem: they put the live and mark bits in the object itself which spreads those bits all over the address space. This leads to the garbage collector touching every single page when it scans and writes all of those bits.
The proper solution is to allocate separate bitmap pages. This dramatically improves cache efficiency. Machines always want a structure of arrays.
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.
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.
https://www.cs.cornell.edu/courses/cs312/2003fa/lectures/sec...
Highly recommend.
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.
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.
Does ZGC not also have an incremental marking phase?
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.