4 ms·

Linked list strikes again.

by filiphorvat 4y ago

MuffinFlavored 4y ago
Is there not a way to do safe linked lists in Rust?
- msdrigg 4y ago
  You can do a singly linked list just fine. But with a doubly linked list, who owns the memory to each node? In reality, you can do a doubly linked list with something like `RefCell`. See the famous blog post on linked lists in rust here: https://rust-unofficial.github.io/too-many-lists/fourth-building.html https://rust-unofficial.github.io/too-many-lists/fourth-buil...
  - deleted 4y ago
    [deleted]
- howinteresting 4y ago
  Because of cache locality issues, linked lists are a bad data structure for almost all purposes. A plain old vector, or maybe a VecDeque, wins for almost all workloads. For the few times they are useful (e.g. if you're writing lock-free algorithms, you want a hard upper bound O(1) append rather than just amortized O(1) append, or you don't have malloc available), Rust is a fine language to write them in. But also there are plenty of high-quality libraries on crates.io, so you probably won't have to write your own.
- jackpeterfletch 4y ago
  The borrow checker makes a doublily linked list difficult, from my understanding. They're almost always a bad data structure to pick though, as the speed difference between being able to iterate a contiguous list, and even completely rebuild it, vs having to follow arbitrary pointers mean that the 'complexity' improvements of a linked list often become irrelevant. ------ Open Question) I have this intuition that the borrow checker might enforce a way of working that fundamentally stops you from doing things that aren't _really_ compatible with the way a CPU actually works on the lowest level. Is there any credence to that, and if so, is it happenstance, or is there some more fundamental reason?
  - kaba0 4y ago
    > I have this intuition that the borrow checker might enforce a way of working that fundamentally stops you from doing things that aren't _really_ compatible with the way a CPU actually works on the lowest level. No, I think you are reading too much into it. One is free to Box-allocate/pointer-chase on every line in Rust without any trouble. Sure, as other low level languages, rust also prefers/makes stack-allocation more ergonomic/the default, which is a quite cache-friendly way of operation but not even the stack is “native” in and of itself - it is just a frequently and extensively used part of the “heap”.

Linked list strikes again.

MuffinFlavored 4y ago

Is there not a way to do safe linked lists in Rust?

msdrigg 4y ago
You can do a singly linked list just fine. But with a doubly linked list, who owns the memory to each node? In reality, you can do a doubly linked list with something like `RefCell`. See the famous blog post on linked lists in rust here: https://rust-unofficial.github.io/too-many-lists/fourth-building.html https://rust-unofficial.github.io/too-many-lists/fourth-buil...
- deleted 4y ago
  [deleted]
howinteresting 4y ago
Because of cache locality issues, linked lists are a bad data structure for almost all purposes. A plain old vector, or maybe a VecDeque, wins for almost all workloads. For the few times they are useful (e.g. if you're writing lock-free algorithms, you want a hard upper bound O(1) append rather than just amortized O(1) append, or you don't have malloc available), Rust is a fine language to write them in. But also there are plenty of high-quality libraries on crates.io, so you probably won't have to write your own.
jackpeterfletch 4y ago
The borrow checker makes a doublily linked list difficult, from my understanding. They're almost always a bad data structure to pick though, as the speed difference between being able to iterate a contiguous list, and even completely rebuild it, vs having to follow arbitrary pointers mean that the 'complexity' improvements of a linked list often become irrelevant. ------ Open Question) I have this intuition that the borrow checker might enforce a way of working that fundamentally stops you from doing things that aren't _really_ compatible with the way a CPU actually works on the lowest level. Is there any credence to that, and if so, is it happenstance, or is there some more fundamental reason?
- kaba0 4y ago
  > I have this intuition that the borrow checker might enforce a way of working that fundamentally stops you from doing things that aren't _really_ compatible with the way a CPU actually works on the lowest level. No, I think you are reading too much into it. One is free to Box-allocate/pointer-chase on every line in Rust without any trouble. Sure, as other low level languages, rust also prefers/makes stack-allocation more ergonomic/the default, which is a quite cache-friendly way of operation but not even the stack is “native” in and of itself - it is just a frequently and extensively used part of the “heap”.