22 ms·

Modern garbage collection

434 points by junke 10y ago

Jabbles 10y ago
The title of Go's GC announcement is "Go GC: Prioritizing low latency and simplicity", and I think that a variation of that would be a better title for this. Some users may prefer a different tradeoff, and I think it's important to know that there is a tradeoff. But as this article says "I have no doubt that many Go users are very happy with the new runtime.", and that seems like a worthwhile metric. https://blog.golang.org/go15gc https://blog.golang.org/go15gc
- fropelfizz 10y ago
  > But as this article says "I have no doubt that many Go users are very happy with the new runtime.", and that seems like a worthwhile metric. A metric for what? For it making many Go users very happy, or for making rather big claims like "future of GC"?
  - Jabbles 10y ago
    Making your users happy seems like a reasonable goal. Neither the article nor the Go announcement suggest this is the "future of GC".
    - boryas 10y ago
      First line of the Go announcement: "Go is building a garbage collector (GC) not only for 2015 but for 2025 and beyond" to me, that suggests they think they have the future of GC
      - Merovius 10y ago
        There is a difference between "a future-proof GC" and "the future of GC".
      - alanbernstein 10y ago
        I thought it was implied that they were talking about a GC for Go specifically.
- draw_down 10y ago
  That there are tradeoffs is the whole point, the messaging makes it sound like there aren't.
  - weberc2 10y ago
    The title says "prioritizing"; if that's not synonymous with "making tradeoffs", I don't know what is.
boardwaalk 10y ago
Interesting article. I haven't internalized all the parameters of the Go GC, but I wonder if there's a way to tune it on the fly. For example, if I want to run at 60 FPS (16ms/frame), and I've measured that actually doing all the CPU side work took 10ms, can I let the GC have ~5ms of GC time (rather than the <1ms advertised) at the end of my frame to increase throughput (read: less cycles burned overtime & better power efficiency)? If not in Go, can I do this elsewhere like on the JVM? Hopefully this isn't too off topic (since the article is about trade-offs of throughput vs latency).
- lossolo 10y ago
  I don't think you can do it with Go. But you can do it with Nim for example, there if you set 3 ms max GC time you have guarantee that you will only get 3ms of GC time. You can set max time for Java GC also, but from what I seen it's not so strict on G1 collector.
  - yoklov 10y ago
    Is there a way to ensure that the amount of time you set aside for GC is, err, enough? I imagine the outcome of it being insufficient would be quite bad... eventually.
- sophacles 10y ago
  I don't recall a lot about it, but what you described is "real-time garbage collection". If you google that term, you should find some work/writeups related to it :)
- mike_hearn 10y ago
  That's a realtime GC and yes, you can buy a JVM from IBM that has one, they call it the Metronome collector: http://researcher.watson.ibm.com/researcher/view_group_subpage.php?id=175 http://researcher.watson.ibm.com/researcher/view_group_subpa... Metronome has pause time in the hundreds of microseconds range. The tradeoff it makes is that, amongst other things, it requires read barriers i.e. every time you read a pointer from the heap you have to execute some extra code to interact with the GC subsystem. If you think about how often you read pointers from the heap in a typical program, well, that turns into a lot of barriers and a corresponding execution performance hit.
qznc 10y ago
> It has been known since 1984 that most allocations “die young” i.e. become garbage very soon after being allocated. This observation is called the generational hypothesis and is one of the strongest empirical observations in the entire PL engineering space. It has been consistently true across very different kinds of programming languages and across decades of change in the software industry: it is true for functional languages, imperative languages, languages that don’t have value types and languages that do. Is it really? The linked paper is about Smalltalk. A lot of the research is about Java. Functional probably talks about Haskell and ML. All those languages rely on GC completely. Is this hypothesis still true, when a language allows the programmer to mix different memory management techniques? For example, if you have smart pointer and stack allocation, do objects still "die young"? It might be that these young objects never reach the GC, because they are now allocated elsewhere, which means we have mostly long living objects under GC management. I guess a selective use of the Boehm GC would be the only reasonable way to falsify the hypothesis. Did anybody try that?
- _ph_ 10y ago
  If you look at a language like Java, where most operations produce some amount of garbage, the observation holds true. If you have a function performing some work, then all memory allocated which is not referenced by the return result, is garbage. And the introduction of generational GC with Hotspot back then, did a lot to improve the Java performance. This is no golden bullet though, as when the young generation overruns during a function call, not all memory allocations local to that function call can be collected, and even worse, they might be promoted to older generations, where they are rather costy to get rid of. Another view on this is, that ideally, you don't perform short lived heap allocations in the first place. Go for example tends to require less heap allocations than Java, and the compiler tries to put them on the stack, if they don't escape the function in which they are allocated. So Go manages to avoid those allocations, which generational GCs are especially good at cleaning up. The idea of generational GC is still considered by the Go team - they plan to have a special heap for each goroutine. This heap would be collected when the groutine exits. This approach would combine the sound idea of generational GC with a pretty good heuristic for the life time of the young generation.
twic 10y ago
An interesting shift in the wind for modern garbage collection comes from microservices. The work on JVM garbage collectors over the last ten years has increasingly been about supporting bigger and bigger heaps efficiently, as physical machines have got bigger, and programs' (or at least application servers') heaps have grown to fill them. Even Shenandoah, a current prototype collector, is designed around large heaps. But with microservices, we use our cavernous machines to house many small heaps instead. That leaves us with rather different garbage collection challenges. So, it's possible that the Go developers will get to ignore decades of progress, as they love to do, and still be competitive, because that progress was towards a different future to the one we arrived at.
- agumonkey 10y ago
  I'd love to know about other GC schemes. Between no GC and whole VM GC. By type GC, localized sub tree GC. edit: thank you all for your answers, much appreciatedly
  - osi 10y ago
    Look at what Erlang's BEAM VM does. It has per-"process" heaps iirc.
  - micmus 10y ago
    Erlang has a per-process GC - each Erlang process has it's own heap and it's own garbage collector. There's no VM-wide GC. This usually means the GC pauses apply only to a small part of your system, while the other parts are running completely normally. There's a good article that describes it in depth: https://www.erlang-solutions.com/blog/erlang-19-0-garbage-collector.html https://www.erlang-solutions.com/blog/erlang-19-0-garbage-co...
    - noss 10y ago
      Also if you have a lot of data you use an ets table which is more or less an in-process but off-gc-heap key-value database.
    - 10y ago
draw_down 10y ago
Excellent post, thank you.
LeanderK 10y ago
But why does Go prioritise low latency? I would think that low latency is not super important for web-servers since there are various other factors adding up to the total latency (what i mean here: time spent between call of the http request to finished receiving all bytes).
- Jabbles 10y ago
  Consider jitter, rather than latency. If you're building a video calling service. You don't want random 10ms gaps between your frames. Also consider fan-out. GC pauses add to the long-tail of latency. If your service depends on many backend services, your overall latency may well depend on the maximum of all your backends.
  - DannyB2 10y ago
    Processing video in a GC system is best handled like some other things that are continuous ongoing processing without doing a GC. 1. Allocate all your structures up front. 2. Your main video processing loop (or compression, encryption, signal processing, etc) does not do any memory allocation. This is also like writing games in Java.
- hashmal 10y ago
  the world of computing isn't just web servers. besides, the vast majority of language implementations already favor throughput over latency when it comes to GC. when latency is a requirement for your project you have no choice but fall back on languages like C. it would be nice to have a viable alternative with managed memory.
  - LeanderK 10y ago
    yeah, but when i hear go i think of web servers ;)
  - pjmlp 10y ago
    There is still hope for a Modula-3 replacement with the ongoing work on Swift, .NET Native, D, Nim. Even if it still isn't quite here today.
bitwize 10y ago
Why use garbage collection at all when value semantics and smart pointers cover virtually all the use cases for GC, much more efficiently?
- raphaelj 10y ago
  A generational GC is way more efficient than `std::shared_ptr`. `std::shared_ptr` is implementing a reference counting garbage collection, which is like the most inefficient way of implementing a GC. FYI: - Allocating memory in a generational GC is as fast as allocating something on the stack. It's basically changing the value in a register. It's order of magnitude faster than calling `malloc()`. - A generational garbage collection is slower than freeing a stack frame, but has a lower per item overhead than calling `free()`. tl;dr: for most programs, generational GCs are the fastest at allocating dynamic memory.
  - avar 10y ago
    Because calling malloc() & free() is expensive? That's just an implementation detail of your reference-counting GC or malloc(). You can also just pre-allocate memory in batches which makes allocation just changing a pointer to some pre-allocated memory. Many reference based GC's do that, e.g. perl. Or have I entirely misunderstood your comment?
    - Kutta 10y ago
      malloc and free are indeed far more expensive than allocation in a runtime system with copying GC.
    - rwmj 10y ago
      One problem amongst several with allocating memory in batches (or using a pool allocation scheme) is that you end up making poor use of the cache. After a while you have a lot of free memory mixed up with the used memory in your pool (see the article - the generational hypothesis), but because it's spread out a lot of that unused memory gets loaded into cache lines when accessing the memory which is still being used. Having said all that, pool allocators can work really well for certain workloads, especially client-server stuff. Apache uses a pool allocator for serving requests. Pool allocators also fit well with languages like C/C++, but that's just because those languages are very poorly suited to GC, there are much better designed languages which integrate better with modern GC.
lispm 10y ago
> It has been known since 1984 that most allocations “die young” i.e. become garbage very soon after being allocated. 1983: A Real-Time Garbage Collector Based on the Lifetimes of Objects, Lieberman/Hewitt http://web.media.mit.edu/~lieber/Lieberary/GC/Realtime/Realtime.html http://web.media.mit.edu/~lieber/Lieberary/GC/Realtime/Realt... Since objects with short lifetimes account for a large portion of storage use, it is worth optimizing a garbage collector to reclaim storage for these objects more quickly.
- voidlogic 10y ago
  I'd be interesting to know to what degree Go's aggressive stack-based allocation/escaping makes this hypothesis less strong than other languages. For example, Java a few generations ago was very poor at escaping heap allocation to the stack and so much the opposite skewing towards heap allocation over stack allocation, so I'm sure the JVMs of this era were an extremely good fit for the generational hypothesis.
lossolo 10y ago
I can't wait to see how ROC (Request Oriented Collector) [1] will benefit Go GC. Go is mostly used in web services which means you could collect garbage from whole request when it's over. ROC will try to do that. You can read more about it in the link that I've provided. 1. https://docs.google.com/document/d/1gCsFxXamW8RRvOe5hECz98Ftk-tcRRJcDFANj2VwCB0/edit https://docs.google.com/document/d/1gCsFxXamW8RRvOe5hECz98Ft...
- geekingfrog 10y ago
  It's addressed in the article. Basically, you can mimick that with a generational GC as long as the youg generation space is large enough to hold all objects from a request.
  - mike_hearn 10y ago
    Note that advanced collectors like G1 auto-adjust the young gen size as the program runs. This means pause times can take a little while to settle, but after the GC warms up you should find it's more or less like the ROC: https://software.intel.com/en-us/blogs/2014/06/18/part-1-tuning-java-garbage-collection-for-hbase https://software.intel.com/en-us/blogs/2014/06/18/part-1-tun... (note: that article is about a rather old version but the graphs illustrate the concept) This may not help you if you can't tolerate warmup latency spikes. In that case you need to do some GC tuning to tell the collector enough that it can get it right from the start.
coldcode 10y ago
One thing I don't miss now writing in Swift is a garbage collector. Are there other languages that do something similar to Swift? It seems most languages either use a GC of some kind or make you do your own heap management.
- pjmlp 10y ago
  Swift has a garbage collector. https://www.amazon.com/Garbage-Collection-Algorithms-Automatic-Management/dp/0471941484 https://www.amazon.com/Garbage-Collection-Algorithms-Automat... Check chapter 5.
  - kibwen 10y ago
    I think it's both fair to say that reference counting is a form of garbage collection (dynamic lifetime determination is dynamic lifetime determination), but also remark that reference counting has notably distinct performance characteristics (some good, some bad) compared to a tracing collector.
    - pjmlp 10y ago
      Both being GC algorithms, what one should discuss is implementation advantages and disadvantages of each algorithm. Just like sorting or graph navigation algorithms get discussed, for example. However somehow we get this pop culture of GC vs RC instead.
  - azinman2 10y ago
    To me, a true garbage collector means any cyclic references can be cleared. That is not the case in Swift... you can still leak memory.
    - pjmlp 10y ago
      Which is not true if a data structure happens to have a strong reference, like in a cache or event handler, thus "leaking" in a true garbage collector.
notacoward 10y ago
One thing I wish people in the PL/GC community would take more seriously is the idea of explicitly separate heaps or heap partitions. If it's a problem that pause times can be proportional to heap size with some approaches, then the problem can be alleviated by having more small heaps instead of one large. I've used this approach in my own code, including kernel code, to very good effect. Yet somehow the language features to support this properly have never existed in any language that I know of. At best we get heuristics to approximate it; more often, nothing.
- liveoneggs 10y ago
  erlang has this I think?
- mike_hearn 10y ago
  Research is done. Here is a tech talk on a form of GC integrated into the JVM where the user can annotate regions: http://www.oracle.com/technetwork/java/jvmls2015-wimmer-2637907.pdf http://www.oracle.com/technetwork/java/jvmls2015-wimmer-2637... https://www.youtube.com/watch?v=3JphI1Z0MTk&list=PLX8CzqL3ArzUo2dtMurvpUTAaujPMeuuU&index=12 https://www.youtube.com/watch?v=3JphI1Z0MTk&list=PLX8CzqL3Ar... The region markings are used as hints. Allocations are put into the region when possible and then the region is discarded at the end in one go, which is of course a well explored idea but this one is interesting in that you only scope out the regions and don't need to manually assign each allocation. Also allocations that naturally exist beyond the end of the region work properly without additional effort. One issue is that it's often quite hard to beat a properly tuned generational collector even with techniques that intuitively 'feel' right. As one example, Azul experimented with aggressive hardware-assisted stack allocation on their custom CPU and abandoned it because they found it didn't really beat well tuned generational collection.
  - notacoward 10y ago
    Awesome, thanks!
  - deleted 10y ago
    [deleted]
wangchow 10y ago
Alas, having no garbage collector at all is a blissful state of simplicity when performance matters. It's not very difficult to clean up one's objects manually in a well-thought-out codebase.
- pjmlp 10y ago
  > well-thought-out codebase. Which in real life means a single developer ownership codebase.
  - hood_syntax 10y ago
    Or a meticulous team of very high quality engineers with top notch documentation and design practices. Note that I do agree with you, however, because as you said: > in real life
    - pjmlp 10y ago
      In real life most companies don't want to pay for "meticulous team of very high quality engineers with top notch documentation and design practices". They rather pay for outsourced consultants that deliver something that works within a fixed price contract.
      - wangchow 10y ago
        And most humans are lazy f%$#s who throw things away rather than recycling them.
      - prodigal_erik 10y ago
        Knuth's code has bugs. NASA's code has bugs. There's no reason to believe that high quality software engineers even exist.
        gpderetta 10y ago
        High Quality != 0 bugs. (Small) teams of high quality engineers do exist, but are very expensive.
dkersten 10y ago
I would love to see an implementation of this http://wiki.luajit.org/New-Garbage-Collector http://wiki.luajit.org/New-Garbage-Collector
- rurban 10y ago
  Why? It's still designed to use the worst of the three possible strategies, which Mike tend to ignore. A modern GC is compacting, with mark&copy or copying, if you have enough memory. Mark&sweep is only good for small devices with not enough memory, or a FFI or bad ABI/VM. Walking the heap is always at least 10-100x slower than walking the stack.
  - dkersten 10y ago
    Why? Because I don't know a lot about garbage collectors, but I am familiar with Mikes amazing work on LuaJIT and I trust that he knows enough about what he's talking about (based on the quality of his luajit work) for enough of his claims to be true for this to be interesting, useful or both.
    - PeCaN 10y ago
      The thing you have to understand about Mike's work on the new LuaJIT GC design is that it's heavily constrained by the Lua API. It's not a very interesting GC, though it does improve slightly on the standard tricolor incremental marking GC. See my reply to your other post.
- PeCaN 10y ago
  I implemented something heavily based on that once¹, though no work has gone into optimizing much. It's not particularly state-of-the-art, but it's a good design for what it is. I'll probably use the quad-color strategy in my next incremental GC. Note that while Mike's is strictly non-copying/non-compacting (because of Lua's API) mine does copy between generations and compacts the oldest generation. This makes arena management simpler and faster. I think that's the only significant difference between my implementation and Mike's design. I suspect it's still a bit buggy, though it passes my test suite™. Non-trival GCs can be tricky. And to reiterate, it's not especially fast, because no work has gone into making it fast. (It's not slow either, because the design is good, but don't expect performance competitive with current production GCs².) 1. https://github.com/alpha123/yu https://github.com/alpha123/yu 2. Well, it probably smokes Ruby and Python, but those go solidly in the ‘toy GC’ category.
AstralStorm 10y ago
So, why GC instead of region memory allocation like in Rust? (and some other less known languages)
- kibwen 10y ago
  Rust doesn't use region-based memory management, though the borrow checker does somewhat resemble it. And the reason to use a GC is that it often works well enough for tasks that aren't especially demanding.
costcopizza 10y ago
I thought this was going to be about actual garbage collection and municipal infrastructure. That's what I get for being non-tech and browsing HN!
jeffdavis 10y ago
Are GCs scaling well to new hardware? Memory sizes are increasing, as are core counts. But if those extra cores are being used to GC the larger memory, are we effectively losing those extra cores?
- mike_hearn 10y ago
  That's partly what the article is about. In a pure mark/sweep GC, as the heap size goes up, the work needed to complete a GC cycle and free some memory goes up too. Thus the more memory you use the more cores you need. In more complicated collectors that isn't necessarily the case: collection is incremental and done only as much as needed to keep up with the creation of garbage. As I say in the article, there are reports of people running JVM/G1 on terabyte sized heaps. The problem they have is that if they experience a concurrent mode failure (which G1 is not designed to optimise because in a properly tuned system it's meant to never happen) you're looking at, like, a 5-10 minute pause time whilst the entire heap is mark/sweep and cleaned out as much as possible. So with such huge heaps you'd better make sure the collector doesn't fall behind!
dfox 10y ago
> implementing a generational collector requires the ability to move things around in memory While this is true for traditional implementations with separate heap regions, it is not necessary. One can easily represent new and old generations as linked lists in per-object overhead and just change pointers in such overhead to move objects between generations. There is at least one Smalltalk VM that works in this way and IIRC traditional BEAM (ie. non-HiPE) Erlang VM has GC that works in essentially same way.
- eternalban 10y ago
  > One can easily represent new and old generations as linked lists Sure, it's easy but non-optimal. A side-effect of a moving generational garbage collector is heap compaction and better temporal locality.
- stevefolta 10y ago
  The Boehm collector claims to be generational, and doesn't move memory, but I haven't found the details of its generationality.
  - dfox 10y ago
    The relevant paper describes it as "mostly-parallel, mostly-generational". The idea is that it works like traditional tri-color mark and sweep collector, but white objects stay white between partial collections unless they are modified (ie. reside on memory page that was modified and thus caused memory access trap). In essence it seems to me that difference between generational and incremental/parallel mode lies only in what causes white objects to revert to black (ie. if it happens after each sweep (incremental) or only when sweep does not produce enough free memory (generational)).
skybrian 10y ago
Mike Hearn criticizes the Go implementers for making misleading claims about building a "garbage collector for the next decade", but I don't see them making claims that they are solving garbage collection for any language other than Go? There's an underlying assumption (both in the article and in comments here) that the results of garbage collection research are generally applicable across languages. It's not obvious that this is true. While you can certainly get a lot of ideas from previous research, memory allocation and access patterns can differ significantly between languages (due to different language features and common idioms), and what seemed like a win for one language might not actually apply for a different one.
- jblow 10y ago
  Yeah. I find it a haughty article because he's not acknowledging the elephant in the room, which is that GC is not a solved problem despite all the whiz-bang techniques ... and that the Go people aren't being dishonest or ignorant of these techniques, but rather, judging those techniques not to be so useful for the class of programs they care about.
  - Locke1689 10y ago
    The following statement from the article addresses this: As Go is a relatively ordinary imperative language with value types, its memory access patterns are probably comparable to C# where the generational hypothesis certainly holds and thus .NET uses a generational collector. I think that's reasonable. I would say it is on the Go developers to point out why they think Go would have seriously different performance characteristics from similar C# network applications using Task-based asynchrony (similar to goroutine + channel based asynchrony in Go).
    - Merovius 10y ago
      I don't think this is an actual claim made by go developers. Their arguments for choosing the algorithm they did was (at least as far as I remember, feel free to point me to a source) a) go for implementation simplicity, readability and clarity first then b) once you figure out where it needs improvement, do that. They didn't choose mark-and-sweep because they thought other algorithms are worse, go has special needs or anything else. At least this would be the first time I've heard about it. The same goes, from what I've seen, for most of the arrogance ascribed to them (in this article and elsewhere); it usually hinges on making up or misrepresenting things they've allegedly said.
pklausler 10y ago
When processes are short-lived, sometimes the best GC is exit(2).
jeffdavis 10y ago
Tangent: In databases, it's common to do arena based allocation. You allocate objects of similar lifetime (life of a query, life of a transaction, life of a procedure execution, etc.), and free them all at once when the lifetime is up. When hacking postgresql, for instance, using pfree() is fairly uncommon. You just allocate, (which goes to the current arena by default), and then the arena is wiped out all at once later. Of course, sometimes you might use a lot of memory temporarily in a loop, and you need to pfree() it each iteration. But that is the exception. I think of each arena as a tiny heap (though of course they can grow large).
- buzzybee 10y ago
  I've seen this strategy appear before in real-time situations where new allocations remain in a near-constant band: As long as you have enough memory to make it through one loop, you could use it as the defining strategy of your game engine or signal processor, at least w/r to temporary allocations. I've also heard of GC algorithms using exactly this behavior for the nursery stage.
  - mike_hearn 10y ago
    Arena allocation in C/C++ is doing something similar to generational GC. I was about to type "simulating it" but that's not quite right ... they exploit similar observations to similar effects in different ways. In C/C++ you have to manually decide how short lived allocations are ahead of time and either stack or arena allocate them. Freeing all the allocations on the stack or the arena is then very fast. In a generational GC the programmer doesn't annotate allocations like that ahead of time. Instead it is assumed that all allocations might be short lived. How long they actually live is then tracked and eventually they're moved out of the "arena" (young gen space) by copying them. But again, freeing the contents of the young gen is very fast because you don't actually touch dead data at all, you only copy the live objects. I've heard of GCs that can actually do "pre-tenuring": when the VM knows an allocation will definitely live for a long time based on profiling data it can be allocated directly into the old gen space. That reduces your minor GC pause times further. All this adds overhead of course, but makes automatic something C/C++ devs would do themselves. Given the potentially catastrophic security consequences of screwing up in the C/C++ model I've become a lot less sympathetic to that approach over the years. How much extra performance is a security advisory and possible resulting botnet worth to you?
strictfp 10y ago
We should focus on multiple small heaps instead - like erlang does it. Low latency, high capacity, no stop the world, simple implementation.
bitmapbrother 10y ago
>But if you take one thing away, let it be this: garbage collection is a hard problem, really hard, one that has been studied by an army of computer scientists for decades. So be very suspicious of supposed breakthroughs that everyone else missed. They are more likely to just be strange or unusual tradeoffs in disguise, avoided by others for reasons that may only become apparent later. I really take issue with this. Imagine all of the progress that would have been delayed or quite possibly not achieved had people not persevered against the traditional thinking. Yes, GC is a hard problem but just because something's been researched for a long period of time does not mean there is no room left for innovation. Breakthroughs come some people that think differently not from people that think it's all been done before.
avifreedman 10y ago
I read "typical worst-case pause time" in go and don't know whether to laugh or cry. We are seeing massively longer pauses in production and the suggestion is to go to 1.8, which is not ready. Reminds me of ruby - religious people practicing on production to get the nirvana. Yes, it's getting better, or at least less bad, but yeesh. We'll just waste resources architecting around long pauses, and rewrite critical stuff in C, for a few more years...

434 points by junke 10y ago

The title of Go's GC announcement is "Go GC: Prioritizing low latency and simplicity", and I think that a variation of that would be a better title for this. Some users may prefer a different tradeoff, and I think it's important to know that there is a tradeoff. But as this article says "I have no doubt that many Go users are very happy with the new runtime.", and that seems like a worthwhile metric. https://blog.golang.org/go15gc https://blog.golang.org/go15gc

fropelfizz 10y ago
> But as this article says "I have no doubt that many Go users are very happy with the new runtime.", and that seems like a worthwhile metric. A metric for what? For it making many Go users very happy, or for making rather big claims like "future of GC"?
- Jabbles 10y ago
  Making your users happy seems like a reasonable goal. Neither the article nor the Go announcement suggest this is the "future of GC".
  - boryas 10y ago
    First line of the Go announcement: "Go is building a garbage collector (GC) not only for 2015 but for 2025 and beyond" to me, that suggests they think they have the future of GC
    - Merovius 10y ago
      There is a difference between "a future-proof GC" and "the future of GC".
    - alanbernstein 10y ago
      I thought it was implied that they were talking about a GC for Go specifically.
draw_down 10y ago
That there are tradeoffs is the whole point, the messaging makes it sound like there aren't.
- weberc2 10y ago
  The title says "prioritizing"; if that's not synonymous with "making tradeoffs", I don't know what is.

boardwaalk 10y ago

Interesting article. I haven't internalized all the parameters of the Go GC, but I wonder if there's a way to tune it on the fly. For example, if I want to run at 60 FPS (16ms/frame), and I've measured that actually doing all the CPU side work took 10ms, can I let the GC have ~5ms of GC time (rather than the <1ms advertised) at the end of my frame to increase throughput (read: less cycles burned overtime & better power efficiency)? If not in Go, can I do this elsewhere like on the JVM? Hopefully this isn't too off topic (since the article is about trade-offs of throughput vs latency).

lossolo 10y ago
I don't think you can do it with Go. But you can do it with Nim for example, there if you set 3 ms max GC time you have guarantee that you will only get 3ms of GC time. You can set max time for Java GC also, but from what I seen it's not so strict on G1 collector.
- yoklov 10y ago
  Is there a way to ensure that the amount of time you set aside for GC is, err, enough? I imagine the outcome of it being insufficient would be quite bad... eventually.
sophacles 10y ago
I don't recall a lot about it, but what you described is "real-time garbage collection". If you google that term, you should find some work/writeups related to it :)
mike_hearn 10y ago
That's a realtime GC and yes, you can buy a JVM from IBM that has one, they call it the Metronome collector: http://researcher.watson.ibm.com/researcher/view_group_subpage.php?id=175 http://researcher.watson.ibm.com/researcher/view_group_subpa... Metronome has pause time in the hundreds of microseconds range. The tradeoff it makes is that, amongst other things, it requires read barriers i.e. every time you read a pointer from the heap you have to execute some extra code to interact with the GC subsystem. If you think about how often you read pointers from the heap in a typical program, well, that turns into a lot of barriers and a corresponding execution performance hit.

qznc 10y ago

> It has been known since 1984 that most allocations “die young” i.e. become garbage very soon after being allocated. This observation is called the generational hypothesis and is one of the strongest empirical observations in the entire PL engineering space. It has been consistently true across very different kinds of programming languages and across decades of change in the software industry: it is true for functional languages, imperative languages, languages that don’t have value types and languages that do. Is it really? The linked paper is about Smalltalk. A lot of the research is about Java. Functional probably talks about Haskell and ML. All those languages rely on GC completely. Is this hypothesis still true, when a language allows the programmer to mix different memory management techniques? For example, if you have smart pointer and stack allocation, do objects still "die young"? It might be that these young objects never reach the GC, because they are now allocated elsewhere, which means we have mostly long living objects under GC management. I guess a selective use of the Boehm GC would be the only reasonable way to falsify the hypothesis. Did anybody try that?

_ph_ 10y ago
If you look at a language like Java, where most operations produce some amount of garbage, the observation holds true. If you have a function performing some work, then all memory allocated which is not referenced by the return result, is garbage. And the introduction of generational GC with Hotspot back then, did a lot to improve the Java performance. This is no golden bullet though, as when the young generation overruns during a function call, not all memory allocations local to that function call can be collected, and even worse, they might be promoted to older generations, where they are rather costy to get rid of. Another view on this is, that ideally, you don't perform short lived heap allocations in the first place. Go for example tends to require less heap allocations than Java, and the compiler tries to put them on the stack, if they don't escape the function in which they are allocated. So Go manages to avoid those allocations, which generational GCs are especially good at cleaning up. The idea of generational GC is still considered by the Go team - they plan to have a special heap for each goroutine. This heap would be collected when the groutine exits. This approach would combine the sound idea of generational GC with a pretty good heuristic for the life time of the young generation.

twic 10y ago

An interesting shift in the wind for modern garbage collection comes from microservices. The work on JVM garbage collectors over the last ten years has increasingly been about supporting bigger and bigger heaps efficiently, as physical machines have got bigger, and programs' (or at least application servers') heaps have grown to fill them. Even Shenandoah, a current prototype collector, is designed around large heaps. But with microservices, we use our cavernous machines to house many small heaps instead. That leaves us with rather different garbage collection challenges. So, it's possible that the Go developers will get to ignore decades of progress, as they love to do, and still be competitive, because that progress was towards a different future to the one we arrived at.

agumonkey 10y ago
I'd love to know about other GC schemes. Between no GC and whole VM GC. By type GC, localized sub tree GC. edit: thank you all for your answers, much appreciatedly
- osi 10y ago
  Look at what Erlang's BEAM VM does. It has per-"process" heaps iirc.
- micmus 10y ago
  Erlang has a per-process GC - each Erlang process has it's own heap and it's own garbage collector. There's no VM-wide GC. This usually means the GC pauses apply only to a small part of your system, while the other parts are running completely normally. There's a good article that describes it in depth: https://www.erlang-solutions.com/blog/erlang-19-0-garbage-collector.html https://www.erlang-solutions.com/blog/erlang-19-0-garbage-co...
  - noss 10y ago
    Also if you have a lot of data you use an ets table which is more or less an in-process but off-gc-heap key-value database.
  - 10y ago

draw_down 10y ago

Excellent post, thank you.

LeanderK 10y ago

But why does Go prioritise low latency? I would think that low latency is not super important for web-servers since there are various other factors adding up to the total latency (what i mean here: time spent between call of the http request to finished receiving all bytes).

Jabbles 10y ago
Consider jitter, rather than latency. If you're building a video calling service. You don't want random 10ms gaps between your frames. Also consider fan-out. GC pauses add to the long-tail of latency. If your service depends on many backend services, your overall latency may well depend on the maximum of all your backends.
- DannyB2 10y ago
  Processing video in a GC system is best handled like some other things that are continuous ongoing processing without doing a GC. 1. Allocate all your structures up front. 2. Your main video processing loop (or compression, encryption, signal processing, etc) does not do any memory allocation. This is also like writing games in Java.
hashmal 10y ago
the world of computing isn't just web servers. besides, the vast majority of language implementations already favor throughput over latency when it comes to GC. when latency is a requirement for your project you have no choice but fall back on languages like C. it would be nice to have a viable alternative with managed memory.
- LeanderK 10y ago
  yeah, but when i hear go i think of web servers ;)
- pjmlp 10y ago
  There is still hope for a Modula-3 replacement with the ongoing work on Swift, .NET Native, D, Nim. Even if it still isn't quite here today.

bitwize 10y ago

Why use garbage collection at all when value semantics and smart pointers cover virtually all the use cases for GC, much more efficiently?

raphaelj 10y ago
A generational GC is way more efficient than `std::shared_ptr`. `std::shared_ptr` is implementing a reference counting garbage collection, which is like the most inefficient way of implementing a GC. FYI: - Allocating memory in a generational GC is as fast as allocating something on the stack. It's basically changing the value in a register. It's order of magnitude faster than calling `malloc()`. - A generational garbage collection is slower than freeing a stack frame, but has a lower per item overhead than calling `free()`. tl;dr: for most programs, generational GCs are the fastest at allocating dynamic memory.
- avar 10y ago
  Because calling malloc() & free() is expensive? That's just an implementation detail of your reference-counting GC or malloc(). You can also just pre-allocate memory in batches which makes allocation just changing a pointer to some pre-allocated memory. Many reference based GC's do that, e.g. perl. Or have I entirely misunderstood your comment?
  - Kutta 10y ago
    malloc and free are indeed far more expensive than allocation in a runtime system with copying GC.
  - rwmj 10y ago
    One problem amongst several with allocating memory in batches (or using a pool allocation scheme) is that you end up making poor use of the cache. After a while you have a lot of free memory mixed up with the used memory in your pool (see the article - the generational hypothesis), but because it's spread out a lot of that unused memory gets loaded into cache lines when accessing the memory which is still being used. Having said all that, pool allocators can work really well for certain workloads, especially client-server stuff. Apache uses a pool allocator for serving requests. Pool allocators also fit well with languages like C/C++, but that's just because those languages are very poorly suited to GC, there are much better designed languages which integrate better with modern GC.

lispm 10y ago

> It has been known since 1984 that most allocations “die young” i.e. become garbage very soon after being allocated. 1983: A Real-Time Garbage Collector Based on the Lifetimes of Objects, Lieberman/Hewitt http://web.media.mit.edu/~lieber/Lieberary/GC/Realtime/Realtime.html http://web.media.mit.edu/~lieber/Lieberary/GC/Realtime/Realt... Since objects with short lifetimes account for a large portion of storage use, it is worth optimizing a garbage collector to reclaim storage for these objects more quickly.

voidlogic 10y ago
I'd be interesting to know to what degree Go's aggressive stack-based allocation/escaping makes this hypothesis less strong than other languages. For example, Java a few generations ago was very poor at escaping heap allocation to the stack and so much the opposite skewing towards heap allocation over stack allocation, so I'm sure the JVMs of this era were an extremely good fit for the generational hypothesis.

lossolo 10y ago

I can't wait to see how ROC (Request Oriented Collector) [1] will benefit Go GC. Go is mostly used in web services which means you could collect garbage from whole request when it's over. ROC will try to do that. You can read more about it in the link that I've provided. 1. https://docs.google.com/document/d/1gCsFxXamW8RRvOe5hECz98Ftk-tcRRJcDFANj2VwCB0/edit https://docs.google.com/document/d/1gCsFxXamW8RRvOe5hECz98Ft...

geekingfrog 10y ago
It's addressed in the article. Basically, you can mimick that with a generational GC as long as the youg generation space is large enough to hold all objects from a request.
- mike_hearn 10y ago
  Note that advanced collectors like G1 auto-adjust the young gen size as the program runs. This means pause times can take a little while to settle, but after the GC warms up you should find it's more or less like the ROC: https://software.intel.com/en-us/blogs/2014/06/18/part-1-tuning-java-garbage-collection-for-hbase https://software.intel.com/en-us/blogs/2014/06/18/part-1-tun... (note: that article is about a rather old version but the graphs illustrate the concept) This may not help you if you can't tolerate warmup latency spikes. In that case you need to do some GC tuning to tell the collector enough that it can get it right from the start.

coldcode 10y ago

One thing I don't miss now writing in Swift is a garbage collector. Are there other languages that do something similar to Swift? It seems most languages either use a GC of some kind or make you do your own heap management.

pjmlp 10y ago
Swift has a garbage collector. https://www.amazon.com/Garbage-Collection-Algorithms-Automatic-Management/dp/0471941484 https://www.amazon.com/Garbage-Collection-Algorithms-Automat... Check chapter 5.
- kibwen 10y ago
  I think it's both fair to say that reference counting is a form of garbage collection (dynamic lifetime determination is dynamic lifetime determination), but also remark that reference counting has notably distinct performance characteristics (some good, some bad) compared to a tracing collector.
  - pjmlp 10y ago
    Both being GC algorithms, what one should discuss is implementation advantages and disadvantages of each algorithm. Just like sorting or graph navigation algorithms get discussed, for example. However somehow we get this pop culture of GC vs RC instead.
- azinman2 10y ago
  To me, a true garbage collector means any cyclic references can be cleared. That is not the case in Swift... you can still leak memory.
  - pjmlp 10y ago
    Which is not true if a data structure happens to have a strong reference, like in a cache or event handler, thus "leaking" in a true garbage collector.

notacoward 10y ago

One thing I wish people in the PL/GC community would take more seriously is the idea of explicitly separate heaps or heap partitions. If it's a problem that pause times can be proportional to heap size with some approaches, then the problem can be alleviated by having more small heaps instead of one large. I've used this approach in my own code, including kernel code, to very good effect. Yet somehow the language features to support this properly have never existed in any language that I know of. At best we get heuristics to approximate it; more often, nothing.

liveoneggs 10y ago
erlang has this I think?
mike_hearn 10y ago
Research is done. Here is a tech talk on a form of GC integrated into the JVM where the user can annotate regions: http://www.oracle.com/technetwork/java/jvmls2015-wimmer-2637907.pdf http://www.oracle.com/technetwork/java/jvmls2015-wimmer-2637... https://www.youtube.com/watch?v=3JphI1Z0MTk&list=PLX8CzqL3ArzUo2dtMurvpUTAaujPMeuuU&index=12 https://www.youtube.com/watch?v=3JphI1Z0MTk&list=PLX8CzqL3Ar... The region markings are used as hints. Allocations are put into the region when possible and then the region is discarded at the end in one go, which is of course a well explored idea but this one is interesting in that you only scope out the regions and don't need to manually assign each allocation. Also allocations that naturally exist beyond the end of the region work properly without additional effort. One issue is that it's often quite hard to beat a properly tuned generational collector even with techniques that intuitively 'feel' right. As one example, Azul experimented with aggressive hardware-assisted stack allocation on their custom CPU and abandoned it because they found it didn't really beat well tuned generational collection.
- notacoward 10y ago
  Awesome, thanks!
- deleted 10y ago
  [deleted]

wangchow 10y ago

Alas, having no garbage collector at all is a blissful state of simplicity when performance matters. It's not very difficult to clean up one's objects manually in a well-thought-out codebase.

pjmlp 10y ago
> well-thought-out codebase. Which in real life means a single developer ownership codebase.
- hood_syntax 10y ago
  Or a meticulous team of very high quality engineers with top notch documentation and design practices. Note that I do agree with you, however, because as you said: > in real life
  - pjmlp 10y ago
    In real life most companies don't want to pay for "meticulous team of very high quality engineers with top notch documentation and design practices". They rather pay for outsourced consultants that deliver something that works within a fixed price contract.
    - wangchow 10y ago
      And most humans are lazy f%$#s who throw things away rather than recycling them.
    - prodigal_erik 10y ago
      Knuth's code has bugs. NASA's code has bugs. There's no reason to believe that high quality software engineers even exist.
      - gpderetta 10y ago
        High Quality != 0 bugs. (Small) teams of high quality engineers do exist, but are very expensive.

dkersten 10y ago

I would love to see an implementation of this http://wiki.luajit.org/New-Garbage-Collector http://wiki.luajit.org/New-Garbage-Collector

rurban 10y ago
Why? It's still designed to use the worst of the three possible strategies, which Mike tend to ignore. A modern GC is compacting, with mark&copy or copying, if you have enough memory. Mark&sweep is only good for small devices with not enough memory, or a FFI or bad ABI/VM. Walking the heap is always at least 10-100x slower than walking the stack.
- dkersten 10y ago
  Why? Because I don't know a lot about garbage collectors, but I am familiar with Mikes amazing work on LuaJIT and I trust that he knows enough about what he's talking about (based on the quality of his luajit work) for enough of his claims to be true for this to be interesting, useful or both.
  - PeCaN 10y ago
    The thing you have to understand about Mike's work on the new LuaJIT GC design is that it's heavily constrained by the Lua API. It's not a very interesting GC, though it does improve slightly on the standard tricolor incremental marking GC. See my reply to your other post.
PeCaN 10y ago
I implemented something heavily based on that once¹, though no work has gone into optimizing much. It's not particularly state-of-the-art, but it's a good design for what it is. I'll probably use the quad-color strategy in my next incremental GC. Note that while Mike's is strictly non-copying/non-compacting (because of Lua's API) mine does copy between generations and compacts the oldest generation. This makes arena management simpler and faster. I think that's the only significant difference between my implementation and Mike's design. I suspect it's still a bit buggy, though it passes my test suite™. Non-trival GCs can be tricky. And to reiterate, it's not especially fast, because no work has gone into making it fast. (It's not slow either, because the design is good, but don't expect performance competitive with current production GCs².) 1. https://github.com/alpha123/yu https://github.com/alpha123/yu 2. Well, it probably smokes Ruby and Python, but those go solidly in the ‘toy GC’ category.

AstralStorm 10y ago

So, why GC instead of region memory allocation like in Rust? (and some other less known languages)

kibwen 10y ago
Rust doesn't use region-based memory management, though the borrow checker does somewhat resemble it. And the reason to use a GC is that it often works well enough for tasks that aren't especially demanding.

costcopizza 10y ago

I thought this was going to be about actual garbage collection and municipal infrastructure. That's what I get for being non-tech and browsing HN!

jeffdavis 10y ago

Are GCs scaling well to new hardware? Memory sizes are increasing, as are core counts. But if those extra cores are being used to GC the larger memory, are we effectively losing those extra cores?

mike_hearn 10y ago
That's partly what the article is about. In a pure mark/sweep GC, as the heap size goes up, the work needed to complete a GC cycle and free some memory goes up too. Thus the more memory you use the more cores you need. In more complicated collectors that isn't necessarily the case: collection is incremental and done only as much as needed to keep up with the creation of garbage. As I say in the article, there are reports of people running JVM/G1 on terabyte sized heaps. The problem they have is that if they experience a concurrent mode failure (which G1 is not designed to optimise because in a properly tuned system it's meant to never happen) you're looking at, like, a 5-10 minute pause time whilst the entire heap is mark/sweep and cleaned out as much as possible. So with such huge heaps you'd better make sure the collector doesn't fall behind!

dfox 10y ago

> implementing a generational collector requires the ability to move things around in memory While this is true for traditional implementations with separate heap regions, it is not necessary. One can easily represent new and old generations as linked lists in per-object overhead and just change pointers in such overhead to move objects between generations. There is at least one Smalltalk VM that works in this way and IIRC traditional BEAM (ie. non-HiPE) Erlang VM has GC that works in essentially same way.

eternalban 10y ago
> One can easily represent new and old generations as linked lists Sure, it's easy but non-optimal. A side-effect of a moving generational garbage collector is heap compaction and better temporal locality.
stevefolta 10y ago
The Boehm collector claims to be generational, and doesn't move memory, but I haven't found the details of its generationality.
- dfox 10y ago
  The relevant paper describes it as "mostly-parallel, mostly-generational". The idea is that it works like traditional tri-color mark and sweep collector, but white objects stay white between partial collections unless they are modified (ie. reside on memory page that was modified and thus caused memory access trap). In essence it seems to me that difference between generational and incremental/parallel mode lies only in what causes white objects to revert to black (ie. if it happens after each sweep (incremental) or only when sweep does not produce enough free memory (generational)).

skybrian 10y ago

Mike Hearn criticizes the Go implementers for making misleading claims about building a "garbage collector for the next decade", but I don't see them making claims that they are solving garbage collection for any language other than Go? There's an underlying assumption (both in the article and in comments here) that the results of garbage collection research are generally applicable across languages. It's not obvious that this is true. While you can certainly get a lot of ideas from previous research, memory allocation and access patterns can differ significantly between languages (due to different language features and common idioms), and what seemed like a win for one language might not actually apply for a different one.

jblow 10y ago
Yeah. I find it a haughty article because he's not acknowledging the elephant in the room, which is that GC is not a solved problem despite all the whiz-bang techniques ... and that the Go people aren't being dishonest or ignorant of these techniques, but rather, judging those techniques not to be so useful for the class of programs they care about.
- Locke1689 10y ago
  The following statement from the article addresses this: As Go is a relatively ordinary imperative language with value types, its memory access patterns are probably comparable to C# where the generational hypothesis certainly holds and thus .NET uses a generational collector. I think that's reasonable. I would say it is on the Go developers to point out why they think Go would have seriously different performance characteristics from similar C# network applications using Task-based asynchrony (similar to goroutine + channel based asynchrony in Go).
  - Merovius 10y ago
    I don't think this is an actual claim made by go developers. Their arguments for choosing the algorithm they did was (at least as far as I remember, feel free to point me to a source) a) go for implementation simplicity, readability and clarity first then b) once you figure out where it needs improvement, do that. They didn't choose mark-and-sweep because they thought other algorithms are worse, go has special needs or anything else. At least this would be the first time I've heard about it. The same goes, from what I've seen, for most of the arrogance ascribed to them (in this article and elsewhere); it usually hinges on making up or misrepresenting things they've allegedly said.

pklausler 10y ago

When processes are short-lived, sometimes the best GC is exit(2).

jeffdavis 10y ago

Tangent: In databases, it's common to do arena based allocation. You allocate objects of similar lifetime (life of a query, life of a transaction, life of a procedure execution, etc.), and free them all at once when the lifetime is up. When hacking postgresql, for instance, using pfree() is fairly uncommon. You just allocate, (which goes to the current arena by default), and then the arena is wiped out all at once later. Of course, sometimes you might use a lot of memory temporarily in a loop, and you need to pfree() it each iteration. But that is the exception. I think of each arena as a tiny heap (though of course they can grow large).

buzzybee 10y ago
I've seen this strategy appear before in real-time situations where new allocations remain in a near-constant band: As long as you have enough memory to make it through one loop, you could use it as the defining strategy of your game engine or signal processor, at least w/r to temporary allocations. I've also heard of GC algorithms using exactly this behavior for the nursery stage.
- mike_hearn 10y ago
  Arena allocation in C/C++ is doing something similar to generational GC. I was about to type "simulating it" but that's not quite right ... they exploit similar observations to similar effects in different ways. In C/C++ you have to manually decide how short lived allocations are ahead of time and either stack or arena allocate them. Freeing all the allocations on the stack or the arena is then very fast. In a generational GC the programmer doesn't annotate allocations like that ahead of time. Instead it is assumed that all allocations might be short lived. How long they actually live is then tracked and eventually they're moved out of the "arena" (young gen space) by copying them. But again, freeing the contents of the young gen is very fast because you don't actually touch dead data at all, you only copy the live objects. I've heard of GCs that can actually do "pre-tenuring": when the VM knows an allocation will definitely live for a long time based on profiling data it can be allocated directly into the old gen space. That reduces your minor GC pause times further. All this adds overhead of course, but makes automatic something C/C++ devs would do themselves. Given the potentially catastrophic security consequences of screwing up in the C/C++ model I've become a lot less sympathetic to that approach over the years. How much extra performance is a security advisory and possible resulting botnet worth to you?

strictfp 10y ago

We should focus on multiple small heaps instead - like erlang does it. Low latency, high capacity, no stop the world, simple implementation.

bitmapbrother 10y ago

>But if you take one thing away, let it be this: garbage collection is a hard problem, really hard, one that has been studied by an army of computer scientists for decades. So be very suspicious of supposed breakthroughs that everyone else missed. They are more likely to just be strange or unusual tradeoffs in disguise, avoided by others for reasons that may only become apparent later. I really take issue with this. Imagine all of the progress that would have been delayed or quite possibly not achieved had people not persevered against the traditional thinking. Yes, GC is a hard problem but just because something's been researched for a long period of time does not mean there is no room left for innovation. Breakthroughs come some people that think differently not from people that think it's all been done before.

avifreedman 10y ago

I read "typical worst-case pause time" in go and don't know whether to laugh or cry. We are seeing massively longer pauses in production and the suggestion is to go to 1.8, which is not ready. Reminds me of ruby - religious people practicing on production to get the nirvana. Yes, it's getting better, or at least less bad, but yeesh. We'll just waste resources architecting around long pauses, and rewrite critical stuff in C, for a few more years...