8 ms·

Mark–Scavenge: Waiting for Trash to Take Itself Out

166 points by vips7L 2y ago

throwaway81523 2y ago
I thought comparing reachability to "true" liveness had been studied in the past. Ben Zorn may have worked on it in the 1980s: https://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5313.html https://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5313.html Also: https://people.cs.umass.edu/~emery/pubs/04-17.pdf https://people.cs.umass.edu/~emery/pubs/04-17.pdf
A4ET8a8uTh0 2y ago
What a time to be alive, I read it the opening fully expecting to see an open source automated trashcan that takes itself to the curb each Monday. I was disappointed to find out it is about an actual garbage collection algorithm.
- garblegarble 2y ago
  I know this is completely off-topic, but you might be interested in this[1] YouTuber who did something not far off that... 1: https://www.youtube.com/watch?v=VhYEOG9LOIk https://www.youtube.com/watch?v=VhYEOG9LOIk
kibwen 2y ago
> Modern garbage collection assumes that the weak generational hypothesis holds and that most objects die young Aside, I'm curious how first-class support for value types and Go-style stack allocation via escape analysis changes the value proposition of the generational hypothesis. If we hypothesize that short-lived objects are local to a single function scope (and thus eligible for stack allocation either explicitly via a value type or heuristically via escape analysis) then it might completely upend the generational hypothesis and make it so that relatively more long-lived objects are getting heap-allocated. Surely someone's done some studies on this?
- DamonHD 2y ago
  AFAIK not nearly enough stuff gets caught by escape analysis - and thus stack allocated - to make a difference.
  - kibwen 2y ago
    I'm open to believing that this is true, but some real numbers would be nice. Surely it wouldn't be a hugely invasive change to fork the Go compiler, change the stack allocation check to `return false`, and then measure the overhead of the garbage collector on real Go programs with stack allocation both enabled and disabled.
    - DamonHD 2y ago
      I may have been answering past you - I am thinking of Java running on the JDK here. And indeed I may be out of date also.
      - cempaka 2y ago
        Yeah in Java land specifically I think the question would become, "does the generational hypothesis still hold up once we have Valhalla and a much larger share of short-lived objects are stack allocated as value types?" but of course it may be years until the ecosystem reaches that point, if ever.
        neonsunset 2y ago
        As shown by C#, it will generally continue to be relevant since both primarily use JIT compilation with ability to modify code at runtime which can violate inter-procedural escape analysis assumptions leading to heap allocations of the objects that are passed down to the callees (there is work scheduled for .NET 10 to address this, at least for AOT compilation where interproc analysis conclusions will be impossible to violate). You can craft a workload which violates the hypothesis by only allocating objects that live for a long time but both JVM and .NET GC implementations are still much faster designs than Go's GC which prioritizes small memory footprint and consistent latency on low allocation traffic (though as of .NET 9, SRV GC puts much more priority on this, making similar tradeoffs).
fweimer 2y ago
How does this relate to Shenandoah's region selection logic? Doesn't it have similar behavior?
m463 2y ago
This is fascinating. The idea of mark/scavenge is pretty cool for page-based allocation and deallocation. Also real-time or maybe latency-intolerant systems, which basically can't block for garbage collection. You could probably keep scavenging and stay ahead of things without impacting things in a black and white way.
- AtlasBarfed 2y ago
  This may be naive, but gc has now been around since the java days at mass scale (that is I'm calling java the first mass market GC computing system, just go with it for now) for about 30 years. The big lie of GC is that you never need to worry about memory management. The insidious lie is that you have no control when you do need it Rust went with a new extreme: no GC, but the compiler does a memory verification and a LOT of obscure complex notation and keywords So ... I'm wondering if there is a happy medium, where you can have keywords that strongly hint to a GC how to manage memory (eg arena/permanent, thread group bound, local/young, etc) that will be easier than rust. Maybe we could have multiple heaps defined (a big problem with GC heaps is the bigger they are the harder it is for the bigO of the management algorithms to scale, so nice they aren't linear bigO). I'm thinking of something like Cassandra where tables and even subsections of tables don't need their bloom filters, commit logs, atc all intermingled in a single heap, to the great detriment of heao performance. Instead, provide annotations to partition the heaps or run multiple heaps Of course this is a massive complexity rabbit hole/slippery slide.
  - m463 2y ago
    I remember a long time ago using the apache portable runtime and pool malloc was pretty interesting. I believe it probably was designed around web requests - which could disappear at any time. The idea was that you allocated a memory pool, and did all your mallocs within that pool. If there was a problem, you could easily clean up and free the entire pool. I think this idea could work really well the the memory system - a pool could be a number of underlying pages and gc would be easy, and letting go of the pages would be too.
  - funcDropShadow 2y ago
codetrotter 2y ago
I was wondering if the .java TLD belonged to the Java island, or to Oracle or to someone else. https://icannwiki.org/.java https://icannwiki.org/.java It’s Oracle.

166 points by vips7L 2y ago

I thought comparing reachability to "true" liveness had been studied in the past. Ben Zorn may have worked on it in the 1980s: https://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5313.html https://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5313.html Also: https://people.cs.umass.edu/~emery/pubs/04-17.pdf https://people.cs.umass.edu/~emery/pubs/04-17.pdf

A4ET8a8uTh0 2y ago

What a time to be alive, I read it the opening fully expecting to see an open source automated trashcan that takes itself to the curb each Monday. I was disappointed to find out it is about an actual garbage collection algorithm.

garblegarble 2y ago
I know this is completely off-topic, but you might be interested in this[1] YouTuber who did something not far off that... 1: https://www.youtube.com/watch?v=VhYEOG9LOIk https://www.youtube.com/watch?v=VhYEOG9LOIk

kibwen 2y ago

> Modern garbage collection assumes that the weak generational hypothesis holds and that most objects die young Aside, I'm curious how first-class support for value types and Go-style stack allocation via escape analysis changes the value proposition of the generational hypothesis. If we hypothesize that short-lived objects are local to a single function scope (and thus eligible for stack allocation either explicitly via a value type or heuristically via escape analysis) then it might completely upend the generational hypothesis and make it so that relatively more long-lived objects are getting heap-allocated. Surely someone's done some studies on this?

DamonHD 2y ago
AFAIK not nearly enough stuff gets caught by escape analysis - and thus stack allocated - to make a difference.
- kibwen 2y ago
  I'm open to believing that this is true, but some real numbers would be nice. Surely it wouldn't be a hugely invasive change to fork the Go compiler, change the stack allocation check to `return false`, and then measure the overhead of the garbage collector on real Go programs with stack allocation both enabled and disabled.
  - DamonHD 2y ago
    I may have been answering past you - I am thinking of Java running on the JDK here. And indeed I may be out of date also.
    - cempaka 2y ago
      Yeah in Java land specifically I think the question would become, "does the generational hypothesis still hold up once we have Valhalla and a much larger share of short-lived objects are stack allocated as value types?" but of course it may be years until the ecosystem reaches that point, if ever.
      - neonsunset 2y ago
        As shown by C#, it will generally continue to be relevant since both primarily use JIT compilation with ability to modify code at runtime which can violate inter-procedural escape analysis assumptions leading to heap allocations of the objects that are passed down to the callees (there is work scheduled for .NET 10 to address this, at least for AOT compilation where interproc analysis conclusions will be impossible to violate). You can craft a workload which violates the hypothesis by only allocating objects that live for a long time but both JVM and .NET GC implementations are still much faster designs than Go's GC which prioritizes small memory footprint and consistent latency on low allocation traffic (though as of .NET 9, SRV GC puts much more priority on this, making similar tradeoffs).

fweimer 2y ago

How does this relate to Shenandoah's region selection logic? Doesn't it have similar behavior?

m463 2y ago

This is fascinating. The idea of mark/scavenge is pretty cool for page-based allocation and deallocation. Also real-time or maybe latency-intolerant systems, which basically can't block for garbage collection. You could probably keep scavenging and stay ahead of things without impacting things in a black and white way.

AtlasBarfed 2y ago
This may be naive, but gc has now been around since the java days at mass scale (that is I'm calling java the first mass market GC computing system, just go with it for now) for about 30 years. The big lie of GC is that you never need to worry about memory management. The insidious lie is that you have no control when you do need it Rust went with a new extreme: no GC, but the compiler does a memory verification and a LOT of obscure complex notation and keywords So ... I'm wondering if there is a happy medium, where you can have keywords that strongly hint to a GC how to manage memory (eg arena/permanent, thread group bound, local/young, etc) that will be easier than rust. Maybe we could have multiple heaps defined (a big problem with GC heaps is the bigger they are the harder it is for the bigO of the management algorithms to scale, so nice they aren't linear bigO). I'm thinking of something like Cassandra where tables and even subsections of tables don't need their bloom filters, commit logs, atc all intermingled in a single heap, to the great detriment of heao performance. Instead, provide annotations to partition the heaps or run multiple heaps Of course this is a massive complexity rabbit hole/slippery slide.
- m463 2y ago
  I remember a long time ago using the apache portable runtime and pool malloc was pretty interesting. I believe it probably was designed around web requests - which could disappear at any time. The idea was that you allocated a memory pool, and did all your mallocs within that pool. If there was a problem, you could easily clean up and free the entire pool. I think this idea could work really well the the memory system - a pool could be a number of underlying pages and gc would be easy, and letting go of the pages would be too.
- funcDropShadow 2y ago

codetrotter 2y ago

I was wondering if the .java TLD belonged to the Java island, or to Oracle or to someone else. https://icannwiki.org/.java https://icannwiki.org/.java It’s Oracle.