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....
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.
> 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.
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.
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?
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.
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....
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.
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.
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.