4 ms·

Can you elaborate, what key assumptions about memory safety linked lists break? Sure, double linked lists may have non-trivial ownership, but that doesn't compr

by delamon 10mo ago

Can you elaborate, what key assumptions about memory safety linked lists break? Sure, double linked lists may have non-trivial ownership, but that doesn't compromise safety.

estebank 10mo ago
Rust wants all memory to be modeled as an ownership tree: the same bit of memory can't be owned by more than one data structure. A doubly linked list breaks that requirement so it can't be modeled in safe Rust directly. The options are using unsafe, or using one of the pointer wrapper types that have runtime checks that ensure correct behavior and own the underlying memory as far Rust is concerned.
- zozbot234 10mo ago
  You can do it by combining ghostcell/qcell along with some bespoke "static/compile-time reference counting" for the double links part. But ghostcell/qcell is quite difficult to use with Rust's current feature set (it has to use lifetime hacks to place a safe "brand" on type instantiations, a kind of quasi-capability construct), so it hasn't become a part of standard rust so far.
- delamon 10mo ago
  Right. So it is not that double-linked lists are inherently unsafe, it is (just) Rust ownership model cannot represent them (any other cyclic structures).
  - wiz21c 10mo ago
    It's not that it cannot, it just doesn't want to :-) (but you're right). I guess that in this very case of DLL, it's a bit hard to swallow. To be honest, it's because the rest of rust really helps me in other areas of my projects that I have accepted that. Learning the ownership model of rust is really painful, it really forces you to code in its way and it was not pleasant to me.
    - delamon 10mo ago
      I've been trying to convert to Rust an in-memory database and failed. It is strictly single-threaded and full of intrusive lists. I tried hard to please borrow-checker, but one have little choice when internal structures are full of cycles. The result was ugly mess of Rc all over the place. I guess it is just an example of a problem that doesn't fit Rust well. This makes me wonder: what performance cost Rust code pay due to inability represent cyclic structures efficiently? It seems people tend to design their data in way to please Rust and not in way that would be otherwise more performance efficient.
      - steveklabnik 10mo ago
        Using Rc doesn't sound like an intrusive list to me. Personally I find tons of Rcs to be messy, so I'd agree with you. > what performance cost Rust code pay due to inability represent cyclic structures efficiently? You can still write the code you'd write in C with unsafe. There's no inherent loss left on the table. Furthermore, a lot of C folks reach for intrusive lists because it's easy in C, but that doesn't mean that it's always the most performant. See https://bcantrill.dtrace.org/2018/09/28/the-relative-performance-of-c-and-rust/ https://bcantrill.dtrace.org/2018/09/28/the-relative-perform... as an example of this phenomenon.

by delamon 10mo ago

Can you elaborate, what key assumptions about memory safety linked lists break? Sure, double linked lists may have non-trivial ownership, but that doesn't compromise safety.

estebank 10mo ago

Rust wants all memory to be modeled as an ownership tree: the same bit of memory can't be owned by more than one data structure. A doubly linked list breaks that requirement so it can't be modeled in safe Rust directly. The options are using unsafe, or using one of the pointer wrapper types that have runtime checks that ensure correct behavior and own the underlying memory as far Rust is concerned.

zozbot234 10mo ago
You can do it by combining ghostcell/qcell along with some bespoke "static/compile-time reference counting" for the double links part. But ghostcell/qcell is quite difficult to use with Rust's current feature set (it has to use lifetime hacks to place a safe "brand" on type instantiations, a kind of quasi-capability construct), so it hasn't become a part of standard rust so far.
delamon 10mo ago
Right. So it is not that double-linked lists are inherently unsafe, it is (just) Rust ownership model cannot represent them (any other cyclic structures).
- wiz21c 10mo ago
  It's not that it cannot, it just doesn't want to :-) (but you're right). I guess that in this very case of DLL, it's a bit hard to swallow. To be honest, it's because the rest of rust really helps me in other areas of my projects that I have accepted that. Learning the ownership model of rust is really painful, it really forces you to code in its way and it was not pleasant to me.
  - delamon 10mo ago
    I've been trying to convert to Rust an in-memory database and failed. It is strictly single-threaded and full of intrusive lists. I tried hard to please borrow-checker, but one have little choice when internal structures are full of cycles. The result was ugly mess of Rc all over the place. I guess it is just an example of a problem that doesn't fit Rust well. This makes me wonder: what performance cost Rust code pay due to inability represent cyclic structures efficiently? It seems people tend to design their data in way to please Rust and not in way that would be otherwise more performance efficient.
    - steveklabnik 10mo ago
      Using Rc doesn't sound like an intrusive list to me. Personally I find tons of Rcs to be messy, so I'd agree with you. > what performance cost Rust code pay due to inability represent cyclic structures efficiently? You can still write the code you'd write in C with unsafe. There's no inherent loss left on the table. Furthermore, a lot of C folks reach for intrusive lists because it's easy in C, but that doesn't mean that it's always the most performant. See https://bcantrill.dtrace.org/2018/09/28/the-relative-performance-of-c-and-rust/ https://bcantrill.dtrace.org/2018/09/28/the-relative-perform... as an example of this phenomenon.