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?
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.
> 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.
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.
Or a low latency environment where you need to reliably turn around a piece of data in 500us 1 billion times a day. If you do it in 1000us then the information is no longer of value.
> 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
The JVM's G1 collector has pause time and throughput goals for a long time now. This is not new or exotic.
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. =)
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.
> 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.
> 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.
That is not at all how it works. Essentially it splits the hole heap up into pages, pages have a state empty, allocating, evacuting. There are GC threads who constantly reallocate objects from pages that have high amount of unreachable objects to new pages.
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.
Erlang's threads (called processes in Erlang) don't observably share data, so "concurrent" GC is basically a stop-the-world GC on a thread's local heap. There might be some thread synchronisation involved, but I assume it's much simpler to implement, because you don't have to deal with mutability.
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.)
> 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!
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.
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.
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.
> 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.
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?
> 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.
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.
The JVM has several different types of GC algorithms, many of which are tunable.
(A better place to look to understand GC might actually be LuaJIT or Erlang. I say "might" because while I've been told that both have simple to understand implementations, I have not bothered myself to actually look at them.)
Isn't LuaJIT's GC not that robust? I believe Mike Pall has lamented it as being the worst part of the compiler. I think he's wanted to rewrite it from scratch for a while, but doesn't yet have the time or resources.
Mike last updated that page in 2012, and I'm not sure if he's publicly committed any code for it. I seem to recall him requesting a sponsorship for it.
As far as I can tell, the JVM GC is (not surprisingly) significantly more mature. The JVM has a concurrent mark-sweep algorithm that works similarly to what's described in this document, but more importantly IMO the JVM's GC is generational, and it appears Go's GC is not.
In the JVM, the CMS only occurs on the oldest generation which contains objects that were in use for a while, whereas objects that are created and discarded quickly are cleaned up in younger generations with a copying collector, which avoids memory compaction by switching back and forth between 2 equally sized memory blocks. This means much of the time the JVM can avoid doing a full CMS and keep the time spent in GC only a few ms per second.
I guess it depends on what your use case is. If you're writing low-latency server applications that don't have loads of long-lived internal state and you have memory to spare, the JVM's CMS GC is going to be way more efficient than Go's. But if you're constrained for memory then avoiding copying collectors and generational heaps is your best bet, but you'll pay for it in GC time. Of course the JVM has other GC algorithms like G1, but I don't have much experience with those.
> the JVM's GC is generational, and it appears Go's GC is not.
Correct, that's slated for the 1.6 timeframe:
> While other goals may intervene, 1.6 will most likely be used to improve throughput by adding bump pointer allocation as well as a generational copy collector for nursery (new) spaces. The mature (old) space will be managed using our concurrent GC.
But if I'm reading it correctly GO GC will actually rely on a using a lot of memory to ensure it can hit the pause time goal.
As far as I understand copying/generational collector by themselves don't add a lot of memory overhead. They simply add more complexity. You tend to require a lot more memory to ensure most your allocation & allocation happens in nursery (which can be scary fast and low overhead) and to allow the old generation GC to pace itself.
I wonder how much of the 20% expected GC overhead comes from the fact that they can't do the nursery GC optimisation and whats the expected overhead when it goes generational in 1.6
One thing I absolutely hate with CMS is the fallback single thread collector for Old Gen that makes for a scary possibility. Don't think GO will have one of those which is nice to see (not for me though :().
G1 is the most advanced and is where the main development seems to be happening (ignoring Shenandaoh which is a Red Hat project to create an Azul style virtually-pauseless megascale GC).
For example the G1 garbage collector can deduplicate strings in the heap. This can be a big win for servers and IDEs.
In the latest update I read that G1 is also able to adapt itself to memory pressure in the entire operating system. If you start an app next to the JVM and the OS available memory drops, it'll start to use more CPU time for collection and shrink the heap so it can hand RAM back to the OS and reduce pressure again.
G1 can do lots of other nifty things, but it uses more RAM than ParCMS so it's not the default at the moment. You have to opt into it. I think they want to make it the default one day.
Does anyone else feel like this is reinventing the JVM Garbage Collection technology - which has at least 20 years of calendar experience and countless man hours of engineering research in the real world?
Whatever your thoughts are on Java the language - would it not make sense to focus efforts on the OpenJVM project and all the languages it can support?
Genuinely curious if this seemingly "reinvent the wheel" approach is going to provide benefits.
That's a valid question. I think the answer is: not everybody wants a language based on a relatively heavy/large VM. E.g. Go fits in much more with the UNIX tradition than Java does.
Writing a GC is an iterative process and the Go team are taking the steps to implement a modern GC. You don't work for 2 years and then throw it all in at once.
Despite all that effort, Java GC still has a lot of problems today; long pauses still happen in heavily loaded servers unless they're tuned carefully. Sometimes taking a fresh approach is worthwhile.
Not every language fits on the JVM, we shouldn't only have one VM for everything. GO is natively compiled and the runtime is only for GC very different models then Java
What would be the point of using Go if it needed a VM ?
No VM is one of the reason people use Go, along with easy concurrency backed directly in the language and not as a third party framework.
IF you find the JVM so awesome ,keep using it. I personally think the memory cost isnt worth it ,and when I say cost, I mean the actual cost in $$$. Hardware might be cheap, the cloud isn't.
Sure ,if you're willing to pay $3000 per seat or use something free that hasn't been updated to the latest JDK. And it doesn't come with a guarantee of a lower memory footprint.
Does anyone else feel like this is reinventing the JVM Garbage Collection technology - which has at least 20 years of calendar experience and countless man hours of engineering research in the real world?
Funny, but over a decade ago, we Smalltalkers were once asking: "Does anyone else feel like this is reinventing Smalltalk GC and JIT VM technology - which has years of calendar experience and countless man hours of engineering research in the real world?"
Speaking as someone who writes go code every day right now, I like the language for a number of reasons, including the fact that it can be compiled and deployed without anything like the sort of build/deploy insanity that a modern java installation comes with.
So, I'd rather hit my head against the wall on GC problems while smart people improve it than hit my head against the wall with a MASSIVE deploy/build headache that definitely won't go away for a bunch of technical, political and historical reasons.
> Speaking as someone who writes go code every day right now, I like the language for a number of reasons, including the fact that it can be compiled and deployed without anything like the sort of build/deploy insanity that a modern java installation comes with.
Once properly set up, deploying Java is usually a one click affair, not sure what insanity you are talking about.
Also, Go is compiled natively which certainly complicates the deployment mode (and expect more complications down the line once Go supports dynamic loading).
Either way, Go's deployment model doesn't have much to do with the language and it will become more complex if the language becomes more popular.
What kind of insanity? Are you talking about desktop or server apps?
Whichever you mean, you can create apps that have self contained JREs with the javapackager tool. But most server setups don't seem to need it. If you have a broken IT environment where your admins refuse to upgrade the JVM, that can be an issue, but then you might find yourself being told to stick with an obsolete version of Go in future too in such an environment.
I'm not trying to start a religious conversation; so with that caveat, I'll respond -- By insanity, I'm referring to the need to grok stuff like this page:
Building a large java application is not something I'm an expert at, but I have spent many hours of my life fighting with maven and ant and dependencies, happily some time ago.
By comparison, there's "go build". Or if you need auto-cross-compiling, there's goxc. While an IT manager might limit the version of go on a server, it would have no impact on most go developers; I can build a self-contained binary for linux right from my Macbook Air in under 2 seconds with a single command. Or using goxc, I can build for all binary targets in very short order.
To me reducing this sort of cognitive load on build/deployment is a HUGE benefit go provides, especially to junior developers or teams with different backgrounds.
Building in Java is also a one line command. Deploying is also often a one line command (or a one click affair).
The fact that Go is natively compiled makes this kind of deployment a bit more problematic, and it's bound to get more complicated once Go supports dynamic loading.
I'm not trying to make a judgment call between Java and Go here, just pointing out that saying that one of these language is insanely more complicated to deploy than the other doesn't make much sense.
> Does anyone else feel like this is reinventing the JVM Garbage Collection technology - which has at least 20 years of calendar experience and countless man hours of engineering research in the real world?
No, because GCs optimizations are very dependent on the semantics of the programming language.
There isn't something like a general purpose GC algorithm for every type of programming language out there.
Go is a drastically different language than Java. And porting over Java's GC wouldn't make sense.
In Java, everything except primitive types is a pointer. In Go, on the other hand, programming "by value" is encouraged (pointers are explicit, never implicit). In Go, it's possible to actually avoid creating garbage altogether - you have a decent amount of control of where memory gets allocated.
Thus porting Java's GC, which has been highly optimized to deal with hundreds of short-lived objects whose allocation you as a Java programmer have no control over, wouldn't make sense - it's optimized in all the wrong places, for Go, basically.
Yeah, but we're not comparing apples and oranges here.
The Go team have already adapted GCC to their language, for example. They could have also adapted the JVM. For instance the Java guys are adding value types at the moment, but most of the reason it's hard/slow for them is backwards compatibility with existing code. Go doesn't interop with anything except C anyway, so they could just throw that requirement out and have a customised GoVM that supports value types and so on, whilst reusing all the other technology in there.
> Whatever your thoughts are on Java the language - would it not make sense to focus efforts on the OpenJVM project and all the languages it can support?
Putting Go on the JVM would be taking a language that only has a few "great" features (fast compile/startup time, decent memory efficiency, simple static binary output) and neutering it to the point of irrelevance.
(Off-topic: Figures 1 & 2 are graphically simple and tidy. Does anyone know what software they used to generate them? Or failing that, what software is good at generating such graphics?)
I'm very excited about this. If they can meet their goal, this will make Go much more suitable for online "real-time" (in the colloquial technical sense) applications like game servers. I'm currently starting on my 2nd "game server" in golang. (To be fair, it's much more server than game as of yet.)
More suitable sure but I'm not convinced you'd want to use anything but C or C++ for a server that needs to be as "real-time" as possible. I wish GO could use RAII or another memory scheme so they could drop GC altogether.
If you have pause of only 10ms it's pretty good even for a gameserver.
10ms is 100fps ( server side ) the only game server that fast I know of is the source engine with CS:Go.
Here's another way of seeing it: if your target tick rate is 60Hz (~16ms), when the GC decides to trigger a collection, you lose most of your time budget. You'd have 6ms left on average, sometimes less, so to avoid dropping any frames you'd probably want your tick routine to complete in 5ms. In other words, when it comes to work that must be done every tick (which is probably most of it), you could only safely use less than a third of available CPU time!
I guess dropping a single frame on occasion may not be that bad, and the GC parameters could be retuned (and other GC languages have lower latency), and you could minimize the amount of garbage created, but still, that's not a good situation to be in.
What I've heard is that games aren't particularly heavy on the GC anyway, because they load in the objects in the level and then they don't create much else in terms of objects. There's just not all that much to be collected. I guess it's a bit more complicated for open-world games that need to load and delete game world objects on-the-fly, though.
It depends. Sure you can preload all your world props and level entities, but what about things like projectiles being fired, travelling, and then being de-allocated?
A good strategy for handling this in a GC'd language is using the factory / pool patterns, so during level loading you instantiate 100 "empty" projectile entities that you can re-use. When a projectile is "fired" you request a Projectile from the ProjectilePool, add its initial position/speed/whatever, then add it to the world. It goes through its trajectory, maybe hits a wall, and then you release it back to the ProjectilePool where it is cleared and can be re-used later.
How big would a projectile be? I'm not super familiar with how games encode their state, but I doubt things like projectiles would account for much memory. Which makes me think that it wouldn't cause problems with GC.
That's true, but as slimsag pointed out below, long GC pauses (which are what we're trying to avoid) are caused by large numbers of heap-allocated objects, not by the size of the objects.
The 101 projectiles case is not such a useful what-if in practice. It's a game, so your final tuning comes down to "what will hit my framerate target and memory budget," not what a user requested. If it struggles to keep up with 101 projectiles, you have to either design it down or accept dropped frames in the most demanding situations. So a pool's size limit acts as a guide for the other budgeting considerations anyway - and it plays well with the traditionally constrained memory budgets of console games.
Of course, AAA game engines today will employ custom low-level allocation strategies in order to squeeze out the last few percentage points where they deal with dynamic data - but if your aims are more modest, and you harken back to 80's era gaming, most of those games had a nearly or entirely static memory map. Besides being a poor fit for those tiny microprocessors, dynamic allocation enables out-of-memory and fragmentation errors to exist, leading us back to the "hard limits on instancing" strategy again.
GC still incurs overhead where it has to trace, even if you've pooled everything. Reference counting pulls ahead of tracing collectors in the situation of heavy object persistence, despite being more expensive as a general allocation method. As well, it has predictable latency, which is more important for meeting real-time requirements.
(N.B. as systems parallelize, they become more bound by latency considerations. Seven workers may finish early, but delivery will still get bottlenecked by the eighth slow one.)
More suitable sure but I'm not convinced you'd want to use anything but C or C++ for a server that needs to be as "real-time" as possible.
For what value of "as possible?" It's kind of a miracle that twitch game mechanics FPS work at all with typical Internet latencies, which is one of the various reasons why I'm not doing that. "As possible" in my situation, doesn't include the resources to do that.
I wish Go could use RAII or another memory scheme so they could drop GC altogether.
There's always Rust. Also, Erlang can "cheat" at GC in some ways due to immutability. Server side Swift has potential as well.
Really depends on the use case. Obviously "real-time" in a money context is very different than gaming. For gaming GO will probably be fine but that's also depending on how the game can scale.
> There's always Rust.
I've heard good things about rust though C++ is also pretty fantastic but I guess it's not as popular anymore.
You can still stack allocate things in Go. And use closures when you need nested scopes.
This lets you take garbage off the heap, and avoid GC all together if you want to.
I believe Go does escape analysis so you can still shuffle around pointers to local structs within a stack frame without causing a heap allocation.
edit: That being said you can't really implement something like refcounting for structs you pass around by pointer outside the local stack frame without the compiler emitting an allocation on the heap. To totally avoid using the GC you'll need to do a lot of copying. And there aren't destructors.
Watching you "manual memory all the way" dudes struggle with simple concurrency as much as you do, I'd hate to throw away a GC just for that extra teeny bit of performance.
Well, the 10ms cited as desired GC latency is hardly an extra teeny bit of performance for a game server which would like to tick at at least 60fps (~16ms frame time), which is common for FPS; other types of games are different of course. I suppose it could be tuned to further decrease latency at the cost of throughput...
The duration of a pause has more to do with the size of your heap than with how much garbage you generate. If you generate a lot of garbage, the pauses don't get longer, they get more frequent.
While I agree in the general case, I'm really excited to show off what Rust can do here. We've made some changes lately that make concurrent stuff safe that I'm not sure other languages can do. My favorite latest example:
extern crate threadpool;
use threadpool::ScopedPool;
fn main() {
let mut numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
{
let pool = ScopedPool::new(4);
for x in &mut numbers[..] {
pool.execute(move || {
*x += 1;
});
}
}
println!("{:?}", numbers);
}
This allocates a mutable array on the stack, and then creates a threadpool which adds one to each element of the array, four threads at a time. We need the inner {}s so that we know that the pool is done working before we try to print the result. Yes, mutable pointers into the parent stack frame. But, the compiler can verify that this is absolutely safe. Say, for example, that we left off the inner scope, so that the pool might not be destroyed and therefore join before we try to print out the array. That'd be racy in most languages. In Rust, it's a compile-time error:
error: cannot borrow `numbers` as immutable because it is also borrowed as
mutable
println!("{:?}", numbers);
^~~~~~~
note: previous borrow of `numbers` occurs here; the mutable borrow prevents
subsequent moves, borrows, or modification of `numbers` until the borrow
ends
for x in &mut numbers[..] {
^~~~~~~
note: previous borrow ends here
fn main() {
}
^
Rust knows that you're still holding a mutable reference to the array, and so taking a new immutable one could case a race.
As you can see from the `extern crate`, this pool isn't a compiler built-in: it's a library. There's actually a secondary implementation of a threadpool that makes some different choices internally. But this kind of safety can be gained in whatever concurrent code you're writing, and you can write new concurrent abstractions and ensure that they don't have data races.
> Watching you "manual memory all the way" dudes struggle with simple concurrency as much as you do, I'd hate to throw away a GC just for that extra teeny bit of performance.
reply
I think you may have missed the part where I mentioned RAII. It's a lovely scheme in C++ and a handful of other languages. You can get away from manually managing memory entirely in C++14.
89 comments
[ 3.8 ms ] story [ 160 ms ] threadIt 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.
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.
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. =)
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!
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.
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.
(A better place to look to understand GC might actually be LuaJIT or Erlang. I say "might" because while I've been told that both have simple to understand implementations, I have not bothered myself to actually look at them.)
For large binaries, a relatively primitive reference counting system is used.
If I were to study GC from scratch, I'd start with http://www.hboehm.info/gc/.
In the JVM, the CMS only occurs on the oldest generation which contains objects that were in use for a while, whereas objects that are created and discarded quickly are cleaned up in younger generations with a copying collector, which avoids memory compaction by switching back and forth between 2 equally sized memory blocks. This means much of the time the JVM can avoid doing a full CMS and keep the time spent in GC only a few ms per second.
I guess it depends on what your use case is. If you're writing low-latency server applications that don't have loads of long-lived internal state and you have memory to spare, the JVM's CMS GC is going to be way more efficient than Go's. But if you're constrained for memory then avoiding copying collectors and generational heaps is your best bet, but you'll pay for it in GC time. Of course the JVM has other GC algorithms like G1, but I don't have much experience with those.
Correct, that's slated for the 1.6 timeframe:
> While other goals may intervene, 1.6 will most likely be used to improve throughput by adding bump pointer allocation as well as a generational copy collector for nursery (new) spaces. The mature (old) space will be managed using our concurrent GC.
Source: https://docs.google.com/document/d/16Y4IsnNRCN43Mx0NZc5YXZLo...
As far as I understand copying/generational collector by themselves don't add a lot of memory overhead. They simply add more complexity. You tend to require a lot more memory to ensure most your allocation & allocation happens in nursery (which can be scary fast and low overhead) and to allow the old generation GC to pace itself.
I wonder how much of the 20% expected GC overhead comes from the fact that they can't do the nursery GC optimisation and whats the expected overhead when it goes generational in 1.6
One thing I absolutely hate with CMS is the fallback single thread collector for Old Gen that makes for a scary possibility. Don't think GO will have one of those which is nice to see (not for me though :().
For example the G1 garbage collector can deduplicate strings in the heap. This can be a big win for servers and IDEs.
In the latest update I read that G1 is also able to adapt itself to memory pressure in the entire operating system. If you start an app next to the JVM and the OS available memory drops, it'll start to use more CPU time for collection and shrink the heap so it can hand RAM back to the OS and reduce pressure again.
G1 can do lots of other nifty things, but it uses more RAM than ParCMS so it's not the default at the moment. You have to opt into it. I think they want to make it the default one day.
Whatever your thoughts are on Java the language - would it not make sense to focus efforts on the OpenJVM project and all the languages it can support?
Genuinely curious if this seemingly "reinvent the wheel" approach is going to provide benefits.
That assumes everyone wants a language on the JVM.
No VM is one of the reason people use Go, along with easy concurrency backed directly in the language and not as a third party framework.
IF you find the JVM so awesome ,keep using it. I personally think the memory cost isnt worth it ,and when I say cost, I mean the actual cost in $$$. Hardware might be cheap, the cloud isn't.
Just because the option isn't part of OpenJDK, doesn't mean other commercial JVMs don't offer it on their toolchain.
Funny, but over a decade ago, we Smalltalkers were once asking: "Does anyone else feel like this is reinventing Smalltalk GC and JIT VM technology - which has years of calendar experience and countless man hours of engineering research in the real world?"
I'm sure Lispers have similar things to say.
So, I'd rather hit my head against the wall on GC problems while smart people improve it than hit my head against the wall with a MASSIVE deploy/build headache that definitely won't go away for a bunch of technical, political and historical reasons.
Once properly set up, deploying Java is usually a one click affair, not sure what insanity you are talking about.
Also, Go is compiled natively which certainly complicates the deployment mode (and expect more complications down the line once Go supports dynamic loading).
Either way, Go's deployment model doesn't have much to do with the language and it will become more complex if the language becomes more popular.
Whichever you mean, you can create apps that have self contained JREs with the javapackager tool. But most server setups don't seem to need it. If you have a broken IT environment where your admins refuse to upgrade the JVM, that can be an issue, but then you might find yourself being told to stick with an obsolete version of Go in future too in such an environment.
I'm not trying to start a religious conversation; so with that caveat, I'll respond -- By insanity, I'm referring to the need to grok stuff like this page:
http://maven.apache.org/guides/introduction/introduction-to-...
Building a large java application is not something I'm an expert at, but I have spent many hours of my life fighting with maven and ant and dependencies, happily some time ago.
By comparison, there's "go build". Or if you need auto-cross-compiling, there's goxc. While an IT manager might limit the version of go on a server, it would have no impact on most go developers; I can build a self-contained binary for linux right from my Macbook Air in under 2 seconds with a single command. Or using goxc, I can build for all binary targets in very short order.
To me reducing this sort of cognitive load on build/deployment is a HUGE benefit go provides, especially to junior developers or teams with different backgrounds.
Building in Java is also a one line command. Deploying is also often a one line command (or a one click affair).
The fact that Go is natively compiled makes this kind of deployment a bit more problematic, and it's bound to get more complicated once Go supports dynamic loading.
I'm not trying to make a judgment call between Java and Go here, just pointing out that saying that one of these language is insanely more complicated to deploy than the other doesn't make much sense.
No, because GCs optimizations are very dependent on the semantics of the programming language.
There isn't something like a general purpose GC algorithm for every type of programming language out there.
In Java, everything except primitive types is a pointer. In Go, on the other hand, programming "by value" is encouraged (pointers are explicit, never implicit). In Go, it's possible to actually avoid creating garbage altogether - you have a decent amount of control of where memory gets allocated.
Thus porting Java's GC, which has been highly optimized to deal with hundreds of short-lived objects whose allocation you as a Java programmer have no control over, wouldn't make sense - it's optimized in all the wrong places, for Go, basically.
The Go team have already adapted GCC to their language, for example. They could have also adapted the JVM. For instance the Java guys are adding value types at the moment, but most of the reason it's hard/slow for them is backwards compatibility with existing code. Go doesn't interop with anything except C anyway, so they could just throw that requirement out and have a customised GoVM that supports value types and so on, whilst reusing all the other technology in there.
Putting Go on the JVM would be taking a language that only has a few "great" features (fast compile/startup time, decent memory efficiency, simple static binary output) and neutering it to the point of irrelevance.
I guess dropping a single frame on occasion may not be that bad, and the GC parameters could be retuned (and other GC languages have lower latency), and you could minimize the amount of garbage created, but still, that's not a good situation to be in.
A good strategy for handling this in a GC'd language is using the factory / pool patterns, so during level loading you instantiate 100 "empty" projectile entities that you can re-use. When a projectile is "fired" you request a Projectile from the ProjectilePool, add its initial position/speed/whatever, then add it to the world. It goes through its trajectory, maybe hits a wall, and then you release it back to the ProjectilePool where it is cleared and can be re-used later.
But what if you need 101 projectiles...?
Just guessing =P
Of course, AAA game engines today will employ custom low-level allocation strategies in order to squeeze out the last few percentage points where they deal with dynamic data - but if your aims are more modest, and you harken back to 80's era gaming, most of those games had a nearly or entirely static memory map. Besides being a poor fit for those tiny microprocessors, dynamic allocation enables out-of-memory and fragmentation errors to exist, leading us back to the "hard limits on instancing" strategy again.
GC still incurs overhead where it has to trace, even if you've pooled everything. Reference counting pulls ahead of tracing collectors in the situation of heavy object persistence, despite being more expensive as a general allocation method. As well, it has predictable latency, which is more important for meeting real-time requirements.
(N.B. as systems parallelize, they become more bound by latency considerations. Seven workers may finish early, but delivery will still get bottlenecked by the eighth slow one.)
For what value of "as possible?" It's kind of a miracle that twitch game mechanics FPS work at all with typical Internet latencies, which is one of the various reasons why I'm not doing that. "As possible" in my situation, doesn't include the resources to do that.
I wish Go could use RAII or another memory scheme so they could drop GC altogether.
There's always Rust. Also, Erlang can "cheat" at GC in some ways due to immutability. Server side Swift has potential as well.
Really depends on the use case. Obviously "real-time" in a money context is very different than gaming. For gaming GO will probably be fine but that's also depending on how the game can scale.
> There's always Rust.
I've heard good things about rust though C++ is also pretty fantastic but I guess it's not as popular anymore.
Additionally, Erlang can also make "soft real-time" guarantees because each actor has its own heap, and consequently each actor is GC'd separately.
This lets you take garbage off the heap, and avoid GC all together if you want to.
I believe Go does escape analysis so you can still shuffle around pointers to local structs within a stack frame without causing a heap allocation.
edit: That being said you can't really implement something like refcounting for structs you pass around by pointer outside the local stack frame without the compiler emitting an allocation on the heap. To totally avoid using the GC you'll need to do a lot of copying. And there aren't destructors.
Watching you "manual memory all the way" dudes struggle with simple concurrency as much as you do, I'd hate to throw away a GC just for that extra teeny bit of performance.
- A 10GB heap with one single heap-allocated []byte will have short <1ms pauses.
- A 512MB heap with 500k heap-allocated []byte will have long pauses.
As you can see from the `extern crate`, this pool isn't a compiler built-in: it's a library. There's actually a secondary implementation of a threadpool that makes some different choices internally. But this kind of safety can be gained in whatever concurrent code you're writing, and you can write new concurrent abstractions and ensure that they don't have data races.
I think you may have missed the part where I mentioned RAII. It's a lovely scheme in C++ and a handful of other languages. You can get away from manually managing memory entirely in C++14.