I've never understood why anyone would use a conservative collector outside toy programs or academia. It is hard enough to make programs deterministic even with precise collection. I can't even imagine releasing software that was inherently non-deterministic and could suddenly, and without notice, start retaining memory (even if atypical in practice). Thus, IMHO, which is faster is a moot point.
The same argument would apply to any non-compacting allocator, because the worst case memory blowup due to external fragmentation is huge. But such cases are extremely rarely observed in practice, so people use e.g. standard malloc()/free() implementations or non-compacting garbage collectors without being concerned about that.
In addition, there are plenty of cases where memory usage is unbounded or excessive, not because of allocator behavior, but because of programming mistakes. In fact, memory can sometimes blow up just because of large user inputs and very few systems are prepared for properly handling OOM conditions that happen legitimately.
Case in point: Both CRuby and Apple's JavaScriptCore have garbage collectors that use conservative stack scanning and are widely used in production systems without the world ending.
That said, you're probably not going to use conservative stack scanning because of collection speed alone. There are other trade-offs between conservative stack scanning and precise stack scanning that weigh more heavily.
I'll add the caveat that I would be very cautious about using a conservative GC on 32-bit systems, but on 64-bit systems this is about as much of a concern as memory fragmentation.
But such cases are extremely rarely observed in practice
After long years of finding problems and trying to encourage, pressure, bribe, cajole and finally yell at people about said problems, my professional opinion is that people aren’t very observant, and either do not see problems or pretend not to see them.
They just reboot the process every 48 hours and walk away.
And sadly continuous deployment is making this worse. The collective We have problems that only show up on three or four day weekends, right when you don’t want to be on call.
Unless you have deterministic threading no parallel GC will be deterministic. A lot of software has used the Boehm collector without issue, like inkscape and I believe crystal lang.
It is not sexy, and it has other issues, but it has worked for a long time.
The counterpoint here is that a if your program uses 2gb of memory on a 64bit computer, only 1 in 4 billion random 64 bit values will be plausible addresses (and almost all of them will only pin small amounts of memory).
Less trivial considering that typically only the low ~47 bits of addresses are allowed to be non-zero; then again, values on the stack would still be full 64 bits and any non-zero bit in the top 17 immediately disqualifies it; then again, besides literally random 64-bit integers, ones not pushing up to the 64-bit limit are probably more likely anyway.
Another possibility would be two adjacent 32-bit ints merging; for a 2GB heap this'd require the high half hitting one of the two valid 1≤x≤32767 values (reasonably frequent range for general-purpose numbers) and the bottom one can be anything; though whether such packing can happen on-stack depends on codegen (and, to a lesser extent, the program, as one can just do "12345L<<32" and get a thing that has the 2 in 32767 (0.006%) chance of hitting the heap); but even then fitting a million of such on the stack only gives ~61 potential false roots, and for that to be significant some of those must hit massive objects (brings back some 1 in a billion factor unless there are large cyclic object subgraphs).
Depending on the processor architecture, you might be able to assume a minimum memory alignment and then immediately disqualify values whose least significant bits aren’t zero.
You probably can't if your programming language puts data in those bits (which is fairly commin since it's a very convenient place to store a couple bits of data for the GC).
Didn’t the opposite happen near the end of the 32 bit age? My take was that you could get away with conservative garbage collection if you had 16MB of RAM in a 32 bit address space but as you filled more of it the probability of a significant memory leak converged on 1.
I assume you mean 16 mb of ram in a 32 gb space, but yes. As app size approaches address space size, lots of things get worse.
That said this new generation of only conservatively sweeping the stack has the significant advantage that the stack has remained pretty small (8mb is still the standard stack size), so if you have precise heap scanning the odds of spurious collections from conservative scanning go down a ton.
Yeah... I can't imagine trying to debug that. "We kept getting memory leaks, so we dug into it and realized that the language was interpreting local integer variables as pointers and refusing to free memory, but this only happened sporadically and we couldn't reproduce the bug on our development machines. After banging our heads against the wall for weeks we realized what was going on, and it turns out this behavior is completely intentional and they have no plans to change it."
Computer programming is full of probabilistic edge cases with ridiculous costs that are amortized over normal use. Most optimization, encoding, and compression is based on statistics.
If your use case requires a minimum bound, use another algorithm.
Amortized analysis actually provides a guarantee (either deterministic or probabilistic) that things will tend to even out in the long run. Unless I misunderstand something, conservative GC provides no such guarantee, and there are no hard statistics behind the claim that memory leaks caused by it should be rare. There's a difference between "this algorithm is actually random and so sometimes will happen to exhibit suboptimal behavior" and "under the right circumstances, this garbage collection scheme will consistently produce memory leaks due to arcane rules, but those conditions are practically impossible to reproduce in a controlled setting."
Assuming that on-heap objects are tracked precisely, the maximum number of objects conservative stack scanning can incorrectly consider as roots is O(stack size) (with, in practice, a tiny constant factor, from excluding actual intentional references and frequently-changing or trivial non-reference values).
The only way for the total amount of leaked memory to grow is by replacing something else on the stack, which releases whatever was there before, and, assuming there's some maximum stack size, there's a finite amount of such space.
End result being that, even if you have some code path that generates an integer that looks like a reference, it can only leak one object (which could be massive perhaps, but with generational GC or similar there's no guarantee of all garbage being GC'd at any single GC anyway); if codegen clears stack slots upon their lifetime ending, you need one such integer-holding frame to be on the stack for every object you want to be leaked.
Many quick-sort implementations are deterministic, so will consistently have their worst case behavior on the same inputs again and again.
The good ones try to do a little better than choosing the center element as pivot, but with a well crafted input, it can easily become polynomial anyway.
Luckily sorting is something you can easily choose another implementation of, if the default over didn't fit your use-cade, unlike the GC built into the single language implementation that your customer uses.
I take it there are languages that are locked to a particular GC, and this is a point of pain and friction? A good garbage collected language would make automated memory management both optional and modular. I recall D having a GC that can be disabled?
I’ve never worked with a language that had a precise GC that wasn’t also a nightmare to run in production. Java’s the obvious example of a language with an unmanageable GC. (Yes, they’re claiming the next GC will work, but that was the top line feature in the 1.4 marketing back in the late 1990’s, and I simply don’t believe such claims after 25+ years and over a dozen major releases that failed to deliver it.
Go is supposedly a counterexample. I haven’t used it enough to offer an opinion, but I have heard of companies rewriting Go services simply to avoid GC at runtime.
This is such a weird take. Java's been everywhere in prod in the industry for decades from backends running millions of qps to HFT to game clients.
IME, the most common GC problems I see are:
- incredibly basic settings are wrong, like the max heap size
- the app was written with some very poor behavior, e.g. unreal amounts of allocation or tons of allocation thrashing in tenured heap.
There aren't even a lot of GCs knobs to "manage" anymore compared to a decade ago [0]. Don't treat your GC as a black-box machine with infinitely available resources, and you'll be fine.
Counterpoint: the problem with Java isn't the GC, but the language. If every struct you instantiated in C required a malloc/free, that would be really slow too.
Java's memory management doesn't work like malloc/free at all, and that's why it's fast [1]. Even disregarding scalar replacement that means many `new` don't allocate anything on the heap, nearly all allocations are a pointer bump and objects that die don't require some active deallocation. With tracing collectors it's keeping objects alive for a long time that requires some computational work, not deallocating them (as is the case with refcounting collectors).
An extremely simplified description of how OpenJDK's GCs work is like this: every allocation bumps the "heap end" pointer, and when memory runs out, the GC scans the objects reachable from some set of "roots", resets the allocation pointer to the start of the heap, and copies the live objects to the allocation pointer, bumping it along the way (and in the process, overwriting the dead objects). In practice, the scanning and the compaction may be done concurrently with the application, there is not just one allocation pointer (to avoid contention), and not the entire object graph needs to be scanned to free memory.
The cost of Java's good GC is virtually entirely in memory footprint (there may be some speed costs to GC in some cases, but they're offset by GC's speed benefits).
[1]: Java may indeed be slower than C on some workloads due to memory layout, but that's because of data locality, not GC. The upcoming inlined value objects will take care of that.
Comments
I've never understood why anyone would use a conservative collector outside toy programs or academia. It is hard enough to make programs deterministic even with precise collection. I can't even imagine releasing software that was inherently non-deterministic and could suddenly, and without notice, start retaining memory (even if atypical in practice). Thus, IMHO, which is faster is a moot point.
The same argument would apply to any non-compacting allocator, because the worst case memory blowup due to external fragmentation is huge. But such cases are extremely rarely observed in practice, so people use e.g. standard malloc()/free() implementations or non-compacting garbage collectors without being concerned about that.
In addition, there are plenty of cases where memory usage is unbounded or excessive, not because of allocator behavior, but because of programming mistakes. In fact, memory can sometimes blow up just because of large user inputs and very few systems are prepared for properly handling OOM conditions that happen legitimately.
Case in point: Both CRuby and Apple's JavaScriptCore have garbage collectors that use conservative stack scanning and are widely used in production systems without the world ending.
That said, you're probably not going to use conservative stack scanning because of collection speed alone. There are other trade-offs between conservative stack scanning and precise stack scanning that weigh more heavily.
I'll add the caveat that I would be very cautious about using a conservative GC on 32-bit systems, but on 64-bit systems this is about as much of a concern as memory fragmentation.
After long years of finding problems and trying to encourage, pressure, bribe, cajole and finally yell at people about said problems, my professional opinion is that people aren’t very observant, and either do not see problems or pretend not to see them.
They just reboot the process every 48 hours and walk away.
And sadly continuous deployment is making this worse. The collective We have problems that only show up on three or four day weekends, right when you don’t want to be on call.
Unless you have deterministic threading no parallel GC will be deterministic. A lot of software has used the Boehm collector without issue, like inkscape and I believe crystal lang.
It is not sexy, and it has other issues, but it has worked for a long time.
The counterpoint here is that a if your program uses 2gb of memory on a 64bit computer, only 1 in 4 billion random 64 bit values will be plausible addresses (and almost all of them will only pin small amounts of memory).
Less trivial considering that typically only the low ~47 bits of addresses are allowed to be non-zero; then again, values on the stack would still be full 64 bits and any non-zero bit in the top 17 immediately disqualifies it; then again, besides literally random 64-bit integers, ones not pushing up to the 64-bit limit are probably more likely anyway.
Another possibility would be two adjacent 32-bit ints merging; for a 2GB heap this'd require the high half hitting one of the two valid 1≤x≤32767 values (reasonably frequent range for general-purpose numbers) and the bottom one can be anything; though whether such packing can happen on-stack depends on codegen (and, to a lesser extent, the program, as one can just do "12345L<<32" and get a thing that has the 2 in 32767 (0.006%) chance of hitting the heap); but even then fitting a million of such on the stack only gives ~61 potential false roots, and for that to be significant some of those must hit massive objects (brings back some 1 in a billion factor unless there are large cyclic object subgraphs).
Depending on the processor architecture, you might be able to assume a minimum memory alignment and then immediately disqualify values whose least significant bits aren’t zero.
You probably can't if your programming language puts data in those bits (which is fairly commin since it's a very convenient place to store a couple bits of data for the GC).
Didn’t the opposite happen near the end of the 32 bit age? My take was that you could get away with conservative garbage collection if you had 16MB of RAM in a 32 bit address space but as you filled more of it the probability of a significant memory leak converged on 1.
I assume you mean 16 mb of ram in a 32 gb space, but yes. As app size approaches address space size, lots of things get worse.
That said this new generation of only conservatively sweeping the stack has the significant advantage that the stack has remained pretty small (8mb is still the standard stack size), so if you have precise heap scanning the odds of spurious collections from conservative scanning go down a ton.
I corrected GB -> MB in my post, thanks!
That's only true if the valid addresses or values are uniformly distributed, which is not the case.
The article suggests this might be used for JavaScript VMs maybe the lack of int64s in the language helps?
Yeah... I can't imagine trying to debug that. "We kept getting memory leaks, so we dug into it and realized that the language was interpreting local integer variables as pointers and refusing to free memory, but this only happened sporadically and we couldn't reproduce the bug on our development machines. After banging our heads against the wall for weeks we realized what was going on, and it turns out this behavior is completely intentional and they have no plans to change it."
Computer programming is full of probabilistic edge cases with ridiculous costs that are amortized over normal use. Most optimization, encoding, and compression is based on statistics.
If your use case requires a minimum bound, use another algorithm.
Amortized analysis actually provides a guarantee (either deterministic or probabilistic) that things will tend to even out in the long run. Unless I misunderstand something, conservative GC provides no such guarantee, and there are no hard statistics behind the claim that memory leaks caused by it should be rare. There's a difference between "this algorithm is actually random and so sometimes will happen to exhibit suboptimal behavior" and "under the right circumstances, this garbage collection scheme will consistently produce memory leaks due to arcane rules, but those conditions are practically impossible to reproduce in a controlled setting."
Assuming that on-heap objects are tracked precisely, the maximum number of objects conservative stack scanning can incorrectly consider as roots is O(stack size) (with, in practice, a tiny constant factor, from excluding actual intentional references and frequently-changing or trivial non-reference values).
The only way for the total amount of leaked memory to grow is by replacing something else on the stack, which releases whatever was there before, and, assuming there's some maximum stack size, there's a finite amount of such space.
End result being that, even if you have some code path that generates an integer that looks like a reference, it can only leak one object (which could be massive perhaps, but with generational GC or similar there's no guarantee of all garbage being GC'd at any single GC anyway); if codegen clears stack slots upon their lifetime ending, you need one such integer-holding frame to be on the stack for every object you want to be leaked.
Many quick-sort implementations are deterministic, so will consistently have their worst case behavior on the same inputs again and again. The good ones try to do a little better than choosing the center element as pivot, but with a well crafted input, it can easily become polynomial anyway.
Luckily sorting is something you can easily choose another implementation of, if the default over didn't fit your use-cade, unlike the GC built into the single language implementation that your customer uses.
I take it there are languages that are locked to a particular GC, and this is a point of pain and friction? A good garbage collected language would make automated memory management both optional and modular. I recall D having a GC that can be disabled?
Yeah, but we're talking about memory leaks not some branch misprediction or cache miss.
You're thinking in terms of space, now consider the same concept in the dimension of time.
Branch misprediction is a permanent loss. You will never get those nanoseconds back.
Yes, you have to wait longer.
Space inefficiencies require you to install more memory.
If you exhaust memory, it gets paged to disk, increasing access latency. I.e. You have to wait longer.
I’ve never worked with a language that had a precise GC that wasn’t also a nightmare to run in production. Java’s the obvious example of a language with an unmanageable GC. (Yes, they’re claiming the next GC will work, but that was the top line feature in the 1.4 marketing back in the late 1990’s, and I simply don’t believe such claims after 25+ years and over a dozen major releases that failed to deliver it.
Go is supposedly a counterexample. I haven’t used it enough to offer an opinion, but I have heard of companies rewriting Go services simply to avoid GC at runtime.
This is such a weird take. Java's been everywhere in prod in the industry for decades from backends running millions of qps to HFT to game clients.
IME, the most common GC problems I see are:
There aren't even a lot of GCs knobs to "manage" anymore compared to a decade ago [0]. Don't treat your GC as a black-box machine with infinitely available resources, and you'll be fine.0) https://docs.oracle.com/en/java/javase/22/gctuning/ergonomic...
https://netflixtechblog.com/bending-pause-times-to-your-will...
Counterpoint: the problem with Java isn't the GC, but the language. If every struct you instantiated in C required a malloc/free, that would be really slow too.
Java's memory management doesn't work like malloc/free at all, and that's why it's fast [1]. Even disregarding scalar replacement that means many `new` don't allocate anything on the heap, nearly all allocations are a pointer bump and objects that die don't require some active deallocation. With tracing collectors it's keeping objects alive for a long time that requires some computational work, not deallocating them (as is the case with refcounting collectors).
An extremely simplified description of how OpenJDK's GCs work is like this: every allocation bumps the "heap end" pointer, and when memory runs out, the GC scans the objects reachable from some set of "roots", resets the allocation pointer to the start of the heap, and copies the live objects to the allocation pointer, bumping it along the way (and in the process, overwriting the dead objects). In practice, the scanning and the compaction may be done concurrently with the application, there is not just one allocation pointer (to avoid contention), and not the entire object graph needs to be scanned to free memory.
The cost of Java's good GC is virtually entirely in memory footprint (there may be some speed costs to GC in some cases, but they're offset by GC's speed benefits).
[1]: Java may indeed be slower than C on some workloads due to memory layout, but that's because of data locality, not GC. The upcoming inlined value objects will take care of that.