5 ms·

Is Rust's borrow system also a form of garbage collection?

steveklabnik 10y ago
It is not, unless you count some library types that add reference counting, but those are rarely used. Ownership and borrowing are calculated at compile time, not runtime.
- millstone 10y ago
  Borrowing is purely compile time, but ownership has a runtime component, essentially a 1 bit reference count, called the drop flag. This is needed because objects may be conditionally initialized or uninitialized, depending on runtime values.
  - erickt 10y ago
    The drop flag is only generated for types that implement the `Drop` trait. Furthermore, there's work [0] that will shift the drop flag out of the value onto the call stack frame, and then even only in situations where the compiler cannot statically prove that that the type will be dropped or not. This should save a lot of memory, and potentially open up a whole host of optimizations. [0]: https://github.com/rust-lang/rust/issues/34398 https://github.com/rust-lang/rust/issues/34398
    - millstone 10y ago
      Yes, that's good. Swift also aggressively elides reference count modifications, and will stack-allocate class types if the lifetime can be proven.
      - pcwalton 10y ago
        It is silly to try to equate the drop flags with atomic reference counting on the heap. We could statically eliminate the drop flag entirely if we wanted to, with aggressive tail duplication. (It's not worth it, though, because the drop flag never shows up in profiles, so the code size bloat would be a cure worse than the disease.) Swift can never eliminate the runtime overhead of garbage collection. That's because, at a language level, Rust has static lifetime semantics and Swift has dynamic semantics.
        millstone 10y ago
        Whoa! I simply observed that both Rust and Swift eliminate their respective forms of reference counting when the lifetimes are statically known. The optimization is analogous, even if the nature of the reference counting is very different, as you say. To be sure, the proper Rust analog of Swift classes is Rc/Arc, not drop flags. > Swift can never eliminate the runtime overhead of garbage collection. That's because, at a language level, Rust has static lifetime semantics and Swift has dynamic semantics. Would you agree that Rust can never eliminate the runtime overhead of dynamic dispatch, because trait objects, at a language level, require dynamic dispatch? I would not agree: Rust programmers routinely eliminate it by sticking to the statically-dispatched areas of the language. Likewise, Swift programmers routinely avoid the runtime overhead of reference counting by using structs and not classes.
        Manishearth 10y ago
        > Would you agree that Rust can never eliminate the runtime overhead of dynamic dispatch, because trait objects, at a language level, require dynamic dispatch? I would not agree: Rust programmers routinely eliminate it by sticking to the statically-dispatched areas of the language. Likewise, Swift programmers routinely avoid the runtime overhead of reference counting by using structs and not classes. Sharing is something that is pretty necessary in programming; you are severely limited in what you can do without sharing. Trait objects are not, and are pretty rare in Rust. I often see people using enums over trait objects, and only sticking to trait objects for creating extensible APIs. Rust provides a way of sharing that does not involve any extra runtime overhead, which gets used often. Swift does have nice optimizations to value-typeify things, but without a finer-grained distinction between the kind of sharing you want to do to hint the compiler, this will be vastly limited as compared to Rust giving an explicit choice between borrows and Rc.
        millstone 10y ago
        When I hear sharing I think of shared ownership, and Rust steers you strongly away from that. See for example the awkwardness of global or thread-local variables in Rust. If you are referring to borrowing, Swift's answer is not class types, but inout. inout is not as flexible as Rust references, but it does not use reference counting. In most places where a Rust function would return a mutable reference, the analogous Swift function would take a closure that accepts that something as an inout.
- winstonewert 10y ago
  Ownership and borrowing may be calculated at compile time, but they still result in code being inserted to do things like deallocate objects at run time. It doesn't seem a useful distinction to call one garbage collection and the other not. Swift and Rust are far more similiar to each other in their memory management scheme then either is to Java or Go or D.
  - steveklabnik 10y ago
    > they still result in code being inserted to do things like deallocate objects at run time. I mean yeah, functions are called at runtime, just like every function. The key is more like static/dynamic typing: is the decision to call the destructor at all determined at compile time, or at runtime? (and millstone has been making good points about drop flags on this thread, but that's still only in fairly niche cases, only one bit, and is an implementation detail more than a fundamental aspect of the language. We've had several different variants of drop flags over time, and it's going to change even more in the future, as erickt says.) > Swift and Rust are far more similiar... Agree wholeheartedly.
    - winstonewert 10y ago
      "but that's still only in fairly niche cases, only one bit, and is an implementation detail more than a fundamental aspect of the language." Ok, but isn't the question of whether or not something is done at compile or runtime always an implementation detail? The fact that Rust figures out at compile time whether or not to insert the deallocation functions is super awesome, but it doesn't actually change the semantics of the language relative to if has to check flags or reference counts etc. This is different, to my mind, from static/dynamic typing because they have very different semantics. Early versions of Java used a VM which was dynamically typed, and PyPy converts python code to machine code that doesn't check types (if I'm lucky). So the distinction really isn't whether or not the decision is made at runtime. But really, I only objected in this thread because the claim was made that Swing and Rust were very different because Swing had GC and Rust didn't which seemed to be overemphasizing the differences here.
pcwalton 10y ago
No. Automatic memory management dynamically (at runtime) works out which objects are no longer referenced. Swift's reference counting is a form of automatic memory management because keeping the reference counts up to date is a way of dynamically working out which objects are alive and dead. Rust's ownership system does not: it is static, in that objects are unconditionally freed at specific, static program points.
- deleted 10y ago
  [deleted]

It is not, unless you count some library types that add reference counting, but those are rarely used. Ownership and borrowing are calculated at compile time, not runtime.

millstone 10y ago
Borrowing is purely compile time, but ownership has a runtime component, essentially a 1 bit reference count, called the drop flag. This is needed because objects may be conditionally initialized or uninitialized, depending on runtime values.
- erickt 10y ago
  The drop flag is only generated for types that implement the `Drop` trait. Furthermore, there's work [0] that will shift the drop flag out of the value onto the call stack frame, and then even only in situations where the compiler cannot statically prove that that the type will be dropped or not. This should save a lot of memory, and potentially open up a whole host of optimizations. [0]: https://github.com/rust-lang/rust/issues/34398 https://github.com/rust-lang/rust/issues/34398
  - millstone 10y ago
    Yes, that's good. Swift also aggressively elides reference count modifications, and will stack-allocate class types if the lifetime can be proven.
    - pcwalton 10y ago
      It is silly to try to equate the drop flags with atomic reference counting on the heap. We could statically eliminate the drop flag entirely if we wanted to, with aggressive tail duplication. (It's not worth it, though, because the drop flag never shows up in profiles, so the code size bloat would be a cure worse than the disease.) Swift can never eliminate the runtime overhead of garbage collection. That's because, at a language level, Rust has static lifetime semantics and Swift has dynamic semantics.
      - millstone 10y ago
        Whoa! I simply observed that both Rust and Swift eliminate their respective forms of reference counting when the lifetimes are statically known. The optimization is analogous, even if the nature of the reference counting is very different, as you say. To be sure, the proper Rust analog of Swift classes is Rc/Arc, not drop flags. > Swift can never eliminate the runtime overhead of garbage collection. That's because, at a language level, Rust has static lifetime semantics and Swift has dynamic semantics. Would you agree that Rust can never eliminate the runtime overhead of dynamic dispatch, because trait objects, at a language level, require dynamic dispatch? I would not agree: Rust programmers routinely eliminate it by sticking to the statically-dispatched areas of the language. Likewise, Swift programmers routinely avoid the runtime overhead of reference counting by using structs and not classes.
        Manishearth 10y ago
        > Would you agree that Rust can never eliminate the runtime overhead of dynamic dispatch, because trait objects, at a language level, require dynamic dispatch? I would not agree: Rust programmers routinely eliminate it by sticking to the statically-dispatched areas of the language. Likewise, Swift programmers routinely avoid the runtime overhead of reference counting by using structs and not classes. Sharing is something that is pretty necessary in programming; you are severely limited in what you can do without sharing. Trait objects are not, and are pretty rare in Rust. I often see people using enums over trait objects, and only sticking to trait objects for creating extensible APIs. Rust provides a way of sharing that does not involve any extra runtime overhead, which gets used often. Swift does have nice optimizations to value-typeify things, but without a finer-grained distinction between the kind of sharing you want to do to hint the compiler, this will be vastly limited as compared to Rust giving an explicit choice between borrows and Rc.
        millstone 10y ago
        When I hear sharing I think of shared ownership, and Rust steers you strongly away from that. See for example the awkwardness of global or thread-local variables in Rust. If you are referring to borrowing, Swift's answer is not class types, but inout. inout is not as flexible as Rust references, but it does not use reference counting. In most places where a Rust function would return a mutable reference, the analogous Swift function would take a closure that accepts that something as an inout.
winstonewert 10y ago
Ownership and borrowing may be calculated at compile time, but they still result in code being inserted to do things like deallocate objects at run time. It doesn't seem a useful distinction to call one garbage collection and the other not. Swift and Rust are far more similiar to each other in their memory management scheme then either is to Java or Go or D.
- steveklabnik 10y ago
  > they still result in code being inserted to do things like deallocate objects at run time. I mean yeah, functions are called at runtime, just like every function. The key is more like static/dynamic typing: is the decision to call the destructor at all determined at compile time, or at runtime? (and millstone has been making good points about drop flags on this thread, but that's still only in fairly niche cases, only one bit, and is an implementation detail more than a fundamental aspect of the language. We've had several different variants of drop flags over time, and it's going to change even more in the future, as erickt says.) > Swift and Rust are far more similiar... Agree wholeheartedly.
  - winstonewert 10y ago
    "but that's still only in fairly niche cases, only one bit, and is an implementation detail more than a fundamental aspect of the language." Ok, but isn't the question of whether or not something is done at compile or runtime always an implementation detail? The fact that Rust figures out at compile time whether or not to insert the deallocation functions is super awesome, but it doesn't actually change the semantics of the language relative to if has to check flags or reference counts etc. This is different, to my mind, from static/dynamic typing because they have very different semantics. Early versions of Java used a VM which was dynamically typed, and PyPy converts python code to machine code that doesn't check types (if I'm lucky). So the distinction really isn't whether or not the decision is made at runtime. But really, I only objected in this thread because the claim was made that Swing and Rust were very different because Swing had GC and Rust didn't which seemed to be overemphasizing the differences here.

pcwalton 10y ago

No. Automatic memory management dynamically (at runtime) works out which objects are no longer referenced. Swift's reference counting is a form of automatic memory management because keeping the reference counts up to date is a way of dynamically working out which objects are alive and dead. Rust's ownership system does not: it is static, in that objects are unconditionally freed at specific, static program points.

deleted 10y ago
[deleted]