4 ms·

Aside: Could a Rust library provide an Rc<T> interface but use a more sophisticated GC algorithm underneath?

creata 2y ago
You probably already know this, but the gc crate is an implementation of a somewhat more sophisticated GC, but it uses `derive`s to implement tracing, so it's not exactly the Rc<T> interface.
pornel 2y ago
There are a couple of proof-of-concept libraries adding a `Gc<T> where T: Traceable`, so it is doable. You can't change the existing Rc, because it's a concrete type. Making it use a tracing GC internally would require a lot of compiler magic. However, I don't think a GC will catch on in Rust in its current form. Rust's userbase likes it as a no-GC language. Plus a 3rd party library GC wrapper type can't save you from having to learn ownership and lifetimes used by literally everything else. Once you invest time to learn the "zero-cost" references, a runtime Gc is less appealing, and won't be as ergonomic than the built-in references. Swift, OCaml, and Mojo are trying to add some subset of Rust-like ownership and borrowing, but in a simpler form.
devit 2y ago
You can, but it turns out that, as one may intuitively expect, a GC is never needed unless implementing a VM for a GC-based language or an API that required GC like fd passing on unix domain sockets, and those generally want an ad-hoc GC instead tailored to whatever you are implementing. Since it's not needed and it's massively worse than reference counting (assuming you only change reference counts when essential and use borrowing normally) due to the absurd behavior of scanning most of the heap at arbitrary times, there is no Rust GC crate in widespread use.
- o11c 2y ago
  For GC-based inner languages it's mandatory to mention that inter-language cycles are nasty. Life is much easier in a world of explicit ownership! I curate a list of what kinds of ownership people actually want: https://gist.github.com/o11c/dee52f11428b3d70914c4ed5652d43f7 https://gist.github.com/o11c/dee52f11428b3d70914c4ed5652d43f... It's been 6 years since I first posted it publicly, and neither I nor anyone giving suggestions has ever actually found a use for GC.
  - zarzavat 2y ago
    IME the utility of GC is not for structs but for closures. It’s very easy to cause cycles when freely using closures in non-GC languages.
- tsimionescu 2y ago
  Almost all GCs used in practice today only scan the set of live objects, which in normal operation is much smaller than the entire heap. They also allow much more efficient allocation and de-allocation. The problems with GC are threefold, and why you might not want it in a systems language: 1. GC requires more memory than strictly necessary to be efficient (usually about 1.5x - 2x the amount you absolutely need). You're basically trading runtime efficiency for memory. 2. GC performance is harder to predict and reason about than certain other allocation strategies 3. GC languages tend to encourage excessive heap allocation for various reasons, ending up with much more junk than a typical Rust or C program that has a similar amount of entities Note that item 2 is the one that's least understood. The best part about GCs is that they make heap allocation trivial, and they make de-allocation a no-op. In contrast, both malloc() and free() are extremely complex and costly operations. The GC does impose a cost on every pointer write, similar to (but typically less than) the overhead of Arc<T> over a T*, but that has a very uniform and predictable cost. The problem of unpredictability only comes in the collection phase, and is mostly related to (a) when the collection happens, (b) how much data actually has to be scanned (how many live objects are present on the heap and stack), and (c) what type of collection needs to happen (is it enough to collect from this thread's young generation, or do you need to collect all generations from all threads). Note that many of these problems are in fact solvable, and there actually exist GCs with constant predictable collection times, suitable even for realtime applications (which malloc/free don't support). They are very sophisticated technology that no one is distributing for free though (e.g. you have to pay Azul for a realtime-compatible Java).
  - devbent 2y ago
    People often forget that the runtime of free is not trivially calculatable! I've worked on tiny embedded systems (.net micro framework) where for a given usage pattern the GC was perfectly predictable, as it should be.
    - ShroudedNight 2y ago
      'Costly' doesn't seem to require that O(k) be non-constant: http://www.gii.upv.es/tlsf/ http://www.gii.upv.es/tlsf/
- kaba0 2y ago
  > Since it's not needed and it's massively worse than reference counting Lol, what? Maybe don’t go asserting stuff you clearly know little about. Reference counting is a fine tradeoff for manual memory-managed languages, but it is absolutely smoked out of the water by a tracing GC on most counts. It’s almost like JVM, V8, etc engineers know a thing about the topic and don’t have RC for a good reason. Tracing GC doesn’t burden the mutator threads with additional work, almost everything can be done in parallel, resulting in vastly better throughput. Imagine dropping the last reference to a huge graph, one can actually observe it when exiting a c++ program, it might hang for a few seconds before returning control to you, as all the destructors are recursively called, serially, on the program thread, literally pointer by pointer jumping across the heap, the very thing you are so afraid of. And I didn’t even get to the atomic part, bumping a number up or down with synchronization between CPUs is literally the slowest operation you can do on a modern machine. Tracing GCs elegantly avoid all these problems at the price of some memory overhead. None of these GC algorithms (yes, RC is a GC) is a silver bullet, but let’s not joke ourselves.
  - devit 2y ago
    That's because, unlike Rust, those languages with RC would have a lot of unnecessarily refcounted objects because they don't have value objects, do a whole lot of useless reference count updates because they don't have borrowing and always have to use atomics because they can't ensure that some objects are not shared between threads (and also would need a cycle collector in addition to the reference counting). If you use reference counting properly in a well-designed language then it's obviously better than GC since it's rarely used, fast, simple, local and needs no arbitrary heuristics. The destructor cascades are only a problem for latency and potential stack overflow and can be solved by having custom destructors for recursive structures that queue nodes for destruction, or using arena allocators if applicable.
    - kaba0 2y ago
      So, RC is better than tracing GC, when it’s not used as memory management, and it is special cased everywhere.. got you! Like, as I explicitly wrote, it is probably the correct choice for low-level languages close to the metal, that want easy compatibility with other languages through FFI. But the method itself has still got a much slower throughput than a tracing GC, when used in a similar manner. Anything else is a useless comparison, like is a bicycle better than a tank.
- nickpsecurity 2y ago
  Many use GC languages for productivity in code where that’s more important. Far as slowdowns, there are concurrent and real-time (fixed timing) GC’s out there which reduce or avoid the problems you mention. JX OS also let you mix different GC’s for different components. So, there’s a performance hit of some kind with optional tuning that takes no expertise. Many people would go for those tradeoffs for some applications. Especially if they got to keep using safe, no-GC code in their libraries with their efficiency benefits.
- eru 2y ago
  > You can, but it turns out that, as one may intuitively expect, a GC is never needed unless [...] Rust uses plenty of reference counting. You could replace most of that with a GC; depending on your GC implementation and your reference counting implementation, and your requirements in terms of latency and throughput and ability to handle cycles. > Since it's not needed and it's massively worse than reference counting (assuming you only change reference counts when essential and use borrowing normally) due to the absurd behavior of scanning most of the heap at arbitrary times, there is no Rust GC crate in widespread use. There are choices. You can have real time garbage collectors. And if you want to handle cycles, you need some kind of tracing anyway. Also, if you only care about throughput and not about latency, garbage collection can easily be faster than reference counting. If you don't allow cycles, you can also take advantage of that in your garbage collection. See how Erlang does it. (In Erlang, the garbage collector relocates your objects so that they are in topological order, so all references only point forwards in memory. You can combine that with generational gc, too, of course.)

You probably already know this, but the gc crate is an implementation of a somewhat more sophisticated GC, but it uses `derive`s to implement tracing, so it's not exactly the Rc<T> interface.

pornel 2y ago

There are a couple of proof-of-concept libraries adding a `Gc<T> where T: Traceable`, so it is doable. You can't change the existing Rc, because it's a concrete type. Making it use a tracing GC internally would require a lot of compiler magic. However, I don't think a GC will catch on in Rust in its current form. Rust's userbase likes it as a no-GC language. Plus a 3rd party library GC wrapper type can't save you from having to learn ownership and lifetimes used by literally everything else. Once you invest time to learn the "zero-cost" references, a runtime Gc is less appealing, and won't be as ergonomic than the built-in references. Swift, OCaml, and Mojo are trying to add some subset of Rust-like ownership and borrowing, but in a simpler form.

devit 2y ago

You can, but it turns out that, as one may intuitively expect, a GC is never needed unless implementing a VM for a GC-based language or an API that required GC like fd passing on unix domain sockets, and those generally want an ad-hoc GC instead tailored to whatever you are implementing. Since it's not needed and it's massively worse than reference counting (assuming you only change reference counts when essential and use borrowing normally) due to the absurd behavior of scanning most of the heap at arbitrary times, there is no Rust GC crate in widespread use.

o11c 2y ago
For GC-based inner languages it's mandatory to mention that inter-language cycles are nasty. Life is much easier in a world of explicit ownership! I curate a list of what kinds of ownership people actually want: https://gist.github.com/o11c/dee52f11428b3d70914c4ed5652d43f7 https://gist.github.com/o11c/dee52f11428b3d70914c4ed5652d43f... It's been 6 years since I first posted it publicly, and neither I nor anyone giving suggestions has ever actually found a use for GC.
- zarzavat 2y ago
  IME the utility of GC is not for structs but for closures. It’s very easy to cause cycles when freely using closures in non-GC languages.
tsimionescu 2y ago
Almost all GCs used in practice today only scan the set of live objects, which in normal operation is much smaller than the entire heap. They also allow much more efficient allocation and de-allocation. The problems with GC are threefold, and why you might not want it in a systems language: 1. GC requires more memory than strictly necessary to be efficient (usually about 1.5x - 2x the amount you absolutely need). You're basically trading runtime efficiency for memory. 2. GC performance is harder to predict and reason about than certain other allocation strategies 3. GC languages tend to encourage excessive heap allocation for various reasons, ending up with much more junk than a typical Rust or C program that has a similar amount of entities Note that item 2 is the one that's least understood. The best part about GCs is that they make heap allocation trivial, and they make de-allocation a no-op. In contrast, both malloc() and free() are extremely complex and costly operations. The GC does impose a cost on every pointer write, similar to (but typically less than) the overhead of Arc<T> over a T*, but that has a very uniform and predictable cost. The problem of unpredictability only comes in the collection phase, and is mostly related to (a) when the collection happens, (b) how much data actually has to be scanned (how many live objects are present on the heap and stack), and (c) what type of collection needs to happen (is it enough to collect from this thread's young generation, or do you need to collect all generations from all threads). Note that many of these problems are in fact solvable, and there actually exist GCs with constant predictable collection times, suitable even for realtime applications (which malloc/free don't support). They are very sophisticated technology that no one is distributing for free though (e.g. you have to pay Azul for a realtime-compatible Java).
- devbent 2y ago
  People often forget that the runtime of free is not trivially calculatable! I've worked on tiny embedded systems (.net micro framework) where for a given usage pattern the GC was perfectly predictable, as it should be.
  - ShroudedNight 2y ago
    'Costly' doesn't seem to require that O(k) be non-constant: http://www.gii.upv.es/tlsf/ http://www.gii.upv.es/tlsf/
kaba0 2y ago
> Since it's not needed and it's massively worse than reference counting Lol, what? Maybe don’t go asserting stuff you clearly know little about. Reference counting is a fine tradeoff for manual memory-managed languages, but it is absolutely smoked out of the water by a tracing GC on most counts. It’s almost like JVM, V8, etc engineers know a thing about the topic and don’t have RC for a good reason. Tracing GC doesn’t burden the mutator threads with additional work, almost everything can be done in parallel, resulting in vastly better throughput. Imagine dropping the last reference to a huge graph, one can actually observe it when exiting a c++ program, it might hang for a few seconds before returning control to you, as all the destructors are recursively called, serially, on the program thread, literally pointer by pointer jumping across the heap, the very thing you are so afraid of. And I didn’t even get to the atomic part, bumping a number up or down with synchronization between CPUs is literally the slowest operation you can do on a modern machine. Tracing GCs elegantly avoid all these problems at the price of some memory overhead. None of these GC algorithms (yes, RC is a GC) is a silver bullet, but let’s not joke ourselves.
- devit 2y ago
  That's because, unlike Rust, those languages with RC would have a lot of unnecessarily refcounted objects because they don't have value objects, do a whole lot of useless reference count updates because they don't have borrowing and always have to use atomics because they can't ensure that some objects are not shared between threads (and also would need a cycle collector in addition to the reference counting). If you use reference counting properly in a well-designed language then it's obviously better than GC since it's rarely used, fast, simple, local and needs no arbitrary heuristics. The destructor cascades are only a problem for latency and potential stack overflow and can be solved by having custom destructors for recursive structures that queue nodes for destruction, or using arena allocators if applicable.
  - kaba0 2y ago
    So, RC is better than tracing GC, when it’s not used as memory management, and it is special cased everywhere.. got you! Like, as I explicitly wrote, it is probably the correct choice for low-level languages close to the metal, that want easy compatibility with other languages through FFI. But the method itself has still got a much slower throughput than a tracing GC, when used in a similar manner. Anything else is a useless comparison, like is a bicycle better than a tank.
nickpsecurity 2y ago
Many use GC languages for productivity in code where that’s more important. Far as slowdowns, there are concurrent and real-time (fixed timing) GC’s out there which reduce or avoid the problems you mention. JX OS also let you mix different GC’s for different components. So, there’s a performance hit of some kind with optional tuning that takes no expertise. Many people would go for those tradeoffs for some applications. Especially if they got to keep using safe, no-GC code in their libraries with their efficiency benefits.
eru 2y ago
> You can, but it turns out that, as one may intuitively expect, a GC is never needed unless [...] Rust uses plenty of reference counting. You could replace most of that with a GC; depending on your GC implementation and your reference counting implementation, and your requirements in terms of latency and throughput and ability to handle cycles. > Since it's not needed and it's massively worse than reference counting (assuming you only change reference counts when essential and use borrowing normally) due to the absurd behavior of scanning most of the heap at arbitrary times, there is no Rust GC crate in widespread use. There are choices. You can have real time garbage collectors. And if you want to handle cycles, you need some kind of tracing anyway. Also, if you only care about throughput and not about latency, garbage collection can easily be faster than reference counting. If you don't allow cycles, you can also take advantage of that in your garbage collection. See how Erlang does it. (In Erlang, the garbage collector relocates your objects so that they are in topological order, so all references only point forwards in memory. You can combine that with generational gc, too, of course.)