3 ms·
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 garba
by Gankro 10y 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 10y 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 10y agoMore 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 10y agoI 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?
- catnaroek 10y agoCertainly 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.