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.
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.
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.
In order not to have mutator threads waiting for GC threads, they use worksharing. When the mutator wants to read from a page that is evacuting then, it will move that object itself (this is where the need the read barrior).
This all requires very small amount of syncronisation, there is one small checkin point that every thread has to visit, then its all concurrent again. The pauses are only relate to how long it takes everybody to checkin, not the size of the heap, or the size of the pages.
This allows multible 100GB with very small pause times.
I just wrote this from memory and its of course more complicated, but this might help you to think about it.
Go doesn't try (yet) to compact heap by moving objects there. They first need a solution not to break C code.
https://groups.google.com/forum/#!msg/golang-nuts/AFEf6VM-qr...
As you say, the pacing strategy is about delivering good performance, not about pause times. Pause times are a separable concern.
The current (in development) GC is not pauseless. It stops the world to finish each collection. Those pauses are very short (well under 10ms, often under 1ms) so we are not worrying about eliminating them at the moment. But we know how to do that if we choose to.
http://dl.acm.org/citation.cfm?id=376810 (Sapphire) is the current state of the art for pauseless collectors, and one of the authors is the primary developer working on the Go GC now.
As a side note, if you don't compact then pauseless becomes much easier. And while it was taken as gospel for decades, it's not clear that on today's hardware you necessarily need to compact, ever. (Cue flames.)
Yeah, my (theoretical) designs skipped compaction as well. I would have different arenas for differently-sized objects instead (akin to e.g. TCMalloc), which could be reused very efficiently (although that's probably a common allocation technique by now). Although you could still grow a huge heap in very specific situations, if the program behaved at least somewhat consistently (kept allocating objects of roughly the same size), you wouldn't need compaction at all.
Again, this is just theory, unfortunately :) I'll check out Sapphire!
Source: 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.
The JVM's G1 collector has pause time and throughput goals for a long time now. This is not new or exotic.
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.
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/GvA0DaCI2...
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-pausel...
I will start looking into this again because I do not remember hearing much since.
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. =)
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.
Just to add that JamaicaVM, Aonix and Websphere Real Time GCs do have hard limits on collection times according to their documentation, but I never used them so I cannot judge how they really behave.
Well, although these things are somewhat true obviously Java didn't start out that way. It started out looking more like Go. The JVM got this way because it is so heavily used for so many things. To paraphrase jwz, the JVM is big because your needs are big.
Go doesn't seem to have dramatically different goals to Java. They're both GCd languages with a standard library, memory safe code etc. The logical conclusion is that if Go became as widely used for as long as Java, it'd end up looking quite similar. The Go runtime is already walking the same path as the JVM guys did, albeit with ahead of time instead of just in time compilation.
> Its hard to tune JVM GCs for 10ms pause (its doable by the experts for good code)
That statement lacks too much context to mean anything. Most JVM GC pauses are young gen only and those take virtually no time at all, 10ms would be very high for such a collection. Other pauses can be just a few milliseconds as long as you don't actually run out of memory (this will force a full stop the world collection), but it tends to depend on how much free RAM you have and the sizes of the heaps, etc.
State of the art collectors like Azul's and Shenandoah aim to collect heaps that are hundreds of gigabytes with pause times in the few milliseconds or less range.
I don't know why Go would be more allocation friendly than Java, but I'm not a Go expert. What features are you thinking of?
I did say that JVM is the way it is due to its wide spared use and that GO team is setting expectations of GC overhead. There are too many java programmers without any thought of GC.
> That statement lacks too much context to mean anything. Most JVM GC pauses are young gen only and those take virtually no time at all, 10ms would be very high for such a collection. Other pauses can be just a few milliseconds as long as you don't actually run out of memory (this will force a full stop the world collection), but it tends to depend on how much free RAM you have and the sizes of the heaps, etc. > State of the art collectors like Azul's and Shenandoah aim to collect heaps that are hundreds of gigabytes with pause times in the few milliseconds or less range.
I was expecting that anyone who knows generational GC already knows how fast most young gen GC pauses are. When you talk about pause time goals you talk about worst case times which is old gen GC. And for a big and complex heap getting to 10ms pause time is not at all easy in my limited experience. CMS and lots of memory helps but it is still no way trivial.
Azul's is completely different and Shenandoah has big expectations and some nice design but only time will tell if the theories works well in practice (I do hope so).
You commented on G1 in another place and while I was highly anticipating G1 in my own latency sensitive server G1 performed much worse than CMS. I didn't try to tune it much but the point remains its not as easy as just use G1, set the pause time goals and you are done.
All GC (in JVM world at least) seem to start with good theories than you find it doesn't work for all kinds of realistic usage pattern and adjust. G1 had to change a lot of their assumptions once it met the real world (from the JavaOne talks of Oracle people).
> I don't know why Go would be more allocation friendly than Java, but I'm not a Go expert. What features are you thinking of?
I'm purely a Java guy but I think someone already gave some answer.