7 ms·

For someone that's not very familiar with garbage collectors, does this mean that the GC will reduce or eliminate execution pauses that are common in GC'd langu

by Osiris 12y ago

For someone that's not very familiar with garbage collectors, does this mean that the GC will reduce or eliminate execution pauses that are common in GC'd languages?

bcinman 12y ago
My understanding is that there will still be pauses, but they'll be in the sub 10ms range rather than the 100ms range.
kid0m4n 12y ago
If I am understanding this right, it will do its best to limit the pause time to a predictable value
bradleyjg 12y ago
I believe the current plan is a hybrid setup, with both a stop the world and concurrent collector. See http://golang.org/s/go14gc http://golang.org/s/go14gc and the HN discussion https://news.ycombinator.com/item?id=8148666 https://news.ycombinator.com/item?id=8148666 It is possible to write a pauseless garbage collector (e.g. Azul for java) but it is a major undertaking and the powers that be have decided not to do so for now. See this discussion https://groups.google.com/forum/#!topic/golang-dev/GvA0DaCI2BU https://groups.google.com/forum/#!topic/golang-dev/GvA0DaCI2...
- 616c 12y ago
  I assume you are referring to the Go GC efforts. I would imagine (someone with zero compiler, VM design, or PL design experience), that is a humongous undertaking. But if it is interesting to anyone, I used to follow news about the FOSS counter-effort to Azul (which ironically did start open source with OpenJDK, but then what corporate from what I understood from Azul people posting OpenJDK lists), Shenandoah. https://rkennke.wordpress.com/2013/06/10/shenandoah-a-pauseless-gc-for-openjdk/ https://rkennke.wordpress.com/2013/06/10/shenandoah-a-pausel... I will start looking into this again because I do not remember hearing much since.
  - pjmlp 12y ago
    Red Hat is driving the effort. There was a talk at JavaONE.
Buttons840 12y ago
> The goal of the Go 1.5 (June 2015) Garbage Collector (GC) is to reduce GC latency, making Go acceptable for implementing a broad spectrum of systems requiring low response times. Quantitatively this means that for adequately provisioned machines limiting GC latency to less than 10 milliseconds (10ms), with mutator (Go application code) availability of more than 40 ms out of every 50 ms. Hardware provisioning should allow for in-memory heap sizes twice as large as reachable memory and 25% of CPU cycles, typically one out of 4 hardware threads, available for GC tasks. These goals align with a future with ever-increasing numbers of hardware threads and an ever-increasing amount of memory, all within an ever-decreasing power and expense budget. >Tactically, we will use a hybrid stop the world (STW) / concurrent garbage collector (CGC). The STW piece will limit the amount of time goroutines are stopped to less than 10 milliseconds out of every 50 milliseconds. If the GC completes a cycle in this time frame, great. If not, the GC will transition into a concurrent GC for the remainder of the 50 millisecond block. This process will repeat until the GC cycle completes. As a practical matter if one has a 50 millisecond response quality of service (QOS) requirement one should expect to have 40 milliseconds in which to do mutator tasks. These numbers assume hardware equivalent to a generic $1000 desktop box running Linux. Source: http://llvm.cc/t/go-1-4-garbage-collection-plan-and-roadmap-golang-org/33 http://llvm.cc/t/go-1-4-garbage-collection-plan-and-roadmap-... It appears the answer to your question is no. My interpretation of the above is that, like other garbage collectors (Haskell's comes to mind, I don't know much about other GCs), some garbage collection will be able to happen concurrently with no pausing, but some collection will still require "stop the world" pauses. Go's goal to limit those stop the world pauses to 10 ms is not something I have seen in many other garbage collectors. The only other garbage collector I've encountered with a similar feature is Nim's garbage collector which claims to allow a limit on how long each garage collection pass will take, similar to what Go is trying to do. I wonder if Go want this 10 ms limit to be a hard or soft limit? * Take all I say about garbage collectors with a grain of salt. I have had some interest in their various features, but am no expert.
- TylerE 12y ago
  That said, 5-10ms GC pauses are generally not noticeable.
arnsholt 12y ago
This should reduce pauses, I think. However, it's important to note that latency (short pauses) and raw throughput are antagonistic criteria for GCs. A concurrent GC means that you can collect garbage while other code is running, but to get it working you need to introduce overhead both when reading and writing, which means that time spent on GC-related things will go up, even if latency goes down. In fact, if memory serves, the best GC strategy for raw throughput is actually stop-the-world, since there's so little overhead for memory accesses (basically you can just follow pointers without any bookkeeping). Of course, ten-second (or multi-minute) GC pauses are probably unacceptable for most tasks. =)
tomp 12y ago
I only skimmed the document, but couldn't find any details about the implementation; it deals mostly with how to pace the GC so that it doesn't run out of memory. I can give you a few hints, though. The title says concurrent GC, which is, unfortunately, usually a misnomer in GC literature - it usually means that parts of the GC are concurrent with the mutator (user program), but that there are still synchronization points where pausing the mutator is required. If GC that is actually concurrent 100% of the time, fully-concurrent or on-the-fly label (edit: and pauseless as well, as bradleyjg mentioned) is used. Second, while it's not that hard to implement a mostly-concurrent GC, it's practically impossible to implement an efficient compacting, on-the-fly GC, as it would require read barriers during the compaction phase, which would significantly slow down the program. Azul makes such a GC, but they use privileged (kernel) code to implement read barrier (mutator threads still need to be paused/sychronized with, but not all at the same time) (edit2: Azul's C4 collector doesn't use a kernel read barrier, and apparently their read barrier is much more efficient than most). I don't know if Go features a compacting GC (although many languages do, as that's the only thing that can prevent unbounded heap growth over time), but if it does, it's almost certainly not on-the-fly GC. To summarize, I assume this will only reduce the pauses, not eliminate them.
- deleted 12y ago
  [deleted]
- rdtsc 12y ago
  > The title says concurrent GC, which is, unfortunately, usually a misnomer in GC literature It is confusing. I think they started using pausless as the term now instead to distinguish between the two. > Azul makes such a GC Anyone who is interested in this, should read how that is implement. Really fascinating and cool. However they are not the only ones. Erlang's GC is also pause-less and concurrent between actors. So GC in one actor won't pause other actors on a multi-core system.
  - easytiger 12y ago
    > Anyone who is interested in this, should read how that is implement. Are is it implemented? my understanding was that it retains 4 copies of the entire heap in memory and continuously switches between them, or something like that.
zamalek 12y ago
I don't think there is any current theory that completely eliminates stop-the-world. Taking the .Net concurrent GC as a reference point, it will drastically reduce the amount of times the GC needs to stop-the-world. off-topic warning > someone that's not very familiar with garbage collectors Something that will greatly increase your understanding of GCs is knowing what they actually are: a GC is actually not technically a memory-reclamation device, instead it is a device that simulates infinite memory; if you actually have infinite memory noop is actually a GC. Understanding that is key to understanding the conservative optimizations that some people recommend, if you are too aggressive with how you treat the GC and memory pressure you program might fall apart when influenced by a different GC implementation. Correct GC treatment results in a program that executes well under any GC implementation - including a concurrent GC. There are probably some programs already out there that rely too heavily on the current Go GC and they will likely need to re-align with the new GC implementation. Always be very careful when reading literature that goes very heavily into the implementation of a specific GC, and how you can capitalize off of its implementation. Good literature on GCs has truisms even in the noop GC scenario.
tmd83 12y ago
I haven't really read beyond the intro. I will have to read it in a fresh mind in the morning. Btw. I'm not a GC expert but I read/watched some expert commentary by some true expert. In common GC terminology (as explained already in the thread) concurrent & pauseless are not the same. I know only one GC (Azul's C4) that is pauseless. Even concurrent GCs are rare and hard to implement and GO is doing that with 1.5 There are different ways to implement concurrent GC. My knowledge is basically limited to JVM implementations and even there multiple approaches exists. Beyond the core ideas to handle concurrent GC and mutator (application) thread lies a lot of details on exactly how to lay things out in memory, whether to compact, how to pace mutator vs. GC etc. My conclusions from quite a few GC talks and the evolution of JVM GCs is that the biggest part (most man-hour involved) could very well be in fine tuning the heuristic for these details. But maybe more important for the purpose of this discussion is probably the fact that concurrent GC usually has few things balancing against each other 1. Throughput penalty (how much of the CPU is for GC, how much for application) 2. Memory overhead (how much you have to over provision your heap for GC to perform optimally) 3. How big a single pause time you will allow Generally when you make one of them better the other suffers. Some GC focuses more on one than the other and also allows to tune some of the parameter. JVM GCs I think have too many requirements and expectations on them from historic and wide spread usage. It doesn't help that in Java controlling allocation is difficult, its generally a memory hog model, the runtime is huge etc. I think the GO team is doing a nice thing by setting up the expectations early in the life of the language, the fact that its more memory/allocation friendly (if the developer wants it from what I read) and the reality of modern machine (lots of core & ram) and setting their priority. They are optimising for predictable and low pause, predictable throughout at fairly high penalty. Its hard to tune JVM GCs for 10ms pause (its doable by the experts for good code) but they are also unlikely to incur a 20% throughput penalty nor 100% heap over provision in most cases. To be fair low pause optimisation in JVM GC also incur high heap usage (often twice like GO proposal). I expect that the limit of 10ms is a soft limit though. By prioritising this heavily and the nature of GO they will probably achieve it with a lot more predictability than most other GC I presume but I don't know of any practical way to guarantee it (from my limited knowledge of course of a GC user and not implementor) except reducing mutator throughput excessively which contradicts with their other goal. But I would be very curious to see how predictable a GC GO team can make without requiring excessive tuning that JVM GC tend to require.

by Osiris 12y ago

For someone that's not very familiar with garbage collectors, does this mean that the GC will reduce or eliminate execution pauses that are common in GC'd languages?

bcinman 12y ago

My understanding is that there will still be pauses, but they'll be in the sub 10ms range rather than the 100ms range.

kid0m4n 12y ago

If I am understanding this right, it will do its best to limit the pause time to a predictable value

bradleyjg 12y ago

I believe the current plan is a hybrid setup, with both a stop the world and concurrent collector. See http://golang.org/s/go14gc http://golang.org/s/go14gc and the HN discussion https://news.ycombinator.com/item?id=8148666 https://news.ycombinator.com/item?id=8148666 It is possible to write a pauseless garbage collector (e.g. Azul for java) but it is a major undertaking and the powers that be have decided not to do so for now. See this discussion https://groups.google.com/forum/#!topic/golang-dev/GvA0DaCI2BU https://groups.google.com/forum/#!topic/golang-dev/GvA0DaCI2...

616c 12y ago
I assume you are referring to the Go GC efforts. I would imagine (someone with zero compiler, VM design, or PL design experience), that is a humongous undertaking. But if it is interesting to anyone, I used to follow news about the FOSS counter-effort to Azul (which ironically did start open source with OpenJDK, but then what corporate from what I understood from Azul people posting OpenJDK lists), Shenandoah. https://rkennke.wordpress.com/2013/06/10/shenandoah-a-pauseless-gc-for-openjdk/ https://rkennke.wordpress.com/2013/06/10/shenandoah-a-pausel... I will start looking into this again because I do not remember hearing much since.
- pjmlp 12y ago
  Red Hat is driving the effort. There was a talk at JavaONE.

Buttons840 12y ago

> The goal of the Go 1.5 (June 2015) Garbage Collector (GC) is to reduce GC latency, making Go acceptable for implementing a broad spectrum of systems requiring low response times. Quantitatively this means that for adequately provisioned machines limiting GC latency to less than 10 milliseconds (10ms), with mutator (Go application code) availability of more than 40 ms out of every 50 ms. Hardware provisioning should allow for in-memory heap sizes twice as large as reachable memory and 25% of CPU cycles, typically one out of 4 hardware threads, available for GC tasks. These goals align with a future with ever-increasing numbers of hardware threads and an ever-increasing amount of memory, all within an ever-decreasing power and expense budget. >Tactically, we will use a hybrid stop the world (STW) / concurrent garbage collector (CGC). The STW piece will limit the amount of time goroutines are stopped to less than 10 milliseconds out of every 50 milliseconds. If the GC completes a cycle in this time frame, great. If not, the GC will transition into a concurrent GC for the remainder of the 50 millisecond block. This process will repeat until the GC cycle completes. As a practical matter if one has a 50 millisecond response quality of service (QOS) requirement one should expect to have 40 milliseconds in which to do mutator tasks. These numbers assume hardware equivalent to a generic $1000 desktop box running Linux. Source: http://llvm.cc/t/go-1-4-garbage-collection-plan-and-roadmap-golang-org/33 http://llvm.cc/t/go-1-4-garbage-collection-plan-and-roadmap-... It appears the answer to your question is no. My interpretation of the above is that, like other garbage collectors (Haskell's comes to mind, I don't know much about other GCs), some garbage collection will be able to happen concurrently with no pausing, but some collection will still require "stop the world" pauses. Go's goal to limit those stop the world pauses to 10 ms is not something I have seen in many other garbage collectors. The only other garbage collector I've encountered with a similar feature is Nim's garbage collector which claims to allow a limit on how long each garage collection pass will take, similar to what Go is trying to do. I wonder if Go want this 10 ms limit to be a hard or soft limit? * Take all I say about garbage collectors with a grain of salt. I have had some interest in their various features, but am no expert.

TylerE 12y ago
That said, 5-10ms GC pauses are generally not noticeable.

arnsholt 12y ago

This should reduce pauses, I think. However, it's important to note that latency (short pauses) and raw throughput are antagonistic criteria for GCs. A concurrent GC means that you can collect garbage while other code is running, but to get it working you need to introduce overhead both when reading and writing, which means that time spent on GC-related things will go up, even if latency goes down. In fact, if memory serves, the best GC strategy for raw throughput is actually stop-the-world, since there's so little overhead for memory accesses (basically you can just follow pointers without any bookkeeping). Of course, ten-second (or multi-minute) GC pauses are probably unacceptable for most tasks. =)

tomp 12y ago

I only skimmed the document, but couldn't find any details about the implementation; it deals mostly with how to pace the GC so that it doesn't run out of memory. I can give you a few hints, though. The title says concurrent GC, which is, unfortunately, usually a misnomer in GC literature - it usually means that parts of the GC are concurrent with the mutator (user program), but that there are still synchronization points where pausing the mutator is required. If GC that is actually concurrent 100% of the time, fully-concurrent or on-the-fly label (edit: and pauseless as well, as bradleyjg mentioned) is used. Second, while it's not that hard to implement a mostly-concurrent GC, it's practically impossible to implement an efficient compacting, on-the-fly GC, as it would require read barriers during the compaction phase, which would significantly slow down the program. Azul makes such a GC, but they use privileged (kernel) code to implement read barrier (mutator threads still need to be paused/sychronized with, but not all at the same time) (edit2: Azul's C4 collector doesn't use a kernel read barrier, and apparently their read barrier is much more efficient than most). I don't know if Go features a compacting GC (although many languages do, as that's the only thing that can prevent unbounded heap growth over time), but if it does, it's almost certainly not on-the-fly GC. To summarize, I assume this will only reduce the pauses, not eliminate them.

deleted 12y ago
[deleted]
rdtsc 12y ago
> The title says concurrent GC, which is, unfortunately, usually a misnomer in GC literature It is confusing. I think they started using pausless as the term now instead to distinguish between the two. > Azul makes such a GC Anyone who is interested in this, should read how that is implement. Really fascinating and cool. However they are not the only ones. Erlang's GC is also pause-less and concurrent between actors. So GC in one actor won't pause other actors on a multi-core system.
- easytiger 12y ago
  > Anyone who is interested in this, should read how that is implement. Are is it implemented? my understanding was that it retains 4 copies of the entire heap in memory and continuously switches between them, or something like that.

zamalek 12y ago

I don't think there is any current theory that completely eliminates stop-the-world. Taking the .Net concurrent GC as a reference point, it will drastically reduce the amount of times the GC needs to stop-the-world. off-topic warning > someone that's not very familiar with garbage collectors Something that will greatly increase your understanding of GCs is knowing what they actually are: a GC is actually not technically a memory-reclamation device, instead it is a device that simulates infinite memory; if you actually have infinite memory noop is actually a GC. Understanding that is key to understanding the conservative optimizations that some people recommend, if you are too aggressive with how you treat the GC and memory pressure you program might fall apart when influenced by a different GC implementation. Correct GC treatment results in a program that executes well under any GC implementation - including a concurrent GC. There are probably some programs already out there that rely too heavily on the current Go GC and they will likely need to re-align with the new GC implementation. Always be very careful when reading literature that goes very heavily into the implementation of a specific GC, and how you can capitalize off of its implementation. Good literature on GCs has truisms even in the noop GC scenario.

tmd83 12y ago

I haven't really read beyond the intro. I will have to read it in a fresh mind in the morning. Btw. I'm not a GC expert but I read/watched some expert commentary by some true expert. In common GC terminology (as explained already in the thread) concurrent & pauseless are not the same. I know only one GC (Azul's C4) that is pauseless. Even concurrent GCs are rare and hard to implement and GO is doing that with 1.5 There are different ways to implement concurrent GC. My knowledge is basically limited to JVM implementations and even there multiple approaches exists. Beyond the core ideas to handle concurrent GC and mutator (application) thread lies a lot of details on exactly how to lay things out in memory, whether to compact, how to pace mutator vs. GC etc. My conclusions from quite a few GC talks and the evolution of JVM GCs is that the biggest part (most man-hour involved) could very well be in fine tuning the heuristic for these details. But maybe more important for the purpose of this discussion is probably the fact that concurrent GC usually has few things balancing against each other 1. Throughput penalty (how much of the CPU is for GC, how much for application) 2. Memory overhead (how much you have to over provision your heap for GC to perform optimally) 3. How big a single pause time you will allow Generally when you make one of them better the other suffers. Some GC focuses more on one than the other and also allows to tune some of the parameter. JVM GCs I think have too many requirements and expectations on them from historic and wide spread usage. It doesn't help that in Java controlling allocation is difficult, its generally a memory hog model, the runtime is huge etc. I think the GO team is doing a nice thing by setting up the expectations early in the life of the language, the fact that its more memory/allocation friendly (if the developer wants it from what I read) and the reality of modern machine (lots of core & ram) and setting their priority. They are optimising for predictable and low pause, predictable throughout at fairly high penalty. Its hard to tune JVM GCs for 10ms pause (its doable by the experts for good code) but they are also unlikely to incur a 20% throughput penalty nor 100% heap over provision in most cases. To be fair low pause optimisation in JVM GC also incur high heap usage (often twice like GO proposal). I expect that the limit of 10ms is a soft limit though. By prioritising this heavily and the nature of GO they will probably achieve it with a lot more predictability than most other GC I presume but I don't know of any practical way to guarantee it (from my limited knowledge of course of a GC user and not implementor) except reducing mutator throughput excessively which contradicts with their other goal. But I would be very curious to see how predictable a GC GO team can make without requiring excessive tuning that JVM GC tend to require.