4 ms·

You might have checked but here is IanT's reply on "Why golang garbage-collector not implement Generational and Compact gc? There is also interesting discussion

by geodel 9y ago

You might have checked but here is IanT's reply on "Why golang garbage-collector not implement Generational and Compact gc? There is also interesting discussion in thread. https://groups.google.com/d/msg/golang-nuts/KJiyv2mV2pU/wdBUH1mHCAAJ https://groups.google.com/d/msg/golang-nuts/KJiyv2mV2pU/wdBU... "However, modern memory allocation algorithms, like the tcmalloc-based approach used by the Go runtime, have essentially no fragmentation issues. And while a bump allocator can be simple and efficient for a single-threaded program, in a multi-threaded program like Go it requires locks. In general it's likely to be more efficient to allocate memory using a set of per-thread caches, and at that point you've lost the advantages of a bump allocator. So I would assert that, in general, with many caveats, there is no real advantage .."

pizlonator 9y ago
Bump allocators don't require locks. Bump allocators are especially effective in the presence of thread-local caches. Whoever wrote that must not be very familiar with how memory management works.
pcwalton 9y ago
> And while a bump allocator can be simple and efficient for a single-threaded program, in a multi-threaded program like Go it requires locks. In general it's likely to be more efficient to allocate memory using a set of per-thread caches, and at that point you've lost the advantages of a bump allocator. Ian is extremely confused here. Every production multithreaded generational GC uses thread-local allocation buffers (edit: thanks to Filip for correcting my terminology).
- pizlonator 9y ago
  Very few production multithreaded generational GCs use per-thread nurseries. But probably all of them use thread-local caches, or what you might call per-thread caches. I think that's what you might have meant. Per-thread nurseries is a shit idea unless your language has extra-super-high levels of infant mortality. Remember that in a per-thread nursery genGC, the write barrier has to infect the pointed-to object with the global heap so that future stores to that object also trigger the barrier. In a normal genGC, the pointed-to object is unaffected; the stored-to object is merely shaded (or card-marked, or logged, or whatever) for revisiting. Humorously for parent's post, to my knowledge the first instance of a thread-local cache was the idea that a multithreaded compacting GC can chop off a slice of memory from the global bump allocator and then use it to service a thread-local allocator. Not 100% sure though because maybe Boehm and friends beat everyone to it.
  - pcwalton 9y ago
    > Very few production multithreaded generational GCs use per-thread nurseries. > Per-thread nurseries is a shit idea unless your language has extra-super-high levels of infant mortality. Isn't that what TLABs are? HotSpot uses TLABs by default, unless my info is out of date… For example, [1] shows the generated assembler for object allocation, which uses nonatomic pointer bumps. I think we might be talking about different things by "per-thread nurseries". All I mean by a "per-thread nursery" is a TLAB. [1]: https://shipilev.net/jvm-anatomy-park/4-tlab-allocation/ https://shipilev.net/jvm-anatomy-park/4-tlab-allocation/
    - pizlonator 9y ago
      Like I said, you're thinking thread-local caches. TLABS are thread-local caches, not per-thread nurseries. There's a HUGE difference between a thread-local cache (which everyone uses and which you cite) and per-thread nurseries (which are an obscure idea that hardly anybody likes).
      - pcwalton 9y ago
        Yes. Apologies for using the wrong terminology :)
- geodel 9y ago
  And TLABs causes more memory fragmentations and which lead to more GCs and more need for memory compaction. So finally Java solved the problem it created itself by implementing compacting and generational GC.
  - pcwalton 9y ago
    What? TLABs allow a bump allocator with copying collection, which results in the least kind of fragmentation you can possibly have—zero! How can TLABs increase fragmentation?
    - geodel 9y ago
      You can read at: https://www.thinkmind.org/download.php?articleid=icons_2012_8_10_20033 https://www.thinkmind.org/download.php?articleid=icons_2012_.... "Thread-local allocation buffers (TLABs) are widely used in memory allocators of garbage-collected systems to speed up the fast-path (thread-local allocation) and reduce global heap contention yet at the expense of increased memory fragmentation. Larger TLABs generally improve performance and scalability but only up to the point where more frequent garbage collection triggered by increased memory fragmen- tation begins dominating the overall memory management overhead. Smaller TLABs decrease memory fragmentation but increase the frequency of executing the slow-path (global allocation) and thus may reduce performance and scalability..."
      - pcwalton 9y ago
        That isn't relevant to what we're discussing here. The problem of fragmentation across arenas that that paper describes is a problem with any system that uses thread-local caching, including Go's tcmalloc. The type of fragmentation we're discussing is fragmentation within a memory arena. That is the kind of fragmentation that only a copying/compacting collector can eliminate.
jerven 9y ago
I think that shipilev wrote this blog post after seeing that post. He and Gil Tene, of Azul Zing/C4 pauseless GC fame, don't seem to be impressed by the GO team GC claims. Mostly because the GO gc does fragment, which can lead to crashes when it shouldn't. The GO team seems to believe escape analysis means no need for generational hypothesis, while Gil and Shiplev think that escape analysis means less allocation (which does help collection, but not enough). Shiplev, these days works with the RedHat Shenadoah GC team. Which is low pause time (in the order of the Go Team promise) while compacting and fully parallel. So he knows a thing or two about modern GCs and JIT and compiler tech ;) Not to say that the Go team doesn't, it just that they might assume somethings which are not true for some apps.
- geodel 9y ago
  Don't know about him but Gil seems happy by Go's choices GC area. Here are Gil's view: https://groups.google.com/forum/#!searchin/mechanical-sympathy/Go$20gc%7Csort:relevance/mechanical-sympathy/JJTUs_jXw5A/55cRmOUoCwAJ https://groups.google.com/forum/#!searchin/mechanical-sympat... About Go: "Go's GC story is evolving. And it's doing so at a fairly quick pace. Judging it based on a current implementation and current choices is premature, I think. I think that the Go team's implementation priority focus on latency is a good one. And unlike others, I don't actually think there is a strong latency vs. throughput tradeoff in the long run." And Kind words about Hotspot: "The overall approach with HotSpot can be thought of as "start with a STW generational collector and increment your way to lower average/typical pauses in the old generations". E.g. all practical collectors in HotSpot use a monolithic stop-the-world copying newgen collector (not concurrent or incremental, monolithic, run-to-completion STW, always). And all collectors in HotSpot have a fallback to a full STW oldgen pause. The various non-monolithic-STW "cool modes" (Partially Concurrent non-compacting Oldgen in CMS, Incremental STW compaction in G1) are filters in the oldgen that occur between full STW newgen pauses and full STW oldgen pauses. They are "happy" when the filters work well enough to keep the STW newgen pauses in the tens of msec and delay the full-STW pauses for hours or days. And they consider it to be "ok and still working" even when those levels are not met." You can check Shenandoah pause times (20-45ms) : https://www.slideshare.net/RedHatDevelopers/shenandoah-gc-java-without-the-garbage-collection-hiccups-christine-flood https://www.slideshare.net/RedHatDevelopers/shenandoah-gc-ja... Decent for Java world but not really competing with Go. To add they seem very critical of Generational GC: "Generational GC pay a steep penalty for copying Data."

by geodel 9y ago

pizlonator 9y ago

Bump allocators don't require locks. Bump allocators are especially effective in the presence of thread-local caches. Whoever wrote that must not be very familiar with how memory management works.

pcwalton 9y ago

> And while a bump allocator can be simple and efficient for a single-threaded program, in a multi-threaded program like Go it requires locks. In general it's likely to be more efficient to allocate memory using a set of per-thread caches, and at that point you've lost the advantages of a bump allocator. Ian is extremely confused here. Every production multithreaded generational GC uses thread-local allocation buffers (edit: thanks to Filip for correcting my terminology).

pizlonator 9y ago
Very few production multithreaded generational GCs use per-thread nurseries. But probably all of them use thread-local caches, or what you might call per-thread caches. I think that's what you might have meant. Per-thread nurseries is a shit idea unless your language has extra-super-high levels of infant mortality. Remember that in a per-thread nursery genGC, the write barrier has to infect the pointed-to object with the global heap so that future stores to that object also trigger the barrier. In a normal genGC, the pointed-to object is unaffected; the stored-to object is merely shaded (or card-marked, or logged, or whatever) for revisiting. Humorously for parent's post, to my knowledge the first instance of a thread-local cache was the idea that a multithreaded compacting GC can chop off a slice of memory from the global bump allocator and then use it to service a thread-local allocator. Not 100% sure though because maybe Boehm and friends beat everyone to it.
- pcwalton 9y ago
  > Very few production multithreaded generational GCs use per-thread nurseries. > Per-thread nurseries is a shit idea unless your language has extra-super-high levels of infant mortality. Isn't that what TLABs are? HotSpot uses TLABs by default, unless my info is out of date… For example, [1] shows the generated assembler for object allocation, which uses nonatomic pointer bumps. I think we might be talking about different things by "per-thread nurseries". All I mean by a "per-thread nursery" is a TLAB. [1]: https://shipilev.net/jvm-anatomy-park/4-tlab-allocation/ https://shipilev.net/jvm-anatomy-park/4-tlab-allocation/
  - pizlonator 9y ago
    Like I said, you're thinking thread-local caches. TLABS are thread-local caches, not per-thread nurseries. There's a HUGE difference between a thread-local cache (which everyone uses and which you cite) and per-thread nurseries (which are an obscure idea that hardly anybody likes).
    - pcwalton 9y ago
      Yes. Apologies for using the wrong terminology :)
geodel 9y ago
And TLABs causes more memory fragmentations and which lead to more GCs and more need for memory compaction. So finally Java solved the problem it created itself by implementing compacting and generational GC.
- pcwalton 9y ago
  What? TLABs allow a bump allocator with copying collection, which results in the least kind of fragmentation you can possibly have—zero! How can TLABs increase fragmentation?
  - geodel 9y ago
    You can read at: https://www.thinkmind.org/download.php?articleid=icons_2012_8_10_20033 https://www.thinkmind.org/download.php?articleid=icons_2012_.... "Thread-local allocation buffers (TLABs) are widely used in memory allocators of garbage-collected systems to speed up the fast-path (thread-local allocation) and reduce global heap contention yet at the expense of increased memory fragmentation. Larger TLABs generally improve performance and scalability but only up to the point where more frequent garbage collection triggered by increased memory fragmen- tation begins dominating the overall memory management overhead. Smaller TLABs decrease memory fragmentation but increase the frequency of executing the slow-path (global allocation) and thus may reduce performance and scalability..."
    - pcwalton 9y ago
      That isn't relevant to what we're discussing here. The problem of fragmentation across arenas that that paper describes is a problem with any system that uses thread-local caching, including Go's tcmalloc. The type of fragmentation we're discussing is fragmentation within a memory arena. That is the kind of fragmentation that only a copying/compacting collector can eliminate.

jerven 9y ago

I think that shipilev wrote this blog post after seeing that post. He and Gil Tene, of Azul Zing/C4 pauseless GC fame, don't seem to be impressed by the GO team GC claims. Mostly because the GO gc does fragment, which can lead to crashes when it shouldn't. The GO team seems to believe escape analysis means no need for generational hypothesis, while Gil and Shiplev think that escape analysis means less allocation (which does help collection, but not enough). Shiplev, these days works with the RedHat Shenadoah GC team. Which is low pause time (in the order of the Go Team promise) while compacting and fully parallel. So he knows a thing or two about modern GCs and JIT and compiler tech ;) Not to say that the Go team doesn't, it just that they might assume somethings which are not true for some apps.

geodel 9y ago
Don't know about him but Gil seems happy by Go's choices GC area. Here are Gil's view: https://groups.google.com/forum/#!searchin/mechanical-sympathy/Go$20gc%7Csort:relevance/mechanical-sympathy/JJTUs_jXw5A/55cRmOUoCwAJ https://groups.google.com/forum/#!searchin/mechanical-sympat... About Go: "Go's GC story is evolving. And it's doing so at a fairly quick pace. Judging it based on a current implementation and current choices is premature, I think. I think that the Go team's implementation priority focus on latency is a good one. And unlike others, I don't actually think there is a strong latency vs. throughput tradeoff in the long run." And Kind words about Hotspot: "The overall approach with HotSpot can be thought of as "start with a STW generational collector and increment your way to lower average/typical pauses in the old generations". E.g. all practical collectors in HotSpot use a monolithic stop-the-world copying newgen collector (not concurrent or incremental, monolithic, run-to-completion STW, always). And all collectors in HotSpot have a fallback to a full STW oldgen pause. The various non-monolithic-STW "cool modes" (Partially Concurrent non-compacting Oldgen in CMS, Incremental STW compaction in G1) are filters in the oldgen that occur between full STW newgen pauses and full STW oldgen pauses. They are "happy" when the filters work well enough to keep the STW newgen pauses in the tens of msec and delay the full-STW pauses for hours or days. And they consider it to be "ok and still working" even when those levels are not met." You can check Shenandoah pause times (20-45ms) : https://www.slideshare.net/RedHatDevelopers/shenandoah-gc-java-without-the-garbage-collection-hiccups-christine-flood https://www.slideshare.net/RedHatDevelopers/shenandoah-gc-ja... Decent for Java world but not really competing with Go. To add they seem very critical of Generational GC: "Generational GC pay a steep penalty for copying Data."