Modern garbage collection: Part 2
blog.plan99.net
blog.plan99.net
This is definitely very significant, you just took away 6% of the CPU time available to the game to calculate everything necessary for that frame. And that's if there's only one pause inside each frame. And if you are running close to 100% CPU time, and the pause happens right before the vsync, you might miss the vsync and you will drop a whole frame.
This is not only a problem with GC, even with more deterministic memory management, like plain malloc() and free() in C, you can have pauses if the operating system needs to go and find some free memory, update page tables, flush TLB caches and so on. So for games and anything real-time, you probably want to avoid memory allocations as much as possible, and certainly don't want your whole process being paused at random. So if you are stuck with GC, then one question would be: can GC be done for individual threads without blocking other threads?
I interpreted the author's point as "GC is now potentially viable for games", in the sense that older GCs might have pause times larger than 16ms, making them obviously inappropriate, whereas today 1ms pauses is something that can be budgeted for at least in some cases.
As you said, malloc/free also have costs, and also GC has other benefits, like bump allocation, moving things to compact memory and improve cache locality, etc. 1ms pauses means GC is worth considering even for a game, in other words.
The general approach used by games is probably superior, which are arenas or zones.
One approach games use is to allocate everything that's necessary for a given frame in a single large block, carve it off over time as needed, then drop the entire arena. All allocations then have memory locality, no fragmentation, basically zero cost to allocate (increment a pointer) and zero cost to deallocate.
This kind of thing actually plays really nicely with Rust's lifetimes since you can couple frame lifetime with objects in that frame and get static validation. Arenas are already available in nightly [1].
[1] https://doc.rust-lang.org/nightly/nightly-rustc/arena/index....
It seems like a strange example to give, when many modern games obsess over minimising delays in all sorts of ways (eg anything Mike Acton talks about: not just cache-friendly data-oriented structure-of-arrays or removing branches, but also eliminating function calls ("where there's one, there's many") and pointer indirection).
And the more competitive ones tend to run higher than 60fps too, making the issue even more prominent, meanwhile for those for which it doesn't really matter (e.g. a 2D adventure game)… neither does ultra-low GC latency either.
So I'd think a GC designed for a gaming system would take this into account; incremental concurrent GC that can be timed to happen at the start of each each frame interval and be paused if it gets close to the end.
https://help.adobe.com/en_US/FlashPlatform/reference/actions...
The whole premise of a GC to save you from thinking about memory allocation is moot if it comes to real-time sensitive tasks, there it makes things harder instead of easier. A reference counting system is much better IMO, even though you may be able to get higher absolute throughput with GC, at least the small overhead you incur is stable and predictable.
What GC delivers is first of all the guarantee of correctness, a pointer is either nil or points to a validly allocated memory. Also, it removes most needs of bookkeeping. That simplifies programs and especially allows to write clean APIs, where functions are fine to allocate reasonable amounts of memory.
But wherever there are large parts of memory required, especially with a clear lifetime, I think a lot about memory allocation and even in a GC language I try to reuse memory wherever that makes sense.
So for a game engine, there should not be much need for allocation during the run time of a "level" and thus GC pauses should only happen between levels.
We work on a dual C++/C# codebase. Something like 3/4 C++ and 1/4 C#. Basically all of the memory lifetime errors happen in C# land. I do not recall a memory lifetime error _ever_ hitting master in C++, but we have one bug against _prod_ right now and two bugs against master right now, as we speak in C#.
Dealing with lifetimes in C++ is easy, dealing with it in C# is a nightmare. Maybe it's easier in Java or Go, I don't know, I've only dealt with Java in school and never coded in anger in Go.
IDispose. We have an ecosystem where a nonnegligible number of in flight objects need to manually be disposed of. In C++, RAII takes care of this for us.
Un listening to events. Needs to happen manually in the standard .NET listeners. C++ solves this with weak_ptr. C# could solve this with a better standard library, but we have .NET.
Honorable mention (not lifetime, but the deadlock quagmire that is C# and its half async half synchronous standard library) is WritableBitmap, which is impossible to use correctly, and has not been deprecated or had a safe replacement offered.
C++ surprises me in ways I expect to be surprised. C# surprises me in ways that leaves me confused and perplexed.
I very much doubt that this is a big _productivity_ win. Languages in which it is idiomatic to "think about ownership over heap allocations" (C++, Rust) aren't obviously less productive than comparable languages where such thinking is not so idiomatic (C, Java, .NET, ObjC, Swift etc.).
It's somewhat common to use refcounting (shared_ptr<>, etc.) in the more exploratory style of programming where such "thinking" is entirely incidental, but refactoring the code to introduce proper tracking of ownership is quite straightforward, and not a serious drain on productivity.
I'm pretty sure that's true for the great majority of software developers, but of course they don't even use a non-GC language!
Part of the reason they don't is that productivity. Not that they chose it personally for that reason, but e.g. historically enterprise code moved to Java and C# for related reasons.
(I also agree there are people that are equally productive in non-GC languages, or even more - different people have different programming styles.)
The enterprise world moved to Java and C# because:
- It was a corporate language with corporate support and that matter a lot in many environment.
- It had at the time one of the best ecosystem of tools available.
- It was the mainstream fashion of a time and nobody get fired to buy Sun/IBM/Microsoft right ?
Most companies (and managers) could not less give a dare about your program crashing with a segfault (unsafe) or a null pointer exception (safe). It's the same result for them.
Not in a security-related situation, it's not! And to a lesser extent, lack of memory safety also poses a danger of silent memory corruption. (Yes, usually the program will crash outright, but not always.) And it can be a lot harder to debug a crash when it doesn't happen until thousands of cycles after the erroneous access.
Sun and Microsoft wouldn't have built and pushed Java and C# in the first place if there hadn't been a real need for safer languages.
Excepted they were safer languages before Java and C#: Ada, Lisp, All the ML family.... And all of them never lift off.
Java and C# have been successful because they were accessible and easy to learn ( partially due to their memory model), not because they were safe.
As a parenthesis, a beautiful side effect of that has also been an entire generation of programmer that has no clue of the memory model their language use underneath, because "it's managed", because it's GC.....without even realising that their 50 Millions nested/mutual object graph will make the GC on its knees on production. With the results we all know today.
I think that Java came 'at the right time': when computers became fast enough that the GC overhead didn't matter (except where low latency matter).
Circular references can be a problem, this is just something you have to live with and design for, just as in languages with manual memory management. In the typical cases where this can be a problem (graphs of objects) its very straightforward how to fix them using weak references.
I don't understand point 3 and 4 and why they would be a property of reference counting for memory management. They both seem completely orthogonal problems that have nothing to do with the mechanisms that decide when to free memory.
Anyway, my original point was not that reference counting is perfect, or even more efficient compared to garbage collection. Just that it is predictable and deterministic, which is very often much more important, especially for code with real-time constraints.
New Swift Ownership API can help, but compiler is not that good to figure out exclusive ownership all by themselves without any annotation. It is common to have more than 10% of you time in RC environment spent on refcount calculations and locks acquisition (some stats: http://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf).
If the language supports ownership tracking and non-synchronized Rc<> as in Rust, refcount updates ought to be rare and/or quick. I agree that this is very much an issue in languages with obligate "managed" memory such as Swift, and that tracing GC may sometimes be preferable to that.
> too much time spent freeing memory
If you're using Rc, you probably care about memory reclaim being deterministic, which tracing GC doesn't give you. You can also use arenas to free a bunch of objects all at once; this also addresses memory fragmentation and slow allocation to some extent.
You can solve this with weak references.
The problem is having the VM allow and support that usage, and the JVM definitely is not best-of-class there. See ixy[0] from a few months back where the researchers / developers didn't manage to get under
> ~20 bytes of allocation per forwarded packet in Java.
In the Objective-C era before automatic reference counting, you had these things called 'autorelease pools' which allow pretty straightforward control over deallocation. I think the same thing is still possible in ARC Obj-C and Swift.
What we did to accomplish this was first aggressively optimize the data ingestion, then spend all that surplus on maintaining a ring buffer of pixels. This meant we were always a little behind live (.5s or 1s, I can't recall), but it made everything smooth as silk. To maintain homeostasis, I'd trigger GC every time we made it through a paint cycle with a full buffer.
There are ways to do it, but it could change the structure of your app. I say, "in our case the main paint loop was stupid-simple so it wasn't that big of a deal to tack it on," but the idea was always sort of in the back of my mind so it definitely informed the design.
What I didn't have to deal with is random inputs from the user changing my display strategy.
I mean, i play games like Skyrim that now and then give you a pause as you walk the world while it unloads cells (i refer to normal walking around, not entering/exiting somewhere - which, btw, would be a good place to force a GC too in a similar game that would be written in a GC'd language) which can even be 1 second long. 1ms is noise long lost in there.
For a competitive game you are looking at a refresh of 240 Hz (4 ms) but people generally target frame rates of at least 300-400 Hz (2.5 ms per frame!). There is simply no room to randomly throw in 1 ms pauses here and there without introducing micro-stuttering.
Even for a casual game 1 ms of extra frame time variance is bad. If your Skyrim has one second freezes while roaming the world, your install is busted, because the game in proper working order doesn't do that.
Yes, it depends on the game, what i wrote doesn't apply to every single game ever made out there, but it does apply to a ton of games.
> Even for a casual game 1 ms of extra frame time variance is bad.
If it happens every several minutes you will 100% not notice it at all. In pretty much every high end 3D game (especially an open world one) you'll get way more variance by turning the camera around and/or just walking than that.
> If your Skyrim has one second freezes while roaming the world, your install is busted, because the game in proper working order doesn't do that.
I'm 100% sure my Skyrim install is perfectly fine (it is a fresh one) and it does happen, just not frequently. If you haven't noticed it... well, as i already wrote, it isn't really noticeable. And - especially on Skyrim - you'll also get way more variance than 1ms just walking around.
The entire game loop would need to be constant time w.r.t. player activity to avoid this issue!
> I'm 100% sure my Skyrim install is perfectly fine (it is a fresh one) and it does happen, just not frequently. If you haven't noticed it... well, as i already wrote, it isn't really noticeable.
My ability to detect lags of one second (like you wrote) is approximately 100 % assuming I am actually looking at the screen. I've seen pauses like this when I had a hard drive and with the 32-bit version of the game when it experienced memory pressure, and also due to badly written mods.
> And - especially on Skyrim - you'll also get way more variance than 1ms just walking around.
That's sadly true, though it tends to run smoothly when it has finished loading everything for an area.
The issue with GCs isn't really that 1ms, the issue is that some GCs (which sadly includes most known ones - like those in Java and C# - but not all GCs) do not provide any form of control beyond mere suggestions. For example last time i checked running System.gc() in Java doesn't really do a full GC run, so you cannot guarantee that by the time gc() returns you'll have all unused memory gone and placing that call between area/level loads in games (where the user expects some sort of delay anyway) doesn't help you much. Similarly you can't just "turn off" the GC until a later point (or until some specified failsafe threshold is reached) so you can't turn off the GC during normal levels and turn it on between level loads and/or when the player opens any inventory/menu/whatever screen (where again a tiny delay will be mostly unnoticed and/or ignored and often can be masked by the UI design) to clean up any garbage.
IMO a GC that gives you such control and takes 100ms is way more useful for games than a GC that give you no control and takes 1ms.
First of all: bullshit. Second of all: bullshit.
99th percentile of 1ms means that 1% of the time you're worse than that. The author says sometimes it's as bad as 8ms. A dropped frame every 15 seconds or so will make your game unplayable. 99th percentile measurements are useless. Tell me how often your users are subjected to any given latency.
One millisecond is enormous. My kingdom for a millisecond. If one in ten frames losses 1ms to a GC and one in a thousand frames looses 4ms, that means my budget is 12ms down from 16ms. Thanks, you've sent my expected environment back to 2010.
People think they can just say "99th percentile is bad but not terrible" and assume that's the end of the argument but that's not how the world works. 99th percentile frame time happens once every 1.7 seconds. If your web page loads 200 assets (which is basically all of them these days) nearly all page loads will hit worse than 99th percentile for one of those asset loads.
99th percentile analysis is useless.
Garbage collection promotion is always, fundamentally, an exercise in doublethink. How can an intolerable process be made to seem tolerable, so that my dodgy language which depends on it can be used in place of a mature language which has a robust mechanism for managing all resources, not just memory?
It can't. GC is fine for things that don't matter, but things have a way of coming, in time, to matter. Then you have a Problem.
> As you can see, there are a lot of different factors that go into designing a garbage collector and some of them impact the design of the wider ecosystem around your platform. I’m not even sure I got them all.
The problem is that a simple GC like this will have low throughput, so it's not worth it. These are some of the most common misconceptions about GCs: that it's hard to write a low-latency GC and that pauses are all that matter. In reality, GC engineering is all about the tradeoff between throughput and latency.
[1]: https://www.memorymanagement.org/glossary/t.html#treadmill
I'm happy that the Go team doesn't want to expose tuning knobs. I've seen a lot of people fiddle with JVM settings without doing the controlled experiments needed to see if it actually helps on a particular machine and I've done that myself. It ends up as cargo-cult programming, like people sharing magic JVM settings on the wiki to allegedly make IntelliJ faster. (It worked for one person!)
That's a problem with what the people are doing then, not the JVM. Furthermore, the new low latency JVM GCs only have 2-3 knobs to tune.
golang likes to pretend that complexity doesn't exist, and goes for the most simplistic approach, at the cost of things like throughput, code size, speed, code maintainability, etc. The JVM is suited for a much wider range of tasks.
Go authors tend to be quite humble about Go being targeted mostly to a specific class of software, read servers. And Go is pretty darn successful at it.
The lack of GC knobs is an informed decision within that context.
> How We Built Uber Engineering’s Highest Query per Second Service Using Go
https://eng.uber.com/go-geofence/
And that was in 2016. Go's GC performance characteristics improved quite a bit since then.
No, it's not true that "latency is what the user sees". Only for interactive applications is that true. In fact, given a choice between the two, I would generally choose throughput over latency.
The Go compiler is an example of an application in which throughput matters 100% and latency matters 0%. Even with some semi-interactive tools like ripgrep, throughput matters much more than latency, because throughput determines how quickly the search finishes.
Even for servers, throughput often matters more in ways beyond how many machines you need. Would you rather have a Web page that takes 10 ms to load with 1 in 10,000 loads taking 2 seconds, or a page that takes 200 ms across-the-board? I'd take the former. Remember that another name for throughput in this context is allocation performance, which makes it clear how important it is.
For example:
Reclaiming raw materials from landfills
Machines/robots that can sort recyclable materials from a heap of mixed garbage.
Better insulated landfillsBut I think it would have been an even better article without the negativity about Go and how the author thinks "the Java guys are winning" in his words. That felt a little petty.
Example 1. The article talks about compaction and generational collection as being Good Things(TM), but it doesn't talk about the costs associated with them. Looking at the linked Go article, these approaches suffer from high write barrier overhead. For Go, this isn't worthwhile because escape analysis allocates many young objects on the stack (which btw is effectively bump-pointer allocation) so trying to further reduce GC overhead by increasing the overhead of every pointer write is just not worth it. It may, however, be the right trade-off for Java.
Example 2. Java's many tuning parameters means that programmers who care about performance have to choose the right GC and tune it. If better GCs come out or tweaks to the algorithms are made, these configurations have to be updated. In contrast, Go programs gets these benefits for free. The best approach seems to be to offer a small number of high-level knobs, but it's hard to determine what those are, leading to the two (suboptimal) extremes you see with Go and Java.
> Example 1. The article talks about compaction and generational collection as being Good Things(TM), but it doesn't talk about the costs associated with them. Looking at the linked Go article, these approaches suffer from high write barrier overhead.
You need a write barrier no matter what for any sort of incremental or concurrent GC, to maintain the tricolor invariant. Otherwise there is no way for the runtime system to detect a store from a black object to a white object. Typical GCs will fold the write barrier needed for generational GC into the write barrier needed for incremental/concurrent GC, so there is no need for extra overhead if properly implemented.
> For Go, this isn't worthwhile because escape analysis allocates many young objects on the stack (which btw is effectively bump-pointer allocation)
Java HotSpot has done the same thing for a long time! It's just that in HotSpot escape analysis doesn't really help allocation performance, because the generational GC already offers bump allocation in the nursery. Escape analysis in the JVM does open up more optimizations, though, because it serves as the scalar-replacement-of-aggregates transformation.
> so trying to further reduce GC overhead by increasing the overhead of every pointer write is just not worth it.
This is only because of their specific implementation. There is no need for increased overhead.
> If better GCs come out or tweaks to the algorithms are made, these configurations have to be updated. In contrast, Go programs gets these benefits for free.
There is no reason why Java can't do the same by updating defaults. In fact, they often do.
> There is no reason why Java can't do the same by updating defaults. In fact, they often do.
Correct. The JVM guys always update the default GC to be the nearest to 'one size fits all'. Obviously if you've made a custom GC configuration then you want a level of tuning that Go does not provide.
But I agree that friendly competition is a good thing! I feel this article was a little past that, though.
Go introduced a new GC a while back with dramatically lower latency numbers, not only compared to the previous Go GC but any other commonly available GC in any language (excluding exotic commercial ones like Azul). Neither the old or new Go GCs are particularly sophisticated compared to the highly developed ones in the Java ecosystem.
The author of these articles seems to take objection that the latency numbers were achieved not by magic or pure GC implementation genius but by simply optimizing for latency, which involves some trade offs. I don't think this negates the usefulness of having a low latency GC available though, although I can understand how it might be frustrating to see a project getting a lot of attention for what feels like a lesser intellectual achievement.
Obviously not all projects even require low worst-case latency, monolithic apps will be less sensitive, applications waiting on 10 other services will be more etc. Some apps the CPU isn't a bottleneck either. It's just another trade off where Go is prioritizing some things. There's even other factors not mentioned in the article like a compacting collector might make calling C functions more complex since it needs object pinning.
[1] There's also another GC mentioned that's less talked about in the article, Shenandoah, that requires patching the JVM and introduces memory overhead to every object for a forwarding pointer. It was hard to find numbers, but it looks like the latency target for this GC is also in the 10ms range (http://clojure-goes-fast.com/blog/shenandoah-in-production/).
Believe it or not, the current default GC is G1GC, which has a target (and quite common) pause of 300ms by default.
> Go introduced a new GC a while back with dramatically lower latency numbers
Or maybe just like Azul's numbers from 2005?
http://big-elephants.com/2018-09/unexpected-gc-pauses/
https://www.usenix.net/legacy/events/vee05/full_papers/p46-c...
> Shenandoah, that requires patching the JVM
The page you linked to says "How do you get Shenandoah? This garbage collector has officially become part of JDK only since version 12 and is available in AdoptOpenJDK 12 builds."
> and introduces memory overhead to every object for a forwarding pointer.
The first version did, Shenandoah 2.0 does not
In the very sentence you quoted I said “excluding exotic commercial ones like Azul“. I’m not sure what point you are trying to make here.
> Shenandoah 2.0 does not
I see. I only googled that link to find the latency target (since it wasn’t mentioned in the original article), I have to confess I didn’t read the rest of it and almost all of what I wrote is based on the original article. Good to know that some of that information is now out of date.