4 ms·

First, "you can write a GC" in Rust is not seriously an answer. You can't do it without unsafe code, it would be a lot of effort to just purposely avoid using a

First, "you can write a GC" in Rust is not seriously an answer. You can't do it without unsafe code, it would be a lot of effort to just purposely avoid using a GCed language. And the existing efforts to do a GC in Rust are very simple mark-sweep designs that (unsurprisingly) don't even support generational collection. Second, the reason why I use the BDD example (or, more generally, persistent data structures) is that it's the simplest way for online discussions, because (unlike simpler examples), it's not amenable to pseudo-solutions that don't resolve the underlying problem and that you don't have the space and time for. The underlying problem is that Rust doesn't really do safe zero-cost abstractions for multiple ownership, and multiple ownership crops up more often in actual Rust code than people like to admit (global caches and memoization often end up with using cloning). You have to deal with it either through Rc<T>, Arc<T>, or cloning, of which cloning is the most common solution, because you don't have the footprints of shared ownership all over your code.

steveklabnik 9y ago
Have you seen crossbeam? That's not mark and sweep. As I said elsewhere, your definition of "zero cost abstractions" differs from what the term means.
- rbehrends 9y ago
  I know about crossbeam vaguely (mostly because the non-blocking concurrency is of interest to my research), but due to lack of documentation, haven't really dug into it and am not even sure what it has to do with GC? > As I said elsewhere, your definition of "zero cost abstractions" differs from what the term means. I'm going by Stroustrup's definition [1]? If your argument is – I'm not sure here – that "Rust gets zero-cost abstractions by limiting what you can do to beat its normal mechanisms", then that's not terribly convincing. What it boils down to is that multiple ownership is a weak spot of Rust, as for other languages that attempt the compile-time memory management thing, such as ParaSail. TANSTAAFL, "There ain't no such thing as a free lunch." No compile-time mechanism can solve the reachability problem for arbitrary runtime graphs without adding some overhead somewhere. Rust does zero overhead for certain kinds of graphs, but still needs overhead for others. [1] http://www.stroustrup.com/ETAPS-corrected-draft.pdf http://www.stroustrup.com/ETAPS-corrected-draft.pdf
  - steveklabnik 9y ago
    Crossbeam's epoch based collection is basically a form of GC, for certain kinds of data structures. Yeah Bjane's definition doesn't say "no overhead", it says "no extra overhead." If your data structure requires a GC, then writing a GC for it is a zero-overhead abstraction. What I'm saying is "gotcha, you need some runtime support for this" is not contradictory to zero-cost abstractions.
    - rbehrends 9y ago
      > If your data structure requires a GC, then writing a GC for it is a zero-overhead abstraction. What I'm saying is "gotcha, you need some runtime support for this" is not contradictory to zero-cost abstractions. There are two points to be made here. 1. The problem is not that a data structure needs GC; it's that reference counting (or worse, atomic reference counting) is about the highest-overhead garbage collection in existence. It's popular because it's easy to implement, has mostly predictable performance, and can be implemented as a library without compiler support, but performance is not one of its virtues. The cost really becomes absurd in the `Arc<T>` case, where you have an atomic operation for each reference count update. Nobody actually implements performance-sensitive data structures using naive atomic reference counting outside of C++ and Rust. 2. Persistent data structures (or anything with structural sharing) are, as I mentioned, just the simplest example. They are suitable for illustrating the problems Rust has with shared ownership, but shared ownership is not limited to those. Rust also has problems with shared ownership in a number of other scenarios (such as global caching or any scenario where object lifetime depends on the semantic state of a program). The underlying problem is that whenever you approximate an undecidable predicate (pointer safety in this case) with a decidable subpredicate, then any zero-cost abstraction claim usually falls flat, because there are typically other decidable subpredicates (not even counting throwing a full theorem prover at the problem) that can handle cases without overhead that your approach can't. In the case of pointer safety, model-checking approaches would be an obvious and well-known example. Obviously, these alternative approaches may carry different software engineering overhead, but a claim about an abstraction being zero-cost is independent of software engineering costs (not to mention that this is an area where Rust is hardly without its own issues).

steveklabnik 9y ago

Have you seen crossbeam? That's not mark and sweep. As I said elsewhere, your definition of "zero cost abstractions" differs from what the term means.

rbehrends 9y ago
I know about crossbeam vaguely (mostly because the non-blocking concurrency is of interest to my research), but due to lack of documentation, haven't really dug into it and am not even sure what it has to do with GC? > As I said elsewhere, your definition of "zero cost abstractions" differs from what the term means. I'm going by Stroustrup's definition [1]? If your argument is – I'm not sure here – that "Rust gets zero-cost abstractions by limiting what you can do to beat its normal mechanisms", then that's not terribly convincing. What it boils down to is that multiple ownership is a weak spot of Rust, as for other languages that attempt the compile-time memory management thing, such as ParaSail. TANSTAAFL, "There ain't no such thing as a free lunch." No compile-time mechanism can solve the reachability problem for arbitrary runtime graphs without adding some overhead somewhere. Rust does zero overhead for certain kinds of graphs, but still needs overhead for others. [1] http://www.stroustrup.com/ETAPS-corrected-draft.pdf http://www.stroustrup.com/ETAPS-corrected-draft.pdf
- steveklabnik 9y ago
  Crossbeam's epoch based collection is basically a form of GC, for certain kinds of data structures. Yeah Bjane's definition doesn't say "no overhead", it says "no extra overhead." If your data structure requires a GC, then writing a GC for it is a zero-overhead abstraction. What I'm saying is "gotcha, you need some runtime support for this" is not contradictory to zero-cost abstractions.
  - rbehrends 9y ago
    > If your data structure requires a GC, then writing a GC for it is a zero-overhead abstraction. What I'm saying is "gotcha, you need some runtime support for this" is not contradictory to zero-cost abstractions. There are two points to be made here. 1. The problem is not that a data structure needs GC; it's that reference counting (or worse, atomic reference counting) is about the highest-overhead garbage collection in existence. It's popular because it's easy to implement, has mostly predictable performance, and can be implemented as a library without compiler support, but performance is not one of its virtues. The cost really becomes absurd in the `Arc<T>` case, where you have an atomic operation for each reference count update. Nobody actually implements performance-sensitive data structures using naive atomic reference counting outside of C++ and Rust. 2. Persistent data structures (or anything with structural sharing) are, as I mentioned, just the simplest example. They are suitable for illustrating the problems Rust has with shared ownership, but shared ownership is not limited to those. Rust also has problems with shared ownership in a number of other scenarios (such as global caching or any scenario where object lifetime depends on the semantic state of a program). The underlying problem is that whenever you approximate an undecidable predicate (pointer safety in this case) with a decidable subpredicate, then any zero-cost abstraction claim usually falls flat, because there are typically other decidable subpredicates (not even counting throwing a full theorem prover at the problem) that can handle cases without overhead that your approach can't. In the case of pointer safety, model-checking approaches would be an obvious and well-known example. Obviously, these alternative approaches may carry different software engineering overhead, but a claim about an abstraction being zero-cost is independent of software engineering costs (not to mention that this is an area where Rust is hardly without its own issues).