4 ms·

> even moderately complex designs (doubly linked list, tree with parent pointers, singly linked stack, hashmap) In other words, imperative data structures? My

> 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.

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.