5 ms·

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?

• lightgreen 11y ago
  Doubly-linked list without unsafe code.
  • ben0x539 11y ago
    A whole GC sounds like a lot of unsafe code!
    • lomnakkus 11y ago
      Certainly, but that's a one-time cost (wrt. code complexity at least).
  • steveklabnik 11y ago
    http://bluss.github.io/ixlist/target/doc/ixlist/struct.List.html http://bluss.github.io/ixlist/target/doc/ixlist/struct.List.... * Only use of unsafe is an unavoidable use for IterMut.
    • SamReidHughes 11y ago
      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.
      • steveklabnik 11y ago
        Yeah, it certainly has weaknesses.
  • pcwalton 11y ago
    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.)
• eximius 11y ago
  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.
  • lgunsch 11y ago
    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.
  • pif 11y ago
    > All a GC does is free the programmer from ... Not only this. It also forces the programmer to implement RAII by hand.
    • deleted 11y ago
      [deleted]
  • ben0x539 11y ago
    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.
• deleted 11y ago
  [deleted]
• klauserc 11y ago
  Lazy evaluation, I think?
  • dbaupp 11y ago
    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.)
• deleted 11y ago
  [deleted]
  • cwzwarich 11y ago
    That article doesn't mention persistent data structures.
    • steveklabnik 11y ago
      Ugh, I always screw up the difference between persistent and lock-free, data structures are not my forte.
• qznc 11y ago
  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.
  • deleted 11y ago
    [deleted]
  • dbaupp 11y ago
    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/ 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).
    • shmerl 11y ago
      Thanks for the link!
• cwzwarich 11y ago
  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.
  • Rusky 11y ago
    > 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?
    • pcwalton 11y ago
      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 http://www.brics.dk/RS/00/39/BRICS-RS-00-39.pdf
• nikic 11y ago
  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/ https://aturon.github.io/blog/2015/08/27/epoch/