Modern garbage collection: Part 2

https://blog.plan99.net/modern-garbage-collection-part-2-1c88847abcfd

by mariuz • 7 years ago

150 91 7 years ago

blog.plan99.net

gsliepen• 7 years ago

For a video game running at 60 frames per second each frame has 16 milliseconds in which to complete, so a pause of less than a millisecond is not going to be significant relative to other overheads.

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?

dkersten• 7 years ago

Yeah, there's a reason games often preallocate large chunks of memory and then not allocate/deallocate during a level, use object pooling and stack allocators.

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).

masklinn2• 7 years ago

It seems like a strange example to give, when many modern games obsess over minimising delays in all sorts of ways

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.

w0utert3• 7 years ago

True. This is why any serious game running on a VM with GC would avoid any kind of per-frame memory allocation and use arena allocators instead.

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.

masklinn2• 7 years ago

True. This is why any serious game running on a VM with GC would avoid any kind of per-frame memory allocation and use arena allocators instead.

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.

[0] https://github.com/ixy-languages/ixy-languages

_ph_• 7 years ago

I don't think the idea of GC is to save you from thinking about memory allocation. Actually, not thinking about memory allocation is a great way to create very slow programs, independant of whether you us an GC or manually free memory, though modern GCs keep the performance penalty reasonably low. Still, you want to think about memory allocation, so that you don't allocate inefficiently.

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.

enhray• 7 years ago

I’ve heard horror stories about reference counting performance cliffs caused by avalanche deallocations, which are hard to predict.

barrkel2• 7 years ago

Per-frame allocation would be very cheap with a tuned generational GC run every frame, as nothing would be live at the end of the frame and thus tracing would take almost no time. Of course the same would be true of an arena allocator, at the cost of needing to classify every allocation accurately.

LessDmesg3• 7 years ago

Reference counting is not better, it's a poor man's GC. Reference counting means: 1) instruction pollution from all the refcount updates and their synchronization 2) circular references, ie memory leaks 3) too much time spent freeing memory (whereas a generational GC spends time on live objects only) 4) memory fragmentation and hence slow allocation (whereas in a normal GC allocation is just O(1)

brighteyes6• 7 years ago

You're right, yes - a 1ms pause has a cost, even in a 16ms budget.

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.

_lbaq• 7 years ago

"Games" is a term for are a large collection of very different types of software, do we mean AAA FPS games? Then I would probably not use a GC, if we mean most other games? Then it's just fine. Many GC events are way shorter than 1ms also...

arcticbull2• 7 years ago

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....

cmrdporcupine• 7 years ago

The other question is: can I at least time this GC so it doesn't overlap the refresh interval and skip a frame? Because 1ms may not be significant if it lands in the middle of the 16ms period, but if it lands at the end you've just produced jitter.

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.

corysama• 7 years ago

You can manually trigger GC in Lua. I’ve used this to trigger light GC work every frame in some games to buy more consistent GC times (no spikes) at the cost of higher average times.

markdog122• 7 years ago

I remember the oddly named System.pauseForGCIfCollectionImminent() AS3 (Flash) function:

https://help.adobe.com/en_US/FlashPlatform/reference/actions...

skybrian3• 7 years ago

Would it make a difference for Minecraft? I haven't played in a while but I remember fiddling with JVM settings to try to get smoother performance.

pjmlp2• 7 years ago

I lost the link to the forum post, where it was described how bad Minecraft data structures were designed.

badsectoracula3• 7 years ago

Considering how variable game frames are, even if the GC eats that 1ms it will be unnoticeable, assuming it doesn't happen too often.

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.

blattimwind4• 7 years ago

Considering how variable game frames are, even if the GC eats that 1ms it will be unnoticeable, assuming it doesn't happen too often.

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.

pron• 7 years ago

Games have a very regular object lifetime, allowing them to manage much of their allocations in arenas, which can certainly beat even modern GCs in performance (although maybe not for good). But concurrent server business applications don't have such regular object lifetimes, and it is getting quite hard to beat the performance of modern GCs with manual memory management in such applications. These days, footprint is the major and pretty much only significant cost to GCs in a great many applications.

hinkley• 7 years ago

My second job was displaying telemetry waveforms in real time, in Java... 1.3 if memory serves. MVP goal was 4 waveforms, I managed to get 16.

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.

brighteyes6• 7 years ago

The technical detail in this article is excellent! A great read.

But 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.

randomidiot6665• 7 years ago

Why? Did he hurt Go's feelings? It's a programming language, not a child. I prefer his honest assessment of their relative strengths and weaknesses.

brighteyes6• 7 years ago

I just think our industry would be a better place if we didn't try to tear down other technologies, say stuff like "X sucks", etc.

But I agree that friendly competition is a good thing! I feel this article was a little past that, though.

uluyol• 7 years ago

Except that it isn't necessary nor is it completely honest. Go and Java take different approaches here, but the article focuses on the merits of the Java approach and the downsides of the approach taken by Go.

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.

skybrian3• 7 years ago

It's odd how he goes out of his way to make the Go team's decisions seem strange just because they're different. What's going on there?

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!)

apta3• 7 years ago

I've seen a lot of people fiddle with JVM settings without doing the controlled experiments

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.

hu32• 7 years ago

That's not the impression I get from Go literature at all.

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.

HALtheWise• 7 years ago

They have had a personal bone to pick with the Go team for a while as a result of some of their marketing language around low-latency GC designs. It sounds to me like their personal work focuses on high-throughput designs, and an increasing industry emphasis on low latency threatens that.

pcwalton5• 7 years ago

It's not that the Go team's decisions are different; it's that they are worse for most applications. If you read the first part of the series, the author goes into detail on this. The problem is essentially that the Go GC focuses entirely on latency at the expense of throughput, which is not the best choice in most cases.

skybrian3• 7 years ago

Well, yes, he says that, but I'm not sure it's an objectively worse tradeoff? It seems like it depends on what you think "most apps" are like. It's not obvious to me that throughput is usually more important than latency, since latency is what the user sees and throughput has more to do with how many machines you need.

gok• 7 years ago

It's telling that of the 15 "things that matter in GC", power consumption isn't mentioned, even in passing.

markdog122• 7 years ago

They do mention they may have missed factors in the original article it links to:

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.

tom_mellior2• 7 years ago

What should be said about it that's not already covered by CPU and memory overhead?

cesarb• 7 years ago

Power consumption has some subtle details which make it different from both CPU and memory overhead. For instance, to reduce power consumption it's important to reduce wakeups.

pastrami_panda2• 7 years ago

Incremental GC is very promising for games in favour of traditional stop-the-world GC. It's essentially time sliced GC that runs over multiple frames. Unity supports it and if you tweak if correctly for your needs the GC can run while the CPU is waiting for the GPU.

chrisseaton• 7 years ago

I don't think there are any GCs that do not stop-the-world at some point, except those with special hardware support, are there? Even C4 requires in theory stopping individual threads, and in practice even has a global stop-the-world phase.

pastrami_panda2• 7 years ago

Yes you're technically correct but the time slicing makes it practically different. More here: https://blogs.unity3d.com/2018/11/26/feature-preview-increme...

pcwalton5• 7 years ago

It's easy to write a GC that doesn't stop the world at all. A Baker treadmill [1], for example, is a very simple type of incremental collector that can be implemented quickly. (It's a fun exercise, by the way!) If you implement it "by the book", it will have no stop-the-world pauses whatsoever (assuming the mutator doesn't allocate faster than collection can happen).

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

pcwalton5• 7 years ago

All the GCs we're talking about here are incremental and have been for decades.

blattimwind4• 7 years ago

In AAA titles especially gains in hardware are generally not squandered to make the software/engines simpler, but rather invested towards better fidelity or higher frame rates / better frame pacing (which is very, very noticeable). Games are one of few areas where the chronic wasting that is pervasive in almost all other software development is not accepted, by and large.

ryanseys• 7 years ago

I was hoping this was about the infrastructure and systems around collecting human garbage in the modern world.

symplee• 7 years ago

Anyone have any details on recent developments in the field?

For example:

  Reclaiming raw materials from landfills
  Machines/robots that can sort recyclable materials from a heap of mixed garbage.
  Better insulated landfills

mzi• 7 years ago

In the area in Stockholm, Sweden where I live we throw "all" garbage (we of course separate glassware, metal, paper, electronics first) in the same bin, but food waste in green bags. I don't know if it's robots that does the final sorting but I would believe so. Less than 1% of household trash ends up in landfills here.

nwallin3• 7 years ago

For a video game running at 60 frames per second each frame has 16 milliseconds in which to complete, so a pause of less than a millisecond is not going to be significant relative to other overheads.

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.

ncmncm3• 7 years ago

As we say in fintech, a millisecond is an eternity. (Lately, I have been hearing that a microsecond is an eternity.)

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.

Modern garbage collection: Part 2

Related Stories