Is there any known pratically relevant programming problem that cannot be solved without a GC, other than running code that assumes that one is available?
When it comes to memory management of particular data structures, a language like Rust can only safely distinguish between the presence of aliasing and the total lack of aliasing; it can't reason about memory locations that have bounded amounts of aliasing like doubly linked lists or trees with parent pointers. If the pattern of aliasing can be described by a regular language, then there exist decidable formalisms that can reason about it, but none of these formalisms have made it into practical programming languages.
If you go further and allow arbitrary directed graphs as data structures, then there is no decidable system for safe manual memory management (and depending on the definitions you use, this is provable). It's also often difficult to write (unproven) safe code in languages like these, so in practice people tend to just use region allocation (allocate your graph, temporarily leak it, and then free it all at once) or they implement a poor garbage collector.
Garbage collection also simplifies concurrent programming greatly, because it allows separate threads of execution to have no knowledge of the memory management strategy used by each other. If you try hard enough you can write a solution by hand that avoids the use of a general GC for any particular use case, but it eventually starts to feel like implementing a special-purpose GC.
That sounds really interesting, is there a good place to read more on the subject?
This is a very nice article about using epoch-based memory reclamation for lock-free datastructures in Rust: https://aturon.github.io/blog/2015/08/27/epoch/
To speculate: A big graph data structure in your big server (not distributed) and some parallel algorithm working on it. There is so much data that you need to purge the obsolete stuff once in a while. Smart pointers are not enough unless you introduce weak references, which is unsafe and error prone. A C++ programmer would probably implement some kind of application-specific garbage collector, but I doubt it would be better than the JVMs GC.
There for sure exists more then zero problems where garbage collection would be a worse solution then manual memory management. Even if you leave kernel development out of the equation.
Not only this. It also forces the programmer to implement RAII by hand.
If you have GC, it can free up a bunch of your complexity budget that you need elsewhere.
* Only use of unsafe is an unavoidable use for IterMut.
(Whether this would be worth the effort is another question, of course.)
use std::mem;
enum Lazy<T> {
Thunk(Box<Fn() -> T>),
EvalInProgress,
Forced(T),
}
impl<T> Lazy<T> {
fn new<F: 'static + Fn() -> T>(f: F) -> Lazy<T> {
Lazy::Thunk(Box::new(f))
}
fn force(&mut self) {
*self = match mem::replace(self, Lazy::EvalInProgress) {
Lazy::Thunk(f) => Lazy::Forced(f()),
Lazy::EvalInProgress => panic!("forcing while evaluating"),
Lazy::Forced(x) => Lazy::Forced(x),
}
}
fn get(&mut self) -> &mut T {
self.force();
match *self {
Lazy::Thunk(_) | Lazy::EvalInProgress => unreachable!(),
Lazy::Forced(ref mut x) => x,
}
}
}
fn main() {
let mut lazy = Lazy::new(|| {
println!("evaluating");
10
});
println!("first: {}", lazy.get());
println!("second: {}", lazy.get());
}
evaluating
first: 10
second: 10