5 ms·

I've also found that basic problems like how to implement typical data structures (without unsafe code) are controversial, difficult, or actually impossible. Th

by TillE 11y ago

I've also found that basic problems like how to implement typical data structures (without unsafe code) are controversial, difficult, or actually impossible. That's really not good. Still optimistic about Rust. But it has some fundamental issues to solve before it's generally usable.

Gankro 11y ago
You can express data structures safely perfectly fine in Rust as long as you do all the things that make them safe in every other language -- aggressively garbage collect, indirect, and runtime validate. I'm not aware of any language that lets you implement an interesting high performance data structure totally safely. Heck, Rust is impressive because you can encode singly-linked-stack and binary-tree-without-parent-pointers efficiently and safely without garbage collection! You can even build iterators that are statically verified to iterate over every element at most once, and statically guaranteed to not be invalidated. Type systems that are powerful enough to ensure the safety of even moderately complex designs (doubly linked list, tree with parent pointers, singly linked stack, hashmap) appear to be unwieldy and relegated to academia.
- catnaroek 11y ago
  > even moderately complex designs (doubly linked list, tree with parent pointers, singly linked stack, hashmap) In other words, imperative data structures? My experience with implementing custom data structures in Rust: (0) Purely functional data structures: You don't even need borrows to express them. The main downsides are: poor locality of reference, inability to parameterize the data structure over whether its nodes are uniquely owned or reference counted. HKTs would fix the latter. (1) Imperative data structures: Not even mutable borrows will help you. You just need to drop down to `unsafe` code.
  - Gankro 11y ago
    More or less. Hence why high performance data structures are invariably unsafe to implement in every language if they can be implemented at all. Rust lets you implement them, and for almost all of them you can even expose a safe high-performance interface to them. The only major exceptions I know for interfaces are * intrusive data structures that just blindly point to random data lying on the stack or stored in other types (a construct like C++ move constructors is necessary to safely manipulate these). * priority queues with high-performance decrease-key (you effectively need to hand clients a pointer to every node, that they can always pass back to you to deref and update the structure from -- this is unsound if that node has been popped and you aren't using a GC scheme).
    - eridius 11y ago
      I have no idea what a "priority queue with high-performance decrease-key" is, but from your brief description, you can't replace the "pointer to every node" with a RAII value that keeps the node from being deallocated?
      - Gankro 11y ago
        Yes, that's garbage collection. :)
        eridius 11y ago
        Ah so you're defining reference-counting as garbage collection?
        Gankro 11y ago
        Absolutely. I don't find the distinction to be particularly meaningful in this case.
        blaisio 11y ago
        Reference counting is a form of garbage collection.
    - catnaroek 11y ago
      Certainly a safe interface is better than none, but unsafe and/or inefficient implementations are just symptoms of expressiveness issues, not a fact of life. That being said, what Rust has is already a strict improvement over not even being able to state how ephemeral data structures can be safely used. Also, establishing the safety of code that manipulates arrays (without runtime bounds checks), cyclical data structures (e.g. doubly-linked lists) and user-defined forms of indirection (e.g. hashing) is probably best done using tools other than unification-based type checkers.
pcwalton 11y ago
Let's not exaggerate the problem. First of all, non-lexical lifetimes have nothing to do with doubly linked lists (what you're referring to). Second, the language is clearly generally usable, as evidenced by the hundreds of thousands of lines of code written in it, most of which was written by people who have never touched the compiler. The reason is simple: most people get by just fine with the rich set of generic collections available in the standard library and on crates.io. For cases in which those aren't sufficient, you write unsafe code or use Rc. Nobody claims Golang is "generally unusable" because you can't implement your own generic data structures. That it's harder than in unsafe C or C++ to implement doubly linked lists in Rust is just a less severe version of the same kind of thing.
rectang 11y ago
I'm just learning Rust and this is the primary question I have: If I can't use the data structures I'm accustomed to (because of mutability issues), what are the alternatives? Where are the articles describing those alternatives? I've seen a lot of interesting discourse about the low-level stuff (e.g. error handling), but not higher-level "start here" approaches.
- deleted 11y ago
  [deleted]
- bsder 11y ago
  > If I can't use the data structures I'm accustomed to (because of mutability issues), what are the alternatives? You can use the data structures you are used to just fine, thanks. Just because everything is immutable by default doesn't mean everything is immutable all the time. In addition, any "unsafety" is generally buried deep inside a library and contained properly. Yes, if you are trying to implement something like a ConcurrentSkipListMap, you're probably going to have "unsafe" in your code (and probably some assembly language). But, if you are using the library, probably not.
rkangel 11y ago
Implementing data structures is considered an 'advanced' topic in Rust. That's ok for two reasons: 1) The data structures you'll need for most scenarios are in the standard library. The data structures you'll need for pretty much every scenario anyone has ever encountered in Rust are on crates.io. It should be relatively rare that you need to write one. 2) Writing data structures IS an advanced topic. The fact that you have trouble with the borrow checker trying to implement them highlights that understanding data ownership can get very complicated. Plus there's usually lots of corner cases to get tripped up in (I can't tell you how many times I've had to debug issues causes with crap implementations of circular buffers in C). And when you do need to write a data structure - unsafe is there to allow you to do it. And given Rusts type system, you can write that data structure once, make REALLY sure you got the unsafe bits right and then hide it behind a beautiful abstraction and never think of it again.

by TillE 11y ago

Gankro 11y ago

You can express data structures safely perfectly fine in Rust as long as you do all the things that make them safe in every other language -- aggressively garbage collect, indirect, and runtime validate. I'm not aware of any language that lets you implement an interesting high performance data structure totally safely. Heck, Rust is impressive because you can encode singly-linked-stack and binary-tree-without-parent-pointers efficiently and safely without garbage collection! You can even build iterators that are statically verified to iterate over every element at most once, and statically guaranteed to not be invalidated. Type systems that are powerful enough to ensure the safety of even moderately complex designs (doubly linked list, tree with parent pointers, singly linked stack, hashmap) appear to be unwieldy and relegated to academia.

catnaroek 11y ago
> even moderately complex designs (doubly linked list, tree with parent pointers, singly linked stack, hashmap) In other words, imperative data structures? My experience with implementing custom data structures in Rust: (0) Purely functional data structures: You don't even need borrows to express them. The main downsides are: poor locality of reference, inability to parameterize the data structure over whether its nodes are uniquely owned or reference counted. HKTs would fix the latter. (1) Imperative data structures: Not even mutable borrows will help you. You just need to drop down to `unsafe` code.
- Gankro 11y ago
  More or less. Hence why high performance data structures are invariably unsafe to implement in every language if they can be implemented at all. Rust lets you implement them, and for almost all of them you can even expose a safe high-performance interface to them. The only major exceptions I know for interfaces are * intrusive data structures that just blindly point to random data lying on the stack or stored in other types (a construct like C++ move constructors is necessary to safely manipulate these). * priority queues with high-performance decrease-key (you effectively need to hand clients a pointer to every node, that they can always pass back to you to deref and update the structure from -- this is unsound if that node has been popped and you aren't using a GC scheme).
  - eridius 11y ago
    I have no idea what a "priority queue with high-performance decrease-key" is, but from your brief description, you can't replace the "pointer to every node" with a RAII value that keeps the node from being deallocated?
    - Gankro 11y ago
      Yes, that's garbage collection. :)
      - eridius 11y ago
        Ah so you're defining reference-counting as garbage collection?
        Gankro 11y ago
        Absolutely. I don't find the distinction to be particularly meaningful in this case.
        blaisio 11y ago
        Reference counting is a form of garbage collection.
  - catnaroek 11y ago
    Certainly a safe interface is better than none, but unsafe and/or inefficient implementations are just symptoms of expressiveness issues, not a fact of life. That being said, what Rust has is already a strict improvement over not even being able to state how ephemeral data structures can be safely used. Also, establishing the safety of code that manipulates arrays (without runtime bounds checks), cyclical data structures (e.g. doubly-linked lists) and user-defined forms of indirection (e.g. hashing) is probably best done using tools other than unification-based type checkers.

pcwalton 11y ago

Let's not exaggerate the problem. First of all, non-lexical lifetimes have nothing to do with doubly linked lists (what you're referring to). Second, the language is clearly generally usable, as evidenced by the hundreds of thousands of lines of code written in it, most of which was written by people who have never touched the compiler. The reason is simple: most people get by just fine with the rich set of generic collections available in the standard library and on crates.io. For cases in which those aren't sufficient, you write unsafe code or use Rc. Nobody claims Golang is "generally unusable" because you can't implement your own generic data structures. That it's harder than in unsafe C or C++ to implement doubly linked lists in Rust is just a less severe version of the same kind of thing.

rectang 11y ago

I'm just learning Rust and this is the primary question I have: If I can't use the data structures I'm accustomed to (because of mutability issues), what are the alternatives? Where are the articles describing those alternatives? I've seen a lot of interesting discourse about the low-level stuff (e.g. error handling), but not higher-level "start here" approaches.

deleted 11y ago
[deleted]
bsder 11y ago
> If I can't use the data structures I'm accustomed to (because of mutability issues), what are the alternatives? You can use the data structures you are used to just fine, thanks. Just because everything is immutable by default doesn't mean everything is immutable all the time. In addition, any "unsafety" is generally buried deep inside a library and contained properly. Yes, if you are trying to implement something like a ConcurrentSkipListMap, you're probably going to have "unsafe" in your code (and probably some assembly language). But, if you are using the library, probably not.

rkangel 11y ago

Implementing data structures is considered an 'advanced' topic in Rust. That's ok for two reasons: 1) The data structures you'll need for most scenarios are in the standard library. The data structures you'll need for pretty much every scenario anyone has ever encountered in Rust are on crates.io. It should be relatively rare that you need to write one. 2) Writing data structures IS an advanced topic. The fact that you have trouble with the borrow checker trying to implement them highlights that understanding data ownership can get very complicated. Plus there's usually lots of corner cases to get tripped up in (I can't tell you how many times I've had to debug issues causes with crap implementations of circular buffers in C). And when you do need to write a data structure - unsafe is there to allow you to do it. And given Rusts type system, you can write that data structure once, make REALLY sure you got the unsafe bits right and then hide it behind a beautiful abstraction and never think of it again.