7 ms·

Conservative GC: Is It Really That Bad?

85 points by dleskov 9y ago

willvarfar 9y ago
This is just off the top of my head, but it made me wonder: are there any VMs that put a stack map header of some sort as a literal in the stack? E.g. for each frame the compiler orders roots first and then other primitives. Then, as you enter the frame, write the number of roots to the stack. When the GC walks the stack it can see precisely which are roots.
- anon1851968 9y ago
  That could be done, but generally precise collectors keep a fixed set of tables outside the stack, that way they only need to figure out which method frames are on the stack and then consult those tables. That incurs fewer writes.
- dbg_nsk 9y ago
  The problem is that it all depends on the liveness of the variables. The same value on the stack can be a root at the begining of the method as the corresponding variable is still alive, and later it becomes useless as the variable is already dead. So, you still need to know a location of each live reference at every safepoint (and that means several stack-maps for each method).
  - willvarfar 9y ago
    You can zero them when they are not live.
    - dbg_nsk 9y ago
      Yeah, we've tried that. It was one of the attempts of improving conservative GC (no dead values on the stack => no false roots). Unfortunately, it causes noticeable performance degradation, so it is easier to consult with stack maps about liveness of the variable.
- barrkel 9y ago
  It can be done. In fact something very close to that is done in the Delphi compiler. Delphi has a variety of reference counted types. Originally just strings, but later dynamic arrays and COM-style interfaces, all use automatic reference counting. Assignment and copying of these types are done via runtime calls, not just for variables of these types, but also structures and static arrays, recursively, that contain these types. When allocating locals of these types, and of types that contain these types, the compiler also writes out an RTTI structure describing the stack layout, a bit like the activation record was an actual Pascal record. This RTTI is used to correctly decrement references when the stack is popped in normal case, or during exception unwinding. The RTTI scheme is smart enough to encode several variables of the same type as being like a static array of that type, etc. All this doesn't help with liveness, of course, which will still be a problem for the code presented in the article. In fact the efficiency of the encoding is in direct opposition to liveness; encoding things as contiguous blocks of pointers will most likely artificially extend their lifetime to the whole call frame.
- munificent 9y ago
  The paper "Accurate Garbage Collection in an Uncooperative Environment" goes over a very roughly similar technique for compiling a GC language to C in a way that lets you easily find the roots because managed objects are stuffed in structs on the C stack in a certain way. It's a really really neat paper that I've been itching to implement for a while.
- Garfgon 9y ago
  Could you use debug information for this? I think the stack frame layout should already be included there.
barrkel 9y ago
The problematic code in the article is, AFAICT, using an object finalizer to free manually allocated memory; such approaches seldom work well, even with precise GCs. Thread stacks are effectively manually allocated blocks of memory. You create a thread, which allocates the stack, and as long as the thread lives, the stack is kept alive - it's self-sustaining. The thread must die by explicit programmatic action, which in turn will free its allocated block of stack memory. Using finalizers at all is usually an anti-pattern in a GC world. The presence of finalizers is a very strong hint that the GC is being used to manage resources other than memory, something that GC is a poor fit for, because other resources almost certainly have no necessary correlation with memory pressure; and GCs usually only monitor GC heap memory pressure. That's not to say that there aren't plenty of edge cases where you can end up with lots of false roots that artificially lengthen object lifetimes with a conservative GC. Putting a thread stack in your cycle of object references and relying on GC pressure to break the cycle isn't a strongly motivating one to my mind, though.
- dbg_nsk 9y ago
  Absolutely agree with you about finalizers! However, please note that this "threadReaper" code is from JDK class, so, the problem can appear on every application that just use Timer class. Of course, there are many other examples of false-roots, but this concrete class caused unexpected OOMs on several applications of our clients, so we made this small sample and used it for sanity checking during implementing precise GC (and then mentioned it in the post).
  - barrkel 9y ago
    I didn't know it was from the JDK, interesting.
  - yxhuvud 9y ago
    I take it you are part of the ones behind the article? Did you ever see the papers about a conservative variant of immix, which would be both compacting and conservative?
    - 9y ago
dmytrish 9y ago
I am not an expert in garbage collection techniques, but this article does not even mention locality of reference (copying GCs improve locality on each compaction) and how many cache misses are introduced by increased fragmentation. Are there any benchmarks on this?
- dbg_nsk 9y ago
  Yes, an excellent point. Unfortunately, we do not have such specific benchmarks at the moment (only general benchmarks on the performance of GC), but I guess we should add them. However, please note, that our conservative GC was also copying (but not full copying) collector, and it also improved locality of references. So an impact on the performance is not so huge as in the case of GC that doesn't provide any compaction at all.
- munificent 9y ago
  I'm no expert either, but some of the literature I've read says that copying GCs aren't a panacea when it comes to improving locality. For some object graphs, they help, for others they actually reorder the objects in ways that make locality worse. Consider, for example, a copying GC that copies using a depth-first traversal of the object graph and then running it over a tree that your program always processes in breadth-first order.
- aidenn0 9y ago
  On SBCL the bigger win for using a copying collector isn't the locality of reference (which helps with some loads, but hurts with others), but rather the fact that you can make an allocation be about two instructions in the non-GC case (pointer increment plus a bounds check). I hadn't spent a lot of time thinking about how much faster this is than malloc/free until a question came up the other day here on HN to the extent of "why would anyone dynamically allocate an object that is smaller than a cache line?" In lisp a commonly allocated structure is a CONS cell which is two pointers in size, and is often smaller than the cache line. It would be very wasteful to do a malloc/free of 8 (or 16) bytes, in C but throughput is approximately identical compared to stack allocating them with SBCLs allocator.
  - 9y ago
naasking 9y ago
Conservative GC would probably work well enough for the JVM because there are no value types or inline arrays which more easily masquerade as roots, ie. a random sequence of bytes as used in crypto or hashing would yield a lot of false positives. By comparison, the CLR is a much worse fit, because value types and stack/inline/fixed arrays means false positives would be much higher for some applications.
- dbg_nsk 9y ago
  You are right, such things as value types or inline arrays are not introduced in Java language (yet), but still JVM can allocate objects including arrays on the stack if this objects are not escaping into the heap. Of course, not all objects fit this condition, but the problem remains.
jacksmith21006 9y ago
This is something that I just love about Go. Get rid of the GC stalling like you have with Java.
- abollaert 9y ago
  Has been discussed before. https://blog.plan99.net/modern-garbage-collection-911ef4f8bd8e https://blog.plan99.net/modern-garbage-collection-911ef4f8bd... https://news.ycombinator.com/item?id=13218550 https://news.ycombinator.com/item?id=13218550
- imtringued 9y ago
  The primary difference is that Go creates less garbage than Java. Of course this results in significantly shorter GC pauses but they still exist.
le-mark 9y ago
So does this analysis extend to libgc/Boehms gc, since it's conservative as well?
aidenn0 9y ago
Interestingly enough, SBCL on x86/x64 has a conservative, but moving, GC. It can know some, but not all roots precisely, so it pins any objects that are reachable through conservative roots. It's earlier implementations were on RISC chips that had 24 or more GPRs so the implementation was simple: 2 stacks and divide the local registers in half for boxed and unboxed values. This obviously didn't work when porting to x86 which had far fewer registers. The ARM port I believe uses the non-conservative approach, despite having 1 less register than x64 (the x64 port was derived from the x86 port so uses the same register assignments).
- rwmj 9y ago
  > divide the local registers in half for boxed and unboxed values Fondly remembers the separate address and data registers on 68000. Why didn't they go back to this approach for x86_64 (16 registers), now that no one really cares about 32 bit x86?
  - aidenn0 9y ago
    The conservative GC approach has worked well enough in practice that nobody is going to do the work. Also there is a performance tradeoff in non-allocating code: Sometimes you need more unboxed registers, other times you need more boxed registers so with only ~6 of each[1] you will run into register pressure. 1: 2 stacks means 2 stack pointers and 2 frame pointers leaving only 12 registers left for values; it's also possible that the SBCL ABI uses a global register for something else as well, which would leave only 11. PowerPC is a really luxurious platform in which you have 32 GPRs so even if you use 8 GPRs for various bookkeeping purposes that leaves 24 remaining, which is enough for pretty much everyone.
- dmm 9y ago
  FWIW Clozure CL has a precise gc on x86/x64. The register usage is detailed here: https://ccl.clozure.com/docs/ccl.html#register-and-stack-usage-conventions https://ccl.clozure.com/docs/ccl.html#register-and-stack-usa...
SteveJS 9y ago
The Chakra Javascript engine uses a conservative generational mark and sweep collector with many phases running in parallel to code execution. It looks like Chakra is now on github (and with an MIT license). In chakra the GC is called it a 'Recycler', which can throw one for a loop when searching for the GC implementation.
PaulHoule 9y ago
The pain from conservative GC depends on how much your address space you are using. In the 32-bit age, you ran into problems more and more as your heap approaches the GB range. At some point the probability that you end up with a false root that keeps a lot of garbage alive goes to 1. In the 64-bit age we get a respite, although many systems don't really use 64-bit pointers.
kazinator 9y ago
A useful hybrid is possible and useful in some circumstances: conservative scan for roots, which point into a precisely traced heap.
bjourne 9y ago
A safepoint in x86 is nothing more than the instruction mov [rip+0x1234], eax. That shouldn't cause a major slowdown? Also, safepoints are useful for features other than gc. For example, you can inspect a running thread's callstack. That is useful when debugging and when objectifying a thread's state. Stack maps can be made a bit smaller by pushing and popping all registers from the stack during gc. That way, you only need to store the values of stack locations in them and not of individual registers. Btw, the article is really good. This is the kind of stuff I keep coming back to HN for!
- dbg_nsk 9y ago
  Right, but even a single instruction placed on every backward branch and at the epilogue of every method causes noticeable impact on the performance. This is especially important in highly optimized code and that's why optimizing compilers like HotSpot C2 (and JET as well) try to remove as many safepoints as possible. Sometimes it even causes troubles like in this case: https://bugs.openjdk.java.net/browse/JDK-5014723 https://bugs.openjdk.java.net/browse/JDK-5014723 Good point about inspecting thread's callstack. Indeed, with conservative GC we had a problem: many popular profilers were incompatible with JET because they inspect threads at safepoints and we had none. When we implemented the precise GC, this problem disappeared and it was an additional benefit for us. However, there are alternative ways to gather thread's callstack out of safepoint. We use them to avoid safepoint bias in our profiler. You can read more about it here: https://www.excelsiorjet.com/blog/articles/portable-profilers-and-where-to-find-them/ https://www.excelsiorjet.com/blog/articles/portable-profiler... ---- Thanks for kind words! I'm glad that you liked the post!

85 points by dleskov 9y ago

This is just off the top of my head, but it made me wonder: are there any VMs that put a stack map header of some sort as a literal in the stack? E.g. for each frame the compiler orders roots first and then other primitives. Then, as you enter the frame, write the number of roots to the stack. When the GC walks the stack it can see precisely which are roots.

anon1851968 9y ago
That could be done, but generally precise collectors keep a fixed set of tables outside the stack, that way they only need to figure out which method frames are on the stack and then consult those tables. That incurs fewer writes.
dbg_nsk 9y ago
The problem is that it all depends on the liveness of the variables. The same value on the stack can be a root at the begining of the method as the corresponding variable is still alive, and later it becomes useless as the variable is already dead. So, you still need to know a location of each live reference at every safepoint (and that means several stack-maps for each method).
- willvarfar 9y ago
  You can zero them when they are not live.
  - dbg_nsk 9y ago
    Yeah, we've tried that. It was one of the attempts of improving conservative GC (no dead values on the stack => no false roots). Unfortunately, it causes noticeable performance degradation, so it is easier to consult with stack maps about liveness of the variable.
barrkel 9y ago
It can be done. In fact something very close to that is done in the Delphi compiler. Delphi has a variety of reference counted types. Originally just strings, but later dynamic arrays and COM-style interfaces, all use automatic reference counting. Assignment and copying of these types are done via runtime calls, not just for variables of these types, but also structures and static arrays, recursively, that contain these types. When allocating locals of these types, and of types that contain these types, the compiler also writes out an RTTI structure describing the stack layout, a bit like the activation record was an actual Pascal record. This RTTI is used to correctly decrement references when the stack is popped in normal case, or during exception unwinding. The RTTI scheme is smart enough to encode several variables of the same type as being like a static array of that type, etc. All this doesn't help with liveness, of course, which will still be a problem for the code presented in the article. In fact the efficiency of the encoding is in direct opposition to liveness; encoding things as contiguous blocks of pointers will most likely artificially extend their lifetime to the whole call frame.
munificent 9y ago
The paper "Accurate Garbage Collection in an Uncooperative Environment" goes over a very roughly similar technique for compiling a GC language to C in a way that lets you easily find the roots because managed objects are stuffed in structs on the C stack in a certain way. It's a really really neat paper that I've been itching to implement for a while.
Garfgon 9y ago
Could you use debug information for this? I think the stack frame layout should already be included there.

barrkel 9y ago

The problematic code in the article is, AFAICT, using an object finalizer to free manually allocated memory; such approaches seldom work well, even with precise GCs. Thread stacks are effectively manually allocated blocks of memory. You create a thread, which allocates the stack, and as long as the thread lives, the stack is kept alive - it's self-sustaining. The thread must die by explicit programmatic action, which in turn will free its allocated block of stack memory. Using finalizers at all is usually an anti-pattern in a GC world. The presence of finalizers is a very strong hint that the GC is being used to manage resources other than memory, something that GC is a poor fit for, because other resources almost certainly have no necessary correlation with memory pressure; and GCs usually only monitor GC heap memory pressure. That's not to say that there aren't plenty of edge cases where you can end up with lots of false roots that artificially lengthen object lifetimes with a conservative GC. Putting a thread stack in your cycle of object references and relying on GC pressure to break the cycle isn't a strongly motivating one to my mind, though.

dbg_nsk 9y ago
Absolutely agree with you about finalizers! However, please note that this "threadReaper" code is from JDK class, so, the problem can appear on every application that just use Timer class. Of course, there are many other examples of false-roots, but this concrete class caused unexpected OOMs on several applications of our clients, so we made this small sample and used it for sanity checking during implementing precise GC (and then mentioned it in the post).
- barrkel 9y ago
  I didn't know it was from the JDK, interesting.
- yxhuvud 9y ago
  I take it you are part of the ones behind the article? Did you ever see the papers about a conservative variant of immix, which would be both compacting and conservative?
  - 9y ago

dmytrish 9y ago

I am not an expert in garbage collection techniques, but this article does not even mention locality of reference (copying GCs improve locality on each compaction) and how many cache misses are introduced by increased fragmentation. Are there any benchmarks on this?

dbg_nsk 9y ago
Yes, an excellent point. Unfortunately, we do not have such specific benchmarks at the moment (only general benchmarks on the performance of GC), but I guess we should add them. However, please note, that our conservative GC was also copying (but not full copying) collector, and it also improved locality of references. So an impact on the performance is not so huge as in the case of GC that doesn't provide any compaction at all.
munificent 9y ago
I'm no expert either, but some of the literature I've read says that copying GCs aren't a panacea when it comes to improving locality. For some object graphs, they help, for others they actually reorder the objects in ways that make locality worse. Consider, for example, a copying GC that copies using a depth-first traversal of the object graph and then running it over a tree that your program always processes in breadth-first order.
aidenn0 9y ago
On SBCL the bigger win for using a copying collector isn't the locality of reference (which helps with some loads, but hurts with others), but rather the fact that you can make an allocation be about two instructions in the non-GC case (pointer increment plus a bounds check). I hadn't spent a lot of time thinking about how much faster this is than malloc/free until a question came up the other day here on HN to the extent of "why would anyone dynamically allocate an object that is smaller than a cache line?" In lisp a commonly allocated structure is a CONS cell which is two pointers in size, and is often smaller than the cache line. It would be very wasteful to do a malloc/free of 8 (or 16) bytes, in C but throughput is approximately identical compared to stack allocating them with SBCLs allocator.
- 9y ago

naasking 9y ago

Conservative GC would probably work well enough for the JVM because there are no value types or inline arrays which more easily masquerade as roots, ie. a random sequence of bytes as used in crypto or hashing would yield a lot of false positives. By comparison, the CLR is a much worse fit, because value types and stack/inline/fixed arrays means false positives would be much higher for some applications.

dbg_nsk 9y ago
You are right, such things as value types or inline arrays are not introduced in Java language (yet), but still JVM can allocate objects including arrays on the stack if this objects are not escaping into the heap. Of course, not all objects fit this condition, but the problem remains.

jacksmith21006 9y ago

This is something that I just love about Go. Get rid of the GC stalling like you have with Java.

abollaert 9y ago
Has been discussed before. https://blog.plan99.net/modern-garbage-collection-911ef4f8bd8e https://blog.plan99.net/modern-garbage-collection-911ef4f8bd... https://news.ycombinator.com/item?id=13218550 https://news.ycombinator.com/item?id=13218550
imtringued 9y ago
The primary difference is that Go creates less garbage than Java. Of course this results in significantly shorter GC pauses but they still exist.

le-mark 9y ago

So does this analysis extend to libgc/Boehms gc, since it's conservative as well?

aidenn0 9y ago

Interestingly enough, SBCL on x86/x64 has a conservative, but moving, GC. It can know some, but not all roots precisely, so it pins any objects that are reachable through conservative roots. It's earlier implementations were on RISC chips that had 24 or more GPRs so the implementation was simple: 2 stacks and divide the local registers in half for boxed and unboxed values. This obviously didn't work when porting to x86 which had far fewer registers. The ARM port I believe uses the non-conservative approach, despite having 1 less register than x64 (the x64 port was derived from the x86 port so uses the same register assignments).

rwmj 9y ago
> divide the local registers in half for boxed and unboxed values Fondly remembers the separate address and data registers on 68000. Why didn't they go back to this approach for x86_64 (16 registers), now that no one really cares about 32 bit x86?
- aidenn0 9y ago
  The conservative GC approach has worked well enough in practice that nobody is going to do the work. Also there is a performance tradeoff in non-allocating code: Sometimes you need more unboxed registers, other times you need more boxed registers so with only ~6 of each[1] you will run into register pressure. 1: 2 stacks means 2 stack pointers and 2 frame pointers leaving only 12 registers left for values; it's also possible that the SBCL ABI uses a global register for something else as well, which would leave only 11. PowerPC is a really luxurious platform in which you have 32 GPRs so even if you use 8 GPRs for various bookkeeping purposes that leaves 24 remaining, which is enough for pretty much everyone.
dmm 9y ago
FWIW Clozure CL has a precise gc on x86/x64. The register usage is detailed here: https://ccl.clozure.com/docs/ccl.html#register-and-stack-usage-conventions https://ccl.clozure.com/docs/ccl.html#register-and-stack-usa...

SteveJS 9y ago

The Chakra Javascript engine uses a conservative generational mark and sweep collector with many phases running in parallel to code execution. It looks like Chakra is now on github (and with an MIT license). In chakra the GC is called it a 'Recycler', which can throw one for a loop when searching for the GC implementation.

PaulHoule 9y ago

The pain from conservative GC depends on how much your address space you are using. In the 32-bit age, you ran into problems more and more as your heap approaches the GB range. At some point the probability that you end up with a false root that keeps a lot of garbage alive goes to 1. In the 64-bit age we get a respite, although many systems don't really use 64-bit pointers.

kazinator 9y ago

A useful hybrid is possible and useful in some circumstances: conservative scan for roots, which point into a precisely traced heap.

bjourne 9y ago

A safepoint in x86 is nothing more than the instruction mov [rip+0x1234], eax. That shouldn't cause a major slowdown? Also, safepoints are useful for features other than gc. For example, you can inspect a running thread's callstack. That is useful when debugging and when objectifying a thread's state. Stack maps can be made a bit smaller by pushing and popping all registers from the stack during gc. That way, you only need to store the values of stack locations in them and not of individual registers. Btw, the article is really good. This is the kind of stuff I keep coming back to HN for!

dbg_nsk 9y ago
Right, but even a single instruction placed on every backward branch and at the epilogue of every method causes noticeable impact on the performance. This is especially important in highly optimized code and that's why optimizing compilers like HotSpot C2 (and JET as well) try to remove as many safepoints as possible. Sometimes it even causes troubles like in this case: https://bugs.openjdk.java.net/browse/JDK-5014723 https://bugs.openjdk.java.net/browse/JDK-5014723 Good point about inspecting thread's callstack. Indeed, with conservative GC we had a problem: many popular profilers were incompatible with JET because they inspect threads at safepoints and we had none. When we implemented the precise GC, this problem disappeared and it was an additional benefit for us. However, there are alternative ways to gather thread's callstack out of safepoint. We use them to avoid safepoint bias in our profiler. You can read more about it here: https://www.excelsiorjet.com/blog/articles/portable-profilers-and-where-to-find-them/ https://www.excelsiorjet.com/blog/articles/portable-profiler... ---- Thanks for kind words! I'm glad that you liked the post!