8 ms·

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

by 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.
- pron 10y ago
  The stack has very little to do with it; see my other comment. The reason Go's GC needs to work less is because Go has arrays-of-structs, while Java doesn't (yet; should be coming in Java 10).
  - pjmlp 10y ago
    And IBM's JVM already has an extension called Packed Objects. http://www.ibm.com/support/knowledgecenter/SSYKE2_8.0.0/com.ibm.java.lnx.80.doc/user/packed_intro.html http://www.ibm.com/support/knowledgecenter/SSYKE2_8.0.0/com....
pron 10y ago
> 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. Where elsewhere? The stack? One of the things people always get wrong about GC challenges is "what about stack allocation?". Modern servers come with up to 6TB of RAM. Applications that are interesting from a GC perspective (i.e., lots of concurrency, data structures etc.) commonly employ heaps that are between 10s and 100s of GBs today. The amount of memory available on stacks is 0.5-10% (thousands of threads are required for the high amount) at most. In other words, stack allocation does not remove the needle by much (although it may affect the frequency of young-gen collections). The Java team discovered that when they added escape analysis and stack allocation, and the effect was not dramatic. The stack simply does not matter that much in the grand scheme of things (arrays-of-structs, OTOH, matter a great deal).
- qznc 10y ago
  Ok, then array-of-structs. Maybe obstacks (region-based allocation). All that stuff that cannot be done in Java, Smalltalk, etc. Does that invalidate the generational hypothesis or not?
  - pjmlp 10y ago
    > All that stuff that cannot be done in Java Maybe not on the standard implementation, but just like C and C++, Java also enjoys some extensions. Packed Objects in IBM J9 http://www.ibm.com/support/knowledgecenter/SSYKE2_8.0.0/com.ibm.java.lnx.80.doc/user/packed_intro.html http://www.ibm.com/support/knowledgecenter/SSYKE2_8.0.0/com.... ObjectLayout in Azul http://www.azulsystems.com/content/goto-conference-chicago-2015-2 http://www.azulsystems.com/content/goto-conference-chicago-2... And in some standard form in Java 10 http://openjdk.java.net/jeps/169 http://openjdk.java.net/jeps/169
  - pron 10y ago
    I guess we'll see when Java gets value types soon, but the Go people can answer that now; only problem is, I'm not sure people build as many and as-data-heavy applications in Go as they do in Java just yet. Also, realtime Java VMs do support arenas (even scoped arenas). So, I don't know the answer, but let's put it this way: I haven't heard anyone saying it isn't true -- and that would be a pretty big thing -- even though there should be enough indicators by now.
pjmlp 10y ago
We had languages like Mesa/Cedar, Modula-2+, Modula-3, Oberon, Oberon-2, Active Oberon, Component Pascal, Eiffel that allow for GC algorithms, stack allocation and if really required unsafe memory management. Even .NET allows for it, but most .NET related research lives within MSR walls, and many don't follow it because Microsoft. So we got Java as the main platform for GC research and only now, thanks to market pressure are we seeing such features planned for Java 10.
- notacoward 10y ago
  > So we got Java as the main platform for GC research Perhaps we did, but it's not because it was the only option. Python has the same need, has always been open source, and has been very popular for as long as Java. Ruby was even more popular than Python for a while, JavaScript might be now. Why didn't much GC research happen in those environments? Is it because people who do GC research looked down their nose at mere scripting languages, even though out in the field all of these have been used for more serious kinds of development? Or is it something else?
  - geodel 10y ago
    It is more likely Oracle/IBM etc put more dollars where their GC is.
  - pjmlp 10y ago
    Probably because those communities aren't welcoming much that type of research and rather use C than an improved VM stack. There are better options to run Python and Ruby than CPython and MRI in terms of performance, yet they lack mainstream adoption.
  - mike_hearn 10y ago
    Java has a think called Jikes, which is a JVM implemented in Java, garbage collectors included. Being implemented in a higher level language makes it much easier to hack on, and in a time-pressured academic environment that makes it a more attractive platform for research than VMs written in C++ (or worse, C). Hundreds of papers have been published on Jikes-based research over the years.
dfox 10y ago
There are languages whose execution model inherently produce large amounts of short-lived objects as sideffect of execution of some code with no explicit allocations, Smalltalk and Scheme with call/cc are probably best examples with Python being comparable, albeit for different reasons. On the other hand, very often it's convenient to just return some freshly allocated object out of function invocation (non-obvious, but trivial example: string), which is why the generational hypothesis tends to hold for almost any language.
- jblow 10y ago
  Sure, but it's also worth pointing out that the class of programs that behave this way is the class of programs that are inefficient to begin with. If you handle strings, and you are copying and freeing strings all the time, that's just slow code. And it's not the case that GC makes the slow code faster... it's that certain techniques enable GC to not fail catastrophically on slow code. It's a little bit disturbing that folks are ready to extrapolate this to some kind of universal rule. In a high-end video game, for example, we hardly allocate anything short-term at runtime. The whole program is architected to avoid it. When we allocate, it tends to be things with medium-to-long-term life (texture maps, sound effects, render targets, whatever) so a generational system is useless there. In fact we don't use GC on these kinds of things at all, because we also need to control exactly when they are deallocated so we can put something in their place, because memory is limited.
  - AlphaSite 10y ago
    You have things that only live for a short while do you not? Object pooling, stack allocation, etc are designed to solve that problem as I understand it.
    - phantarch 10y ago
      While the objects in the pools or stacks may seem transient (on your screen for only a few moments), one simple technique is to only allocate those objects at load time and then flip them in an "on" or "off" state during gameplay. That way you're not doing any real allocation after your game space has loaded.

by qznc 10y ago

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

pron 10y ago
The stack has very little to do with it; see my other comment. The reason Go's GC needs to work less is because Go has arrays-of-structs, while Java doesn't (yet; should be coming in Java 10).
- pjmlp 10y ago
  And IBM's JVM already has an extension called Packed Objects. http://www.ibm.com/support/knowledgecenter/SSYKE2_8.0.0/com.ibm.java.lnx.80.doc/user/packed_intro.html http://www.ibm.com/support/knowledgecenter/SSYKE2_8.0.0/com....

pron 10y ago

> 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. Where elsewhere? The stack? One of the things people always get wrong about GC challenges is "what about stack allocation?". Modern servers come with up to 6TB of RAM. Applications that are interesting from a GC perspective (i.e., lots of concurrency, data structures etc.) commonly employ heaps that are between 10s and 100s of GBs today. The amount of memory available on stacks is 0.5-10% (thousands of threads are required for the high amount) at most. In other words, stack allocation does not remove the needle by much (although it may affect the frequency of young-gen collections). The Java team discovered that when they added escape analysis and stack allocation, and the effect was not dramatic. The stack simply does not matter that much in the grand scheme of things (arrays-of-structs, OTOH, matter a great deal).

qznc 10y ago
Ok, then array-of-structs. Maybe obstacks (region-based allocation). All that stuff that cannot be done in Java, Smalltalk, etc. Does that invalidate the generational hypothesis or not?
- pjmlp 10y ago
  > All that stuff that cannot be done in Java Maybe not on the standard implementation, but just like C and C++, Java also enjoys some extensions. Packed Objects in IBM J9 http://www.ibm.com/support/knowledgecenter/SSYKE2_8.0.0/com.ibm.java.lnx.80.doc/user/packed_intro.html http://www.ibm.com/support/knowledgecenter/SSYKE2_8.0.0/com.... ObjectLayout in Azul http://www.azulsystems.com/content/goto-conference-chicago-2015-2 http://www.azulsystems.com/content/goto-conference-chicago-2... And in some standard form in Java 10 http://openjdk.java.net/jeps/169 http://openjdk.java.net/jeps/169
- pron 10y ago
  I guess we'll see when Java gets value types soon, but the Go people can answer that now; only problem is, I'm not sure people build as many and as-data-heavy applications in Go as they do in Java just yet. Also, realtime Java VMs do support arenas (even scoped arenas). So, I don't know the answer, but let's put it this way: I haven't heard anyone saying it isn't true -- and that would be a pretty big thing -- even though there should be enough indicators by now.

pjmlp 10y ago

We had languages like Mesa/Cedar, Modula-2+, Modula-3, Oberon, Oberon-2, Active Oberon, Component Pascal, Eiffel that allow for GC algorithms, stack allocation and if really required unsafe memory management. Even .NET allows for it, but most .NET related research lives within MSR walls, and many don't follow it because Microsoft. So we got Java as the main platform for GC research and only now, thanks to market pressure are we seeing such features planned for Java 10.

notacoward 10y ago
> So we got Java as the main platform for GC research Perhaps we did, but it's not because it was the only option. Python has the same need, has always been open source, and has been very popular for as long as Java. Ruby was even more popular than Python for a while, JavaScript might be now. Why didn't much GC research happen in those environments? Is it because people who do GC research looked down their nose at mere scripting languages, even though out in the field all of these have been used for more serious kinds of development? Or is it something else?
- geodel 10y ago
  It is more likely Oracle/IBM etc put more dollars where their GC is.
- pjmlp 10y ago
  Probably because those communities aren't welcoming much that type of research and rather use C than an improved VM stack. There are better options to run Python and Ruby than CPython and MRI in terms of performance, yet they lack mainstream adoption.
- mike_hearn 10y ago
  Java has a think called Jikes, which is a JVM implemented in Java, garbage collectors included. Being implemented in a higher level language makes it much easier to hack on, and in a time-pressured academic environment that makes it a more attractive platform for research than VMs written in C++ (or worse, C). Hundreds of papers have been published on Jikes-based research over the years.

dfox 10y ago

There are languages whose execution model inherently produce large amounts of short-lived objects as sideffect of execution of some code with no explicit allocations, Smalltalk and Scheme with call/cc are probably best examples with Python being comparable, albeit for different reasons. On the other hand, very often it's convenient to just return some freshly allocated object out of function invocation (non-obvious, but trivial example: string), which is why the generational hypothesis tends to hold for almost any language.

jblow 10y ago
Sure, but it's also worth pointing out that the class of programs that behave this way is the class of programs that are inefficient to begin with. If you handle strings, and you are copying and freeing strings all the time, that's just slow code. And it's not the case that GC makes the slow code faster... it's that certain techniques enable GC to not fail catastrophically on slow code. It's a little bit disturbing that folks are ready to extrapolate this to some kind of universal rule. In a high-end video game, for example, we hardly allocate anything short-term at runtime. The whole program is architected to avoid it. When we allocate, it tends to be things with medium-to-long-term life (texture maps, sound effects, render targets, whatever) so a generational system is useless there. In fact we don't use GC on these kinds of things at all, because we also need to control exactly when they are deallocated so we can put something in their place, because memory is limited.
- AlphaSite 10y ago
  You have things that only live for a short while do you not? Object pooling, stack allocation, etc are designed to solve that problem as I understand it.
  - phantarch 10y ago
    While the objects in the pools or stacks may seem transient (on your screen for only a few moments), one simple technique is to only allocate those objects at load time and then flip them in an "on" or "off" state during gameplay. That way you're not doing any real allocation after your game space has loaded.