GC and Rust Part 1: Specifying the Problem | Hacker News Reader

GC and Rust Part 1: Specifying the Problem

blog.pnkfx.org

139 pointssteveklabnik23 comments

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?

Doubly-linked list without unsafe code.

A whole GC sounds like a lot of unsafe code!

Certainly, but that's a one-time cost (wrt. code complexity at least).

http://bluss.github.io/ixlist/target/doc/ixlist/struct.List....

* Only use of unsafe is an unavoidable use for IterMut.

That general technique pushes the problem around, where an implementation error will still result in a use-after-free (where you access a dead/reused array element). This could be fixed by paying for a runtime version check. Also, because it uses a Vec, it doesn't have O(1) performance, either. This could also be fixed by using a different underlying data structure.

Yeah, it certainly has weaknesses.

Well, that's true in Rust, but there are systems out there that will allow you to prove doubly-linked lists correct. An alternate approach to GC/RC would be to introduce more type system machinery (or to try to encode it in a library) to allow the construction of these data structures safely.

(Whether this would be worth the effort is another question, of course.)

I can't imagine how there could be. All a GC does is free the programmer from worrying about memory leaks/manual memory management themselves (sort of). It doesn't have any effect on computability.

It does have a significant impact on performance. Especially for real time operating systems, micro controlles, and other embedded systems.

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.

> All a GC does is free the programmer from ...

Not only this. It also forces the programmer to implement RAII by hand.

There's some difference between "it's computable" and "it's practical to write a program that does it in a reasonably simple and maintainable way", though.

If you have GC, it can free up a bunch of your complexity budget that you need elsewhere.

Lazy evaluation, I think?

That can still be done without a GC, e.g. the following is sketch of lazy evaluation in Rust:

  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());
  }

Output:

  evaluating
  first: 10
  second: 10

(There's a pile of tweaks/optimisations that can be made, like making `force` truly a no-op for values that have already been forced and removing the need for the lazy object to be mutable, but the above demonstrates the core idea.)

I remember Cliff Click said that some parallel/concurrent algorithms are infeasable without a GC, because the additional complexity of memory management. However, I do not remember any specific examples.

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.

Some algorithms are tricky, but there's a lot one can do without a GC via epoch-based reclamation schemes: http://aturon.github.io/blog/2015/08/27/epoch/ (I guess this could very well be regarded as a sort of application-specific GC, but, if anything, it feels closer to reference counting than a tracing GC).

Thanks for the link!

The question you ask is a bit vague, so pardon me for only answering one form of it.

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.

> If the pattern of aliasing can be described by a regular language, then there exist decidable formalisms that can reason about it

That sounds really interesting, is there a good place to read more on the subject?

A little digging (as this is interesting to me as well) brought up the Pointer Assertion Logic Engine: http://www.brics.dk/RS/00/39/BRICS-RS-00-39.pdf

Having a GC can make the implementation of lock-free data structures significantly easier. Without GC you effectively end up implementing a sort of very specialized garbage collection scheme for the data structure.

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/

Reply on news.ycombinator.com