Crazy to me that garbage collection systems are a subject of continual evolution and discussion. You'd think it would be "solved" by now... Or is that just in Java world?
As somebody says elsewhere, it's multidimensional issue and a single dimensional garbage collector can't be a brilliant match for everything.
The book "Garbage Collection" by Richard Jones, recently discussed on HN, is something I'd highly recommend you buy and read.
Memory management is hard, and in a world where memory sizes keep increasing, new techniques being developed is expected and perfectly normal.
Unless someone comes up with a no pause, no compute power no code fully correct GC?
But there are also conservative GCs, RCs, etc, that fail different definitions also (leaving behind circular dependencies, having false positives, in reverse order), like in case of many things in CS, there isn’t an objective definition.
Extremely unlikely that such an algorithm exists of course, and even if it did, looking at sorting will quickly suggests that improvements will keep being found even if the best asymptotic complexity had been achieved.
If you look at the very latest JVMs you have three GCs which a spread over throughput-optimized (parallel), a middle ground jack of all trades (g1), and latency-optimized (zgc). They're a lot more self configuring in the past, so no matter what needs your app has it's usually just one CLI switch to get something fairly optimal.
But ZGC is going generational, at which point it will have significantly higher throughput than before. Also, all the JVM GCs can handle massive heaps these days (like, terabyte scale). So at that point the choice might become even simpler: just use ZGC all the time unless you can tolerate higher pauses and want to reclaim some CPU for the app, in which case go with parallel. And in many cases the right tradeoff between latency and performance could be inferred automatically from the frameworks and libraries that are on the classpath, meaning that for most apps even needing to make that choice could go away.
If you have a GC that doesn't pause, can handle terabyte sized heaps, has great throughput, is largely or completely self-configuring, is portable, open source, supports dozens of languages and has clean code, there are really very few metrics left to optimize after that. It seems like HotSpot is nearly there, especially when combined with GraalVM for language support.
Yeah. If.
I also think it’s unlikely that a GC can be written that handles both terabyte sized heaps on machines with hundreds of cores and megabyte sized heaps on single-CPU systems well.
But there aren't so many single core systems with megabyte sized heaps anymore. Even watches are multi-core these days.
But to answer your question, there is JamaicaVM and many niche JVM implementations with hard real time GCs — but it’s simply false that a GC would be somehow a problem for most of your devices.
Functional programming languages can be: https://www.reddit.com/r/haskell/comments/d5d13i / https://archive.is/4iyaG
And so it goes, the bottleneck is always moved.
http://cva.stanford.edu/classes/cs99s/papers/myer-sutherland...
In Java, the goal is to have something that performs reasonably well, without degenerative cases, for a wide variety of applications and services. It also has to handle cases where a monolithic code base results in a multitude of different memory behaviors. Even thinking too hard on the ideal behavior will negatively impact application code.
The research field of garbage collectors is a study of trade-offs.
A highly tuned, application-specific memory strategy will likely outperform Java, but the goal is to not require anyone to build such a thing for most software.
I'm not sure what you mean but I'll try to relate. Automatic garbage collection is a problem not just in the Java world. It's also needed in JavaScript, Python, Go, Haskell, etc.
Citation needed, but I suspect the Java Virtual Machine ecosystem has the most advanced GC algorithms in the world. Even if that's not true, I can tell you with certainty that other language environments have adopted features many years after Java did, such as JavaScript V8 introducing concurrent generational copying in year 2017 ( https://v8.dev/blog/orinoco-parallel-scavenger ). I'm sure there are examples in Go as well where their GC implemented features that Java had a decade earlier.
* Distilling the Real Cost of Production Garbage Collectors
https://twitter.com/stevemblackburn/status/15196411576216576...
https://www.youtube.com/watch?v=OUZt0mo1xic
https://old.reddit.com/r/java/comments/udtdke/the_real_cost_...
https://old.reddit.com/r/ProgrammingLanguages/comments/udt2p...
https://news.ycombinator.com/item?id=31192261
* Low-latency, high-throughput garbage collection
https://twitter.com/stevemblackburn/status/15183861337467289...
https://www.youtube.com/watch?v=1TLmawuxHfY
https://old.reddit.com/r/ProgrammingLanguages/comments/ubp2d...
https://old.reddit.com/r/java/comments/ubgyva/lxr_a_new_java...
Anything more dynamic will require some “ad hoc, informally-specified, bug-ridden, slow implementation of a GC”.
Some think that reference counting gives better performance predictability than a tracing GC, but that is no longer true, certainly compared to the generational ZGC presented here. If you could determine the time where the collection would take place with a refcounting GC, i.e. when the last reference is cleared, you wouldn't need a refcounting GC. It is unpredictable pretty much by definition.
There's a great paper (linked from this post https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/unifie...) showing how refcounting GCs can match the performance of tracing GCs -- in fact, how they can each have the properties of the other -- but that requires sophistication in the implementation of refcounting GCs that most of them don't have. So it is true that a sophisticated refcounting GC and a sophisticated tracing GC can exhibit similar behaviour, but while OpenJDK's tracing GCs are very sophisticated (especially ZGC and G1), most refcounting GCs in the wild are quite unsophisticated. It may certainly be true that unsophisticated refcounting GCs have more desirable properties than unsophisticated tracing GCs, but in practice the choice offered is between unsophisticated refcounting GCs and very sophisticated tracing GCs. The latter beat the former on most counts except for footprint overhead.
I don't think I've mentioned performance anywhere; thanks for the paper I'll take a look.
I don't think so. You don't know when memory will be freed or how long that would take only that it will be freed as soon as possible. The end result is lower footprint but that's about it.
That's an unsubstantiated claim.
While reference counting may be slower than tracing in the general case, Rust's reference counting is not the same thing as general reference counting in languages like e.g. Swift or Python. There are two reasons:
- The good majority (99%+) of objects in Rust don't need to be managed by reference counting at all.
- Rust relies heavily on move semantics to avoid updating the ref-counts, so the good majority of refcounted objects have very few (sometimes just 1) refcount updates.
> reference counting gives better performance predictability than a tracing GC, but that is no longer true, certainly compared to the generational ZGC presented here.
Where does ZGC claim nanosecond latency? But even if it did, it would be still worse, because refcounting doesn't do pauses at all. Pausing applies to pausing all application threads. Spending X nanoseconds freeing memory by one thread does not count as a pause, because the system can still make progress.
> refcounting doesn't do pauses at all
At the cost of throughput.
BTW, I'm not comparing Java to Rust, just ZGC to Rust's GC. I am well aware that it is not used for most objects.
And BTW, I wouldn't be so sure about throughput either. ZGC is capable of allocation rates of the order of only ~5 GB/s, which is way below the theoretical memory bandwidth. I bet jemalloc can do much better.
> ZGC is capable of allocation rates of the order of only ~5 GB/s
That was the non-generational ZGC. Indeed, ZGC's max throughput was well below that of ParallelGC and G1. One of the main goals of generational ZGC is to increase the throughput, and as you can see in the video, they got a 4x increase in throughput.
Object layout is the primary reason for the performance differences between low-level languages and manages ones — Java uses a thread local allocation buffer, which is for all practical purposes just as hot as the stack. What is more expensive is arrays of references and such, but that will be solved by value types once, hopefully.
EDIT: What I’m trying to say is that there is very little overhead to creating short-lived objects in Java.
I've been working on high performance Java software (databases) for many years now and the overhead of creating short lived objects is bearable only because we're going so far trying not to create those objects, writing Java in a kinda C-style - no objects, just primitives as much as you can.
The total overhead is not just bumping up the pointer and zeroing memory but actually all what happens when the GC runs out of the slab. By allocating short lived objects youre making GC collect earlier and overall doing more work. Also the faster you allocate, the more objects survive the collection and more objects must be copied. That process is very expensive and also very complex.
This can be an interesting inqury. Sad that you have to ruin it with snark.
I guess in some sense it was "solved" more than a decade ago in Azul's C4 (Continuously Concurrent Compacting Collector). I wonder how a generational ZGC will compare against it.
What's crazy to me is the sort of cognitive dissonance that you must have to hold a view like that, and still apply software updates at all.
It happens to be true that, if you could solve the halting problem, then you could decide any interesting property of programs; but this is simply because the antecedent is false.
See Wikipedia entry for Rice theorem subsection proof by reduction from the halting problem.
1. Have intersting property solver (e.g. is input squared)
2. Convert solver to halting problem solver
3. Solver is undecidable
So they are in some equatable/convertible.
You can solve it to some extent (e.g. does program terminate in X steps).
And I'm talking about the decider, not the program being fed as input.
> And I'm talking about the decider
EDIT: If by decider you mean program tested for having property P, that's a particular case and not applicable in general, ergo non-important (a program that's a NOP can be shown to leak no memory as well).
So the property P you are testing always returns true? Then it's not interesting per your definition. Leaking memory however is interesting.
The only noninteresting semantic properties of programs that exist are "this is a program" and "this is not a program."
> A program that emits "Yes" on every input will decide some property of programs with zero false negatives.
Followed by
> any semantic property that is not either always true or always false for all program executions
So what you said is your decider always outputs true. That's not an interesting property, because it's true for all inputs.
Btw what is the point of your argument? It still doesn't refute my initial statement. If you want to determine an interesting property of program like leaks, or automatic lifetime calculation or whether output is square of input, you run into Rice Theorem, which makes the problem undecidable. In other words it's impossible to get correct yes and no algorithmically.