12 ms·

Watching Go's new garbage collector move through the heap

261 points by matheusmoreira 3mo ago

nomorewords 3mo ago
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
- john01dav 3mo ago
  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.
- samdhar7 3mo ago
  [flagged]
- jerf 3mo ago
  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.
  - jeffbee 3mo ago
    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.
    - toast0 3mo ago
      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/navarro/navarro.pdf https://www.usenix.org/legacy/events/osdi02/tech/full_papers... [2] https://www.bsdcan.org/2014/schedule/attachments/281_2014_arm_superpages-paper.pdf https://www.bsdcan.org/2014/schedule/attachments/281_2014_ar...
      - jeffbee 3mo ago
        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.
        matheusmoreira 3mo ago
        > 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.
owaislone 3mo ago
For anyone interested in this - https://www.youtube.com/watch?v=gPJkM95KpKo https://www.youtube.com/watch?v=gPJkM95KpKo
- KolmogorovComp 3mo ago
  thank you for the link, great and well-explained talk.
okzgn 3mo ago
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.
- amelius 3mo ago
  That's what every "copying GC" does. https://www.cs.cornell.edu/courses/cs312/2003fa/lectures/sec24.htm https://www.cs.cornell.edu/courses/cs312/2003fa/lectures/sec...
  - okzgn 3mo ago
    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.
extra-AI 3mo ago
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?
prathamdmehta 3mo ago
that's very interesting with some blunt ending
KolmogorovComp 3mo ago
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?
- KolmogorovComp 3mo ago
  Ah it's from 2023, Miguel de Icaza : Swift Godot: Fixing the Multi-million dollar mistake: https://www.youtube.com/watch?v=tzt36EGKEZo https://www.youtube.com/watch?v=tzt36EGKEZo Highly recommend.
  - Rohansi 3mo ago
    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.
    - pjmlp 3mo ago
      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.
    - bob1029 3mo ago
      > 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.
madhu_ghalame 3mo ago
[dead]
runtime_lens 3mo ago
[flagged]
vernonHeim 3mo ago
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.
torginus 3mo ago
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.
fuzzfactor 3mo ago
I never did think much about why they called it a heap until now :)

261 points by matheusmoreira 3mo ago

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

john01dav 3mo ago
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.
samdhar7 3mo ago
[flagged]
jerf 3mo ago
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.
- jeffbee 3mo ago
  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.
  - toast0 3mo ago
    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/navarro/navarro.pdf https://www.usenix.org/legacy/events/osdi02/tech/full_papers... [2] https://www.bsdcan.org/2014/schedule/attachments/281_2014_arm_superpages-paper.pdf https://www.bsdcan.org/2014/schedule/attachments/281_2014_ar...
    - jeffbee 3mo ago
      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.
      - matheusmoreira 3mo ago
        > 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.

owaislone 3mo ago

For anyone interested in this - https://www.youtube.com/watch?v=gPJkM95KpKo https://www.youtube.com/watch?v=gPJkM95KpKo

KolmogorovComp 3mo ago
thank you for the link, great and well-explained talk.

okzgn 3mo ago

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.

amelius 3mo ago
That's what every "copying GC" does. https://www.cs.cornell.edu/courses/cs312/2003fa/lectures/sec24.htm https://www.cs.cornell.edu/courses/cs312/2003fa/lectures/sec...
- okzgn 3mo ago
  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.

extra-AI 3mo ago

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?

prathamdmehta 3mo ago

that's very interesting with some blunt ending

KolmogorovComp 3mo ago

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?

KolmogorovComp 3mo ago
Ah it's from 2023, Miguel de Icaza : Swift Godot: Fixing the Multi-million dollar mistake: https://www.youtube.com/watch?v=tzt36EGKEZo https://www.youtube.com/watch?v=tzt36EGKEZo Highly recommend.
- Rohansi 3mo ago
  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.
  - pjmlp 3mo ago
    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.
  - bob1029 3mo ago
    > 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.

madhu_ghalame 3mo ago

[dead]

runtime_lens 3mo ago

[flagged]

vernonHeim 3mo ago

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.

torginus 3mo ago

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.

fuzzfactor 3mo ago

I never did think much about why they called it a heap until now :)