10 ms·

Go GC: Latency Problem Solved [pdf]

101 points by xkarga00 11y ago

joosters 11y ago
Garbage collecting seems to get solved in each new release of Go and Java, apparently.
- rgbrenner 11y ago
  Do you actually follow Go development? 1.5 is a major improvement to the GC. The only other stable release that had any change to the GC worthy of mention in the release notes was 1.3, which was a minor change. The only possible way to interpret your statement as true, would be if "get solved" meant ANY change or bug fix was applied to the GC. Which is a statement that would apply to so much code (not just the GC) that it would make the statement completely meaningless.
  - AlphaSite 11y ago
    It think he means people tout every release as the final solution to their GC issues. Not officially, necessarily, but some vocal group says it.
    - rgbrenner 11y ago
      That's not true either though. Seriously go take a look at the release announcements on hackernews.
      - Alphasite_ 11y ago
        I never said it was.
  - joosters 11y ago
    Yeah, I'm being unfair in naming Go & Java specifically. But these stories of 'fixing' garbage collection come up all too often. I wonder when we'll see a further GC update that trades latency for throughput... The problem seems to be that no matter how you tweak GC, you will always have a class of program that it performs terribly for (and it seems to impact a large group of programs, never just some obscure corner case). So I suspect that this latest GC tweak will have unexpected results on some other class of program, leading to another tweak, and so on...
    - stcredzero 11y ago
      The problem seems to be that no matter how you tweak GC, you will always have a class of program that it performs terribly for For casual use, most programs can treat GC like magic, but if you are doing serious work in a language with GC, then you should learn about the GC's characteristics. That bit of due diligence and up front design effort is still often going to be tons cheaper than doing the manual memory management. Reducing latency in exchange for throughput is the right decision for the vast majority of programs that will be written in Go. It was already a very attractive language for writing a multiplayer game server, so long as I didn't have very large heaps. (Even so, I can still support 150-250 players and 10's of thousands of entities.) With the "tweak," that limitation is much relaxed.
      - banachtarski 11y ago
        > That bit of due diligence and up front design effort is still often going to be tons cheaper than doing the manual memory management. Calling shenanigans. No it's not, unless the person doing the manual solution is a novice.
        stcredzero 11y ago
        It's not the writing of manual memory management in the usual case/happy path that's the problem. It's the very occasional mistake and the debugging time involved. (Though to be fair, automated static analysis tools have taken great strides, and this is not as big a problem as it used to be.) What GC often gets you is a program that doesn't crash but instead has performance problems, but these are often more easily profiled and found and less severe than a crash. (Manual memory management isn't immune from the same performance problems in any case.) In other words, GC gets you to "Step 1 -- Get it Correct" faster so you can play with running code faster. The cost/benefit may not fit your situation. In that case, use a different tool.
        pascal_cuoq 11y ago
        Despite the drastic page limit in the category I was submitting in, I made sure to include a paragraph about how GC enable sharing and how the only reasonable alternative when implementing a similar system in a non-GC language is a lot of gratuitous copying to solve ownership issues in http://frama-c.com/u3cat/download/CuoqICFP09.pdf http://frama-c.com/u3cat/download/CuoqICFP09.pdf (The page limit was 4. Organizers only raised it to 6 after seeing submitted papers.) I can also confirm the “bit of due diligence” part, and the fact that it's cheaper that the aggravation of not having memory management at all. In the example that I can contribute to the discussion, the due diligence amounted to two more short articles: http://cristal.inria.fr/~doligez/publications/cuoq-doligez-mlw-2008.pdf http://cristal.inria.fr/~doligez/publications/cuoq-doligez-m... and http://blog.frama-c.com/public/unmarshal.pdf http://blog.frama-c.com/public/unmarshal.pdf
  - 1wd 11y ago
    What about 1.4? "The release focuses primarily on implementation work, improving the garbage collector ..." https://golang.org/doc/go1.4 https://golang.org/doc/go1.4
    - jlouis 11y ago
      1.4 focused on getting the GC ready for the changes in 1.5. First, the code was rewritten from C to Go. Second, the GC was made precise, which is a major improvement to a GC. The GC was not made truly concurrent however, and short pause times were not addressed either. These concerns are addressed in the 1.5 release. The trade-off in 1.5 is to eliminate pause times for slightly worse throughput. For the programs Go is written to handle, this trade-off is probably fine.
- deleted 11y ago
  [deleted]
- threeseed 11y ago
  The situation for Go and Java isn't comparable. Java has expanded into the big data space in recent years and underpins Hadoop, Spark, HBase, Cassandra etc where they are dealing with heap sizes up to 1TB. The previous GC algorithms are fine for smaller heaps (<32GB) but they needed something for bigger ones hence the introduction of G1GC. Go is very much just trying to get their foundation GC perfected.
  - jsprogrammer 11y ago
    Is there a perfect GC? Seems it would free memory as soon as it's no longer used.
    - danieldk 11y ago
      Depends on the circumstances. If you would free memory as soon as it's no longer used, it could lead to delays when freeing a large object graph. Also, a lot of performance can be gained be re-using frequently-allocated short-lived objects' memory, rather than freeing them without special treatment.
      - strictfp 11y ago
        The biggest problem IMO is that GC is usually used in languages where it gets no free information about variable scope. GC could actually be really useful in C++ or Rust for postponing the destruction of many small objects and doing it in one big sweep instead.
        pcwalton 11y ago
        > GC could actually be really useful in C++ or Rust for postponing the destruction of many small objects and doing it in one big sweep instead. I've seen this claim before, but I've never understood it. You could add delayed reclamation to your system malloc if it actually helped things: just replace free() with a function that adds to a free list but doesn't actually recycle the memory. That wouldn't require more than a couple of writes and a TLS lookup. I suspect that the reason why mallocs don't do this is that there's little benefit compared to just recycling the memory right away. Prompt reclamation is actually really nice for cache reasons, and adding memory blocks to a free list is what free's fast path does in the first place. Now that's not to say that GC wouldn't be useful in C++ or Rust. I think what a GC would be useful for is for lock-free data structures and long-lived structures with dynamic lifetimes, especially ones shared between threads, to eliminate reference counting traffic. But for short-lived objects, if you have any sort of mark phase, you've already lost. Fundamentally, it's really hard to beat a system that precomputes the object lifetimes at compile time—which is what manual memory management is—with a dynamic system that has to compute them at runtime.
- the8472 11y ago
  Newer java GCs generally aim for larger heaps or higher throughput than the previous ones while keeping pause times low. The goals are shifting. I don't even see a mention of parallelism in that PDF. There's probably a lot of room left to squeeze out performance for Go.
rgbrenner 11y ago
This page adds some context to the slides: https://sourcegraph.com/blog/live/gophercon2015/123574706480 https://sourcegraph.com/blog/live/gophercon2015/123574706480 It was posted here 10 days ago: https://news.ycombinator.com/item?id=9854408 https://news.ycombinator.com/item?id=9854408
jnordwick 11y ago
Still slowish. Far far from "solved." The charts they zoom in on only go to about 500MB in heap, showing 2 ms pause times. It makes me suspicious that the nice linear trend he's showing doesn't hold up under more reasonable values -- my IDE takes up 500 MB and my web browser over a GB. So if by his possibly rosy calculations, a basic 3GB heap is still pausing 6 ms. God forbid I use a 500 GB heap and now we're into the one second range again. This is assuming the linear relationship holds up, but given his choice of graph domain, I have a suspicion that there are issues to the right. This seems typical of Google technology. They say they care about performance, but I have yet to see a piece of Google tech that is actually useful if you care about performance. People automatically assume Google is synonymous with performance, but it definitely isn't. Remember, he says this improved GC pause time is going to come at the expense of Go top-line speed. You Go will get slower, and you sill will have second pauses with any serious work.
- desdiv 11y ago
  >my IDE takes up 500 MB and my web browser over a GB. >So if by his possibly rosy calculations, a basic 3GB heap is still pausing 7 ms. How did you arrive at 3GB? Heap spaces of different processes don't add up, you know?
  - deleted 11y ago
    [deleted]
  - jnordwick 11y ago
    I just said typically for about an low-end estimate for what we use at work. We used to be constrained by Java 32-bit since 64-bit was slow so coded for that range. With compressed OOPS we were able to expand, but still have a lot of code on that low side. Now hundred GB heaps are much more the norm.
- mseepgood 11y ago
  The first chart goes up to 20 GB heap size. > This is assuming the linear relationship holds up Their goal for 1.6 is to make it constant, not linear: "Zooming in, there is still a slight positive correlation between heap size and GC pauses. But they know what the issue is and it will be fixed in Go 1.6." https://sourcegraph.com/blog/live/gophercon2015/123574706480 https://sourcegraph.com/blog/live/gophercon2015/123574706480
jmount 11y ago
I thought the issue with GO garbage collectors wasn't so much speed as correctness (as they GO team historically has gotten GCD speed by sacrificing correctness, or is correctness a goal past version 1.3?).
- mseepgood 11y ago
  The Go garbage collector is precise since Go 1.3: https://golang.org/doc/go1.3 https://golang.org/doc/go1.3
Animats 11y ago
The LISP community went through this in the 1980s. They had to; the original Symbolics LISP machine had 45-minute garbage collections, as the GC fought with the virtual memory. There's a long list of tricks. This one is to write-protect data memory during the GC's marking phase, so marking and computation can proceed simultaneously. When the code stores into a write-protected page, the store is trapped and that pointer is logged for GC attention later. This works as long as the GC's marker is faster than the application's pointer changing. There are programs for which this approach is a lose. A large sort of a tree, where pointers are being retargeted with little computation between changes, is such a program. If they're getting 3ms stalls on a 500MB heap, they're doing pretty well. That the stall time doesn't increase with heap size is impressive. Re "avoid fragmentation to begin with by storing objects of the same size in the same memory span." That's easy today, because we have so much memory and address space. The simplest version of that is to allocate memory in units of powers of 2, with each MMU page containing only one size of block. The size round-up wastes memory, of course. But you can use any exponent in the range 1..2, and have, for example, block sizes every 20%. This approach is popular with conservative garbage collectors (ones that don't know what's a pointer and what's just data that looks like a pointer) because the size of a block can be determined from the pointer alone.
- nickpsecurity 11y ago
  You thought of the LISP machines too, eh? Ill mark GC results under my meme: failure to learn from the past. One exception Azul Systems' Vega machines that have a hardware-assisted, concurrent, pauseless GC. What do you think of their approach? Worth emulating in a smaller, hardware project? Note: As usual, I'm thinking along lines of safer, processor design with possible GC. Needs to be a tad faster than i432. ;)
- lispm 11y ago
  Symbolics added an Ephemeral GC in 1985. It keeps a bitmap of modified memory pages with ephemeral objects in RAM. The Ephemeral GC then looked only at those pages. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.125.2438 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.125.... Macintosh Common Lisp later used a similar scheme on 68k machines with MMU.
shmerl 11y ago
I prefer RAII approach to GC.
- reagency 11y ago
  Explain?
  - gavazzy 11y ago
    Not OP, but RAII provides deterministic destruction. That is, it is provable exactly when the object will be deleted. From wikipedia: "Object destruction varies, however – in some languages, notably C++, automatic and dynamic objects are destroyed at deterministic times, such as scope exit, explicit destruction (via manual memory management), or reference count reaching zero; while in other languages, such as C#, Java, and Python, these objects are destroyed at non-deterministic times, depending on the garbage collector, and object resurrection may occur during destruction, extending the lifetime." https://en.wikipedia.org/wiki/Object_lifetime#Determinism https://en.wikipedia.org/wiki/Object_lifetime#Determinism
    - pjmlp 11y ago
      You can have RAII in C#, Java and Python by making use of using/try-with-resources/with, or HOF with monadic constructs. Yes, it isn't as easy as declaring a templated handle manager class on the stack (it won't work for heap objects) in C++, but it also gets the job done.
  - shmerl 11y ago
    It provides deterministic method of automated memory management and avoids this unpredictable latency issue.

101 points by xkarga00 11y ago

joosters 11y ago

Garbage collecting seems to get solved in each new release of Go and Java, apparently.

rgbrenner 11y ago
Do you actually follow Go development? 1.5 is a major improvement to the GC. The only other stable release that had any change to the GC worthy of mention in the release notes was 1.3, which was a minor change. The only possible way to interpret your statement as true, would be if "get solved" meant ANY change or bug fix was applied to the GC. Which is a statement that would apply to so much code (not just the GC) that it would make the statement completely meaningless.
- AlphaSite 11y ago
  It think he means people tout every release as the final solution to their GC issues. Not officially, necessarily, but some vocal group says it.
  - rgbrenner 11y ago
    That's not true either though. Seriously go take a look at the release announcements on hackernews.
    - Alphasite_ 11y ago
      I never said it was.
- joosters 11y ago
  Yeah, I'm being unfair in naming Go & Java specifically. But these stories of 'fixing' garbage collection come up all too often. I wonder when we'll see a further GC update that trades latency for throughput... The problem seems to be that no matter how you tweak GC, you will always have a class of program that it performs terribly for (and it seems to impact a large group of programs, never just some obscure corner case). So I suspect that this latest GC tweak will have unexpected results on some other class of program, leading to another tweak, and so on...
  - stcredzero 11y ago
    The problem seems to be that no matter how you tweak GC, you will always have a class of program that it performs terribly for For casual use, most programs can treat GC like magic, but if you are doing serious work in a language with GC, then you should learn about the GC's characteristics. That bit of due diligence and up front design effort is still often going to be tons cheaper than doing the manual memory management. Reducing latency in exchange for throughput is the right decision for the vast majority of programs that will be written in Go. It was already a very attractive language for writing a multiplayer game server, so long as I didn't have very large heaps. (Even so, I can still support 150-250 players and 10's of thousands of entities.) With the "tweak," that limitation is much relaxed.
    - banachtarski 11y ago
      > That bit of due diligence and up front design effort is still often going to be tons cheaper than doing the manual memory management. Calling shenanigans. No it's not, unless the person doing the manual solution is a novice.
      - stcredzero 11y ago
        It's not the writing of manual memory management in the usual case/happy path that's the problem. It's the very occasional mistake and the debugging time involved. (Though to be fair, automated static analysis tools have taken great strides, and this is not as big a problem as it used to be.) What GC often gets you is a program that doesn't crash but instead has performance problems, but these are often more easily profiled and found and less severe than a crash. (Manual memory management isn't immune from the same performance problems in any case.) In other words, GC gets you to "Step 1 -- Get it Correct" faster so you can play with running code faster. The cost/benefit may not fit your situation. In that case, use a different tool.
      - pascal_cuoq 11y ago
        Despite the drastic page limit in the category I was submitting in, I made sure to include a paragraph about how GC enable sharing and how the only reasonable alternative when implementing a similar system in a non-GC language is a lot of gratuitous copying to solve ownership issues in http://frama-c.com/u3cat/download/CuoqICFP09.pdf http://frama-c.com/u3cat/download/CuoqICFP09.pdf (The page limit was 4. Organizers only raised it to 6 after seeing submitted papers.) I can also confirm the “bit of due diligence” part, and the fact that it's cheaper that the aggravation of not having memory management at all. In the example that I can contribute to the discussion, the due diligence amounted to two more short articles: http://cristal.inria.fr/~doligez/publications/cuoq-doligez-mlw-2008.pdf http://cristal.inria.fr/~doligez/publications/cuoq-doligez-m... and http://blog.frama-c.com/public/unmarshal.pdf http://blog.frama-c.com/public/unmarshal.pdf
- 1wd 11y ago
  What about 1.4? "The release focuses primarily on implementation work, improving the garbage collector ..." https://golang.org/doc/go1.4 https://golang.org/doc/go1.4
  - jlouis 11y ago
    1.4 focused on getting the GC ready for the changes in 1.5. First, the code was rewritten from C to Go. Second, the GC was made precise, which is a major improvement to a GC. The GC was not made truly concurrent however, and short pause times were not addressed either. These concerns are addressed in the 1.5 release. The trade-off in 1.5 is to eliminate pause times for slightly worse throughput. For the programs Go is written to handle, this trade-off is probably fine.
deleted 11y ago
[deleted]
threeseed 11y ago
The situation for Go and Java isn't comparable. Java has expanded into the big data space in recent years and underpins Hadoop, Spark, HBase, Cassandra etc where they are dealing with heap sizes up to 1TB. The previous GC algorithms are fine for smaller heaps (<32GB) but they needed something for bigger ones hence the introduction of G1GC. Go is very much just trying to get their foundation GC perfected.
- jsprogrammer 11y ago
  Is there a perfect GC? Seems it would free memory as soon as it's no longer used.
  - danieldk 11y ago
    Depends on the circumstances. If you would free memory as soon as it's no longer used, it could lead to delays when freeing a large object graph. Also, a lot of performance can be gained be re-using frequently-allocated short-lived objects' memory, rather than freeing them without special treatment.
    - strictfp 11y ago
      The biggest problem IMO is that GC is usually used in languages where it gets no free information about variable scope. GC could actually be really useful in C++ or Rust for postponing the destruction of many small objects and doing it in one big sweep instead.
      - pcwalton 11y ago
        > GC could actually be really useful in C++ or Rust for postponing the destruction of many small objects and doing it in one big sweep instead. I've seen this claim before, but I've never understood it. You could add delayed reclamation to your system malloc if it actually helped things: just replace free() with a function that adds to a free list but doesn't actually recycle the memory. That wouldn't require more than a couple of writes and a TLS lookup. I suspect that the reason why mallocs don't do this is that there's little benefit compared to just recycling the memory right away. Prompt reclamation is actually really nice for cache reasons, and adding memory blocks to a free list is what free's fast path does in the first place. Now that's not to say that GC wouldn't be useful in C++ or Rust. I think what a GC would be useful for is for lock-free data structures and long-lived structures with dynamic lifetimes, especially ones shared between threads, to eliminate reference counting traffic. But for short-lived objects, if you have any sort of mark phase, you've already lost. Fundamentally, it's really hard to beat a system that precomputes the object lifetimes at compile time—which is what manual memory management is—with a dynamic system that has to compute them at runtime.
the8472 11y ago
Newer java GCs generally aim for larger heaps or higher throughput than the previous ones while keeping pause times low. The goals are shifting. I don't even see a mention of parallelism in that PDF. There's probably a lot of room left to squeeze out performance for Go.

rgbrenner 11y ago

This page adds some context to the slides: https://sourcegraph.com/blog/live/gophercon2015/123574706480 https://sourcegraph.com/blog/live/gophercon2015/123574706480 It was posted here 10 days ago: https://news.ycombinator.com/item?id=9854408 https://news.ycombinator.com/item?id=9854408

jnordwick 11y ago

Still slowish. Far far from "solved." The charts they zoom in on only go to about 500MB in heap, showing 2 ms pause times. It makes me suspicious that the nice linear trend he's showing doesn't hold up under more reasonable values -- my IDE takes up 500 MB and my web browser over a GB. So if by his possibly rosy calculations, a basic 3GB heap is still pausing 6 ms. God forbid I use a 500 GB heap and now we're into the one second range again. This is assuming the linear relationship holds up, but given his choice of graph domain, I have a suspicion that there are issues to the right. This seems typical of Google technology. They say they care about performance, but I have yet to see a piece of Google tech that is actually useful if you care about performance. People automatically assume Google is synonymous with performance, but it definitely isn't. Remember, he says this improved GC pause time is going to come at the expense of Go top-line speed. You Go will get slower, and you sill will have second pauses with any serious work.

desdiv 11y ago
>my IDE takes up 500 MB and my web browser over a GB. >So if by his possibly rosy calculations, a basic 3GB heap is still pausing 7 ms. How did you arrive at 3GB? Heap spaces of different processes don't add up, you know?
- deleted 11y ago
  [deleted]
- jnordwick 11y ago
  I just said typically for about an low-end estimate for what we use at work. We used to be constrained by Java 32-bit since 64-bit was slow so coded for that range. With compressed OOPS we were able to expand, but still have a lot of code on that low side. Now hundred GB heaps are much more the norm.
mseepgood 11y ago
The first chart goes up to 20 GB heap size. > This is assuming the linear relationship holds up Their goal for 1.6 is to make it constant, not linear: "Zooming in, there is still a slight positive correlation between heap size and GC pauses. But they know what the issue is and it will be fixed in Go 1.6." https://sourcegraph.com/blog/live/gophercon2015/123574706480 https://sourcegraph.com/blog/live/gophercon2015/123574706480

jmount 11y ago

I thought the issue with GO garbage collectors wasn't so much speed as correctness (as they GO team historically has gotten GCD speed by sacrificing correctness, or is correctness a goal past version 1.3?).

mseepgood 11y ago
The Go garbage collector is precise since Go 1.3: https://golang.org/doc/go1.3 https://golang.org/doc/go1.3

Animats 11y ago

The LISP community went through this in the 1980s. They had to; the original Symbolics LISP machine had 45-minute garbage collections, as the GC fought with the virtual memory. There's a long list of tricks. This one is to write-protect data memory during the GC's marking phase, so marking and computation can proceed simultaneously. When the code stores into a write-protected page, the store is trapped and that pointer is logged for GC attention later. This works as long as the GC's marker is faster than the application's pointer changing. There are programs for which this approach is a lose. A large sort of a tree, where pointers are being retargeted with little computation between changes, is such a program. If they're getting 3ms stalls on a 500MB heap, they're doing pretty well. That the stall time doesn't increase with heap size is impressive. Re "avoid fragmentation to begin with by storing objects of the same size in the same memory span." That's easy today, because we have so much memory and address space. The simplest version of that is to allocate memory in units of powers of 2, with each MMU page containing only one size of block. The size round-up wastes memory, of course. But you can use any exponent in the range 1..2, and have, for example, block sizes every 20%. This approach is popular with conservative garbage collectors (ones that don't know what's a pointer and what's just data that looks like a pointer) because the size of a block can be determined from the pointer alone.

nickpsecurity 11y ago
You thought of the LISP machines too, eh? Ill mark GC results under my meme: failure to learn from the past. One exception Azul Systems' Vega machines that have a hardware-assisted, concurrent, pauseless GC. What do you think of their approach? Worth emulating in a smaller, hardware project? Note: As usual, I'm thinking along lines of safer, processor design with possible GC. Needs to be a tad faster than i432. ;)
lispm 11y ago
Symbolics added an Ephemeral GC in 1985. It keeps a bitmap of modified memory pages with ephemeral objects in RAM. The Ephemeral GC then looked only at those pages. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.125.2438 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.125.... Macintosh Common Lisp later used a similar scheme on 68k machines with MMU.

shmerl 11y ago

I prefer RAII approach to GC.

reagency 11y ago
Explain?
- gavazzy 11y ago
  Not OP, but RAII provides deterministic destruction. That is, it is provable exactly when the object will be deleted. From wikipedia: "Object destruction varies, however – in some languages, notably C++, automatic and dynamic objects are destroyed at deterministic times, such as scope exit, explicit destruction (via manual memory management), or reference count reaching zero; while in other languages, such as C#, Java, and Python, these objects are destroyed at non-deterministic times, depending on the garbage collector, and object resurrection may occur during destruction, extending the lifetime." https://en.wikipedia.org/wiki/Object_lifetime#Determinism https://en.wikipedia.org/wiki/Object_lifetime#Determinism
  - pjmlp 11y ago
    You can have RAII in C#, Java and Python by making use of using/try-with-resources/with, or HOF with monadic constructs. Yes, it isn't as easy as declaring a templated handle manager class on the stack (it won't work for heap objects) in C++, but it also gets the job done.
- shmerl 11y ago
  It provides deterministic method of automated memory management and avoids this unpredictable latency issue.