6 ms·

Practical Garbage Collection - Part 1: Introduction

181 points by cgbystrom 15y ago

stcredzero 15y ago
What are the long term implications of the increasing amount of parallel computing resources available to programmers? Are we getting to a point where there is enough excess CPU available, that the extra instruction on every assignment for reference counting is no big deal? (In certain contexts. In some contexts extra instructions are always a big deal, but these don't span all of computing.) Combine that with incremental algorithms for cycle reclamation, and you'd have great low-latency GC.
- martincmartin 15y ago
  The the object can be accessed (not modified, just accessed) from multiple threads, the extra instruction needs to be a thread safe atomic increment, which is hugely expensive, and becomes more expensive the more cores you have, especially in a NUMA architecture. Also, when an object is freed, you need to decrement the reference count of every single object it points to, even objects that are referenced from many other places and clearly won't be reclaimed for a long time.
- larsberg 15y ago
  It's still not trivial even with massive parallelism. Performance is easily killed if you: 1) Completely saturate the memory interconnect between the processors and RAM chips 2) If your parallel collector threads are touching the same memory that your worker threads are, you're going to have some cache contention 3) One of the big challenges with cache lines that have writes in them is if they are shared between processors. For example, create two ref cells and have two parallel threads set them -- if the compiler did not happen to pad them out to cache line size, they'll be fighting for the same 64 bytes (8 64-bit words/pointers) of memory We (Manticore) have done a lot of work to isolate the per-CPU work, heap pages, etc. (http://arxiv.org/abs/1105.2554 http://arxiv.org/abs/1105.2554 , MSPC 2011 proceedings should be out on acm.org soon-ish). But it's not easy and requires rearchitecting your whole compiler and runtime system. GHC is also in the middle of some similar work, and they have a much harder problem both due to the challenges of implementing laziness and they have a full-featured system and real user base, so they can't just change things willy-nilly. Further, once you get the parallelism right, you end up in a different situation: Amdahl's Law bites. Even if 90% of your program is amenable to parallel work, if you make that portion go infinitely fast, you still have a sequential portion that takes 10% of the time and therefore limits you to a maximum of 10x speedup. We are hitting that limitation right now in our research and going back to do more sequential performance work. I've got a small army of undergraduates implementing compiler optimizations and analyses :-)
pixie_ 15y ago
The complexity of generational garbage collection vs. the speed of manual collection, makes me feel like the happy medium of speed and simplicity is reference counting, like that found in objective-c. iPhone apps are fast, but take a bit longer to design, develop, and debug due to memory management issues. Though with experience these can be minimized. It probably isn't possible without a ton of modification, but I wish the JVM/CLR had an option to garbage collect through reference counting.
- eru 15y ago
  Reference counting is slower than proper garbage collection, since it adds an overhead for each access, instead of just during the collection. (There are ways to make reference counting faster, but they are no longer quite so simple.)
  - benhoyt 15y ago
    It's not quite true to say reference counting adds overhead "for each access" -- for example, you can easily have a loop which accesses an object but doesn't modify the reference count. Reference counting adds overhead each time someone "expresses an ownership interest" in an object (wording from http://developer.apple.com/library/ios/#documentation/general/conceptual/devpedia-cocoacore/MemoryManagement.html http://developer.apple.com/library/ios/#documentation/genera...). (That's not to say your main point is false. I don't actually know which is faster in general.)
    - aardvark179 15y ago
      This is true, but has to be thought through very carefully in multithreaded environments where another thread might remove an object from a collection, causing it to be deleted while you're still looking at it. Safe looping then requires locks or cloning the collection (which is suddenly more expensive because it will hit all the contents' ref counts). In summary, safe and efficient multithreaded code is never easy.
- rwmj 15y ago
  Unlikely to happen. Reference counting has poor interaction with the CPU memory hierarchy: It makes all objects larger, making the working set correspondingly larger, meaning your data cache is less effective. It makes code larger because of the extra ref counting twiddling code. Larger code means a less effective instruction cache, as well as being slower because of all the extra operations performed. Reference counts must be frequently modified, and they are scattered all over memory (next to each object), so you get poorer locality and more atomic writes which has all sorts of negative implications for cache-coherent SMP architectures. So while you may not notice the penalty of reference counting since it is spread out over every operation, it's unlikely that it is better than proper GC for most applications. Maybe just for ones which are extremely sensitive to latency, yet don't mind running much slower overall (hard real time? aeronautics and space?). As usual you'd need to measure it.
bitops 15y ago
A very good writeup, but one thing always confuses me. What is meant specifically by the "heap" and "stack"? I know what a stack is, but "heap" gets thrown around in many different contexts and I've yet to find any explanation that made it clear. If anyone has a good explanation or good links for those two terms in this context, I'd be very grateful. Thanks! [EDIT: thanks everyone for the answers so far!]
- jws 15y ago
  Traditionally, the stack is a FILO (first in, last out) allocation area. Generally they start at the top of memory and work their way down as space is allocated, then back up as it is freed. The heap might start at the low end of unused memory (above the program and libraries) and is used for allocating space with arbitrary release order. This means it has to keep track of what is used and what is available as well as when to "grow the heap" by allocating more pages of memory. Garbage collection is one way of managing a heap.
- dons 15y ago
  In programming languages, generally: * Stack: "control stack" -- a structure that tracks the context of an evaluation "step" in the program * Heap: an environment that maps symbols to values (i.e a data structure that tracks the bindings of names to computations and results).
- faboo 15y ago
  Usually when people say "the heap" (especially in the context of garbage collection) they mean the memory where new (non-stack) data/objects are allocated from. Usually this is the bulk of memory an application uses. There are other meanings of the word "heap" in the realm of data structures, but I haven't personally seen "heap" the data structure talked about (or used) much in the wild.
  - anamax 15y ago
    > I haven't personally seen "heap" the data structure talked about (or used) much in the wild. Maybe not, but the concept of computing with addresses is reasonably common. That's why programming interviews often have some variation on heap sort or radix sort.
rubashov 15y ago
> The default choice of garbage collector in Hotspot is the throughput collector, which is ... entirely optimized for throughput I just want to confirm this is true? Say you're doing a long running simulation. You don't care about pauses at all. You just want it to finish fast. The default GC with no particular options is the way to go?
- gtani 15y ago
  Well, to not answer your question: Hotspot performance tuning is a fine art, and benchmarking is a somewhat separate fine art, people will sample their data carefully, do a lot fo runs, warming up properly, using different GC's, tuning heap,GC generations, MaxInlineSize, maybe 32-bit (-server). I remember reading linux package managers often don't include -client in the 64-bit install. JDK7 maybe faster, many people have said no difference between sun/Oracle and openJDK (except launcher and fonts, for IDEA, you must have sunjdk), and in some cases JRockit performs more predictably. Here's some blogs that i like about this: http://openjdk.java.net/groups/hotspot/docs/RuntimeOverview.html http://openjdk.java.net/groups/hotspot/docs/RuntimeOverview.... http://q-redux.blogspot.com/search/label/all%20jvm%20options http://q-redux.blogspot.com/search/label/all%20jvm%20options http://redstack.wordpress.com/2010/12/09/recommended-jvm-parameters-for-11g-products/ http://redstack.wordpress.com/2010/12/09/recommended-jvm-par... http://marxsoftware.blogspot.com/2011/10/javaone-2011-definitive-set-of-hotspot.html http://marxsoftware.blogspot.com/2011/10/javaone-2011-defini... http://blog.headius.com/2009/01/my-favorite-hotspot-jvm-flags.html http://blog.headius.com/2009/01/my-favorite-hotspot-jvm-flag... http://groups.google.com/group/jvm-languages/browse_thread/thread/2c10bde4b9985086?pli=1 http://groups.google.com/group/jvm-languages/browse_thread/t... http://stackoverflow.com/questions/tagged/java+hotspot?sort=newest&pagesize=50 http://stackoverflow.com/questions/tagged/java+hotspot?sort=...
- oconnor0 15y ago
  I'd say, odd are, that if you're just interested in throughput, the standard Hotspot GC without any options isn't going to give you optimal performance. I've found that, like gtani, mentions you'll have to spend time tuning to get the performance you want. In a similar situation, I found that the Parallel Old was, by far, the fastest (throughput) collector.
ruggeri 15y ago
I enjoyed this basic introduction to GC; upvoted. What I'd look forward is further discussion of incremental and concurrent GC algorithms. Until then, does anyone know what makes concurrent GC non-trivial? It seems like it shouldn't be too hard to trace concurrent to program execution. And if you don't compact, collection seems to just involve updating some structure tracking free blocks. I'd imagine it's possible to write a thread-safe version of that structure where every "free" request doesn't need to block every "malloc" request. But I must have missed something. I'd also be interested to read how compaction works; how are references remapped from the old address to the new one? Is it possible that a reference value is a pointer to a reference "object" which contains the pointer to data, which needs to be updated? Then you only need to update a single pointer when moving data, but every dereferene incurs an extra layer of indirection.
- dumael 15y ago
  Concurrent GC is somewhat non-trival as the mutator (i.e. the program you write) can delete references to objects from an area of the heap that has not been examined by the GC and introduce references to those same objects in an area that has been examined. This means those objects will be reclaimed since the GC never saw them. To cope with this the mutator is modified at compile/run time to inform the GC of object updates that could lead to this situation. During compaction of any sort, the first time an object is encountered that is to be moved it is copied somewhere else and the old copy's header is overwritten with it's forwarding address. Every time the GC encounters a reference to the old object, it re-writes the reference to the old object with it's new location (conveniently located in the old copy's header). > Is it possible that a reference value is a pointer to a reference "object" which contains the pointer to data, which needs to be updated? Look up something called 'Brook's style forwarding pointer', it is essentially what you've described.
  - ruggeri 15y ago
    Thanks; upvoted! I think I'm beginning to appreciate that concurrent marking is tougher than I thought; specifically, I can see how it can be hard to prove an object is unreachable. So I imagine the marking side is where the difficulties are. Your explanation for compaction makes perfect sense. Of course, this won't work trivially concurrently. Only if you stop the world can you complete examination of the entire live heap and know you've updated all references to the moved object and can collect the original space.
valyala 15y ago
While the article is interesting, it skips important things, which have high influence on practical GC speed - write barriers and finalizers. The following ancient article from Microsoft has better coverage of GC internals http://msdn.microsoft.com/en-us/library/ms973837.aspx http://msdn.microsoft.com/en-us/library/ms973837.aspx (somewhat biased to .NET :) ).

181 points by cgbystrom 15y ago

What are the long term implications of the increasing amount of parallel computing resources available to programmers? Are we getting to a point where there is enough excess CPU available, that the extra instruction on every assignment for reference counting is no big deal? (In certain contexts. In some contexts extra instructions are always a big deal, but these don't span all of computing.) Combine that with incremental algorithms for cycle reclamation, and you'd have great low-latency GC.

martincmartin 15y ago
The the object can be accessed (not modified, just accessed) from multiple threads, the extra instruction needs to be a thread safe atomic increment, which is hugely expensive, and becomes more expensive the more cores you have, especially in a NUMA architecture. Also, when an object is freed, you need to decrement the reference count of every single object it points to, even objects that are referenced from many other places and clearly won't be reclaimed for a long time.
larsberg 15y ago
It's still not trivial even with massive parallelism. Performance is easily killed if you: 1) Completely saturate the memory interconnect between the processors and RAM chips 2) If your parallel collector threads are touching the same memory that your worker threads are, you're going to have some cache contention 3) One of the big challenges with cache lines that have writes in them is if they are shared between processors. For example, create two ref cells and have two parallel threads set them -- if the compiler did not happen to pad them out to cache line size, they'll be fighting for the same 64 bytes (8 64-bit words/pointers) of memory We (Manticore) have done a lot of work to isolate the per-CPU work, heap pages, etc. (http://arxiv.org/abs/1105.2554 http://arxiv.org/abs/1105.2554 , MSPC 2011 proceedings should be out on acm.org soon-ish). But it's not easy and requires rearchitecting your whole compiler and runtime system. GHC is also in the middle of some similar work, and they have a much harder problem both due to the challenges of implementing laziness and they have a full-featured system and real user base, so they can't just change things willy-nilly. Further, once you get the parallelism right, you end up in a different situation: Amdahl's Law bites. Even if 90% of your program is amenable to parallel work, if you make that portion go infinitely fast, you still have a sequential portion that takes 10% of the time and therefore limits you to a maximum of 10x speedup. We are hitting that limitation right now in our research and going back to do more sequential performance work. I've got a small army of undergraduates implementing compiler optimizations and analyses :-)

pixie_ 15y ago

The complexity of generational garbage collection vs. the speed of manual collection, makes me feel like the happy medium of speed and simplicity is reference counting, like that found in objective-c. iPhone apps are fast, but take a bit longer to design, develop, and debug due to memory management issues. Though with experience these can be minimized. It probably isn't possible without a ton of modification, but I wish the JVM/CLR had an option to garbage collect through reference counting.

eru 15y ago
Reference counting is slower than proper garbage collection, since it adds an overhead for each access, instead of just during the collection. (There are ways to make reference counting faster, but they are no longer quite so simple.)
- benhoyt 15y ago
  It's not quite true to say reference counting adds overhead "for each access" -- for example, you can easily have a loop which accesses an object but doesn't modify the reference count. Reference counting adds overhead each time someone "expresses an ownership interest" in an object (wording from http://developer.apple.com/library/ios/#documentation/general/conceptual/devpedia-cocoacore/MemoryManagement.html http://developer.apple.com/library/ios/#documentation/genera...). (That's not to say your main point is false. I don't actually know which is faster in general.)
  - aardvark179 15y ago
    This is true, but has to be thought through very carefully in multithreaded environments where another thread might remove an object from a collection, causing it to be deleted while you're still looking at it. Safe looping then requires locks or cloning the collection (which is suddenly more expensive because it will hit all the contents' ref counts). In summary, safe and efficient multithreaded code is never easy.
rwmj 15y ago
Unlikely to happen. Reference counting has poor interaction with the CPU memory hierarchy: It makes all objects larger, making the working set correspondingly larger, meaning your data cache is less effective. It makes code larger because of the extra ref counting twiddling code. Larger code means a less effective instruction cache, as well as being slower because of all the extra operations performed. Reference counts must be frequently modified, and they are scattered all over memory (next to each object), so you get poorer locality and more atomic writes which has all sorts of negative implications for cache-coherent SMP architectures. So while you may not notice the penalty of reference counting since it is spread out over every operation, it's unlikely that it is better than proper GC for most applications. Maybe just for ones which are extremely sensitive to latency, yet don't mind running much slower overall (hard real time? aeronautics and space?). As usual you'd need to measure it.

bitops 15y ago

A very good writeup, but one thing always confuses me. What is meant specifically by the "heap" and "stack"? I know what a stack is, but "heap" gets thrown around in many different contexts and I've yet to find any explanation that made it clear. If anyone has a good explanation or good links for those two terms in this context, I'd be very grateful. Thanks! [EDIT: thanks everyone for the answers so far!]

jws 15y ago
Traditionally, the stack is a FILO (first in, last out) allocation area. Generally they start at the top of memory and work their way down as space is allocated, then back up as it is freed. The heap might start at the low end of unused memory (above the program and libraries) and is used for allocating space with arbitrary release order. This means it has to keep track of what is used and what is available as well as when to "grow the heap" by allocating more pages of memory. Garbage collection is one way of managing a heap.
dons 15y ago
In programming languages, generally: * Stack: "control stack" -- a structure that tracks the context of an evaluation "step" in the program * Heap: an environment that maps symbols to values (i.e a data structure that tracks the bindings of names to computations and results).
faboo 15y ago
Usually when people say "the heap" (especially in the context of garbage collection) they mean the memory where new (non-stack) data/objects are allocated from. Usually this is the bulk of memory an application uses. There are other meanings of the word "heap" in the realm of data structures, but I haven't personally seen "heap" the data structure talked about (or used) much in the wild.
- anamax 15y ago
  > I haven't personally seen "heap" the data structure talked about (or used) much in the wild. Maybe not, but the concept of computing with addresses is reasonably common. That's why programming interviews often have some variation on heap sort or radix sort.

rubashov 15y ago

> The default choice of garbage collector in Hotspot is the throughput collector, which is ... entirely optimized for throughput I just want to confirm this is true? Say you're doing a long running simulation. You don't care about pauses at all. You just want it to finish fast. The default GC with no particular options is the way to go?

gtani 15y ago
Well, to not answer your question: Hotspot performance tuning is a fine art, and benchmarking is a somewhat separate fine art, people will sample their data carefully, do a lot fo runs, warming up properly, using different GC's, tuning heap,GC generations, MaxInlineSize, maybe 32-bit (-server). I remember reading linux package managers often don't include -client in the 64-bit install. JDK7 maybe faster, many people have said no difference between sun/Oracle and openJDK (except launcher and fonts, for IDEA, you must have sunjdk), and in some cases JRockit performs more predictably. Here's some blogs that i like about this: http://openjdk.java.net/groups/hotspot/docs/RuntimeOverview.html http://openjdk.java.net/groups/hotspot/docs/RuntimeOverview.... http://q-redux.blogspot.com/search/label/all%20jvm%20options http://q-redux.blogspot.com/search/label/all%20jvm%20options http://redstack.wordpress.com/2010/12/09/recommended-jvm-parameters-for-11g-products/ http://redstack.wordpress.com/2010/12/09/recommended-jvm-par... http://marxsoftware.blogspot.com/2011/10/javaone-2011-definitive-set-of-hotspot.html http://marxsoftware.blogspot.com/2011/10/javaone-2011-defini... http://blog.headius.com/2009/01/my-favorite-hotspot-jvm-flags.html http://blog.headius.com/2009/01/my-favorite-hotspot-jvm-flag... http://groups.google.com/group/jvm-languages/browse_thread/thread/2c10bde4b9985086?pli=1 http://groups.google.com/group/jvm-languages/browse_thread/t... http://stackoverflow.com/questions/tagged/java+hotspot?sort=newest&pagesize=50 http://stackoverflow.com/questions/tagged/java+hotspot?sort=...
oconnor0 15y ago
I'd say, odd are, that if you're just interested in throughput, the standard Hotspot GC without any options isn't going to give you optimal performance. I've found that, like gtani, mentions you'll have to spend time tuning to get the performance you want. In a similar situation, I found that the Parallel Old was, by far, the fastest (throughput) collector.

ruggeri 15y ago

I enjoyed this basic introduction to GC; upvoted. What I'd look forward is further discussion of incremental and concurrent GC algorithms. Until then, does anyone know what makes concurrent GC non-trivial? It seems like it shouldn't be too hard to trace concurrent to program execution. And if you don't compact, collection seems to just involve updating some structure tracking free blocks. I'd imagine it's possible to write a thread-safe version of that structure where every "free" request doesn't need to block every "malloc" request. But I must have missed something. I'd also be interested to read how compaction works; how are references remapped from the old address to the new one? Is it possible that a reference value is a pointer to a reference "object" which contains the pointer to data, which needs to be updated? Then you only need to update a single pointer when moving data, but every dereferene incurs an extra layer of indirection.

dumael 15y ago
Concurrent GC is somewhat non-trival as the mutator (i.e. the program you write) can delete references to objects from an area of the heap that has not been examined by the GC and introduce references to those same objects in an area that has been examined. This means those objects will be reclaimed since the GC never saw them. To cope with this the mutator is modified at compile/run time to inform the GC of object updates that could lead to this situation. During compaction of any sort, the first time an object is encountered that is to be moved it is copied somewhere else and the old copy's header is overwritten with it's forwarding address. Every time the GC encounters a reference to the old object, it re-writes the reference to the old object with it's new location (conveniently located in the old copy's header). > Is it possible that a reference value is a pointer to a reference "object" which contains the pointer to data, which needs to be updated? Look up something called 'Brook's style forwarding pointer', it is essentially what you've described.
- ruggeri 15y ago
  Thanks; upvoted! I think I'm beginning to appreciate that concurrent marking is tougher than I thought; specifically, I can see how it can be hard to prove an object is unreachable. So I imagine the marking side is where the difficulties are. Your explanation for compaction makes perfect sense. Of course, this won't work trivially concurrently. Only if you stop the world can you complete examination of the entire live heap and know you've updated all references to the moved object and can collect the original space.

valyala 15y ago

While the article is interesting, it skips important things, which have high influence on practical GC speed - write barriers and finalizers. The following ancient article from Microsoft has better coverage of GC internals http://msdn.microsoft.com/en-us/library/ms973837.aspx http://msdn.microsoft.com/en-us/library/ms973837.aspx (somewhat biased to .NET :) ).