5 ms·

There are some good thoughts concerning when to use a linked list here: https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-

There are some good thoughts concerning when to use a linked list here: https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/

brundolf 5y ago
Your link talks about the general case. For better or worse, (most) Lisps give linked-list operations a special status as a fundamental primitive. For example, getting the tail of a list over and over is commonly used for iterating through its elements. If you try and do this with a Vec you'll be copying and re-allocating almost the whole thing on every loop iteration. Nothing about Lisp requires that you write code this way of course, but it's the epitome of what could be called "Lispy" (literally: "list processing language"), and any preexisting code or habits will hit a brick wall if those lists are implemented as Vecs
- dgb23 5y ago
  To add, Clojure uses a sequence interface that is typically backed by a vector. Conj (instead of cons) is used to derive a new sequence with the thing added in front for lists (which are rarely used) and at the back for vectors.
  - brundolf 5y ago
    It supports both, as it should; Lists are still first-class citizens, it's just that vectors are too. Though also in Clojure's case vectors aren't really vectors, they're immutable persistent data structures that share memory as much as possible, which I think would actually solve most of the performance problem here. But the same is not true of Rust's Vec<>
    - nerpderp82 5y ago
      https://github.com/bodil/im-rs https://github.com/bodil/im-rs
      - brundolf 5y ago
        I'm solely commenting on the implementation in the OP, which uses a regular Vec<>
    - fulafel 5y ago
      Both are supported, but people rarely use lists in normal code IME - just in macros or other syntax representations (eg Datalog).
- tialaramex 5y ago
  > you'll be copying and re-allocating almost the whole thing on every loop iteration. This is true if the list is writeable, but, if so surely a Lisp has to also keep duplicating the list or else it will get into trouble? For reading the list why shouldn't Rust use a slice of the vector? The slice can't own anything, but that's OK, we aren't changing anything. The slice is very cheap, it's basically a pointer into the vector plus a length count.
  - brundolf 5y ago
    > surely a Lisp has to also keep duplicating the list or else it will get into trouble? Nope, it doesn't traditionally duplicate the list. It certainly is possible to get into trouble in your logic, but those are the presented semantics, and debating their virtue is out of scope > why shouldn't Rust use a slice of the vector? You're gonna get into ownership-hell if you can't give a separate Rc to each list tail, because those can get passed around wherever
    - wizzwizz4 5y ago
      That's what Cow is for, surely?
      - brundolf 5y ago
        For the ownership thing? No, I don't think so. I haven't done much with Cow but my understanding is it doesn't do anything to help with cases where you have "multiple owners" of a value. It might allow you to use a slice up until it needs to be cloned, but you'll still have to clone it at that point.
        tialaramex 5y ago
        Unlike the slice, a Cow made from that slice can be Owned. Unlike reference counting the underlying Vector, the Cow won't duplicate the slice until you modify it. This forces you to confront the reality you'd been dodging. Either you actually mutate this list in your program, and the "magic" of linked lists dissolves when it consumes all your memory, or as seems far more likely you get good performance from the better underlying data structure anyway and the "magic" of linked lists dissolves that way. You only get good performance from linked lists today on the rare occasion when their lack of data locality is outweighed by some other factor. Sprinkling the Lisp idiom over things doesn't change that. Here's an example where it's worth it: In highly concurrent systems you can't afford to use any sort of locking to protect data structures, the contention for the locks hurts too much, and you can't afford to reference count everything in those structures because even the contention on the reference counts also costs too much (everything looking at an item is storing to the reference count). So you use Hazard Pointers to avoid prematurely dropping anything. But any type of locking for your Hazard Pointers structure would have too much contention also, so you store the Hazard Pointers in a linked list, new ones can be slotted into place at the start of the list with an atomic compare-exchange. Each CPU core is writing to the Hazard Pointers it "owns" a lot, but they're deliberately too big to share with another CPU's cache, and any CPU cores that need to check the Hazard Pointers read from them all but never write so modern caches cope admirably.

There are some good thoughts concerning when to use a linked list here: https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/

brundolf 5y ago

Your link talks about the general case. For better or worse, (most) Lisps give linked-list operations a special status as a fundamental primitive. For example, getting the tail of a list over and over is commonly used for iterating through its elements. If you try and do this with a Vec you'll be copying and re-allocating almost the whole thing on every loop iteration. Nothing about Lisp requires that you write code this way of course, but it's the epitome of what could be called "Lispy" (literally: "list processing language"), and any preexisting code or habits will hit a brick wall if those lists are implemented as Vecs

dgb23 5y ago
To add, Clojure uses a sequence interface that is typically backed by a vector. Conj (instead of cons) is used to derive a new sequence with the thing added in front for lists (which are rarely used) and at the back for vectors.
- brundolf 5y ago
  It supports both, as it should; Lists are still first-class citizens, it's just that vectors are too. Though also in Clojure's case vectors aren't really vectors, they're immutable persistent data structures that share memory as much as possible, which I think would actually solve most of the performance problem here. But the same is not true of Rust's Vec<>
  - nerpderp82 5y ago
    https://github.com/bodil/im-rs https://github.com/bodil/im-rs
    - brundolf 5y ago
      I'm solely commenting on the implementation in the OP, which uses a regular Vec<>
  - fulafel 5y ago
    Both are supported, but people rarely use lists in normal code IME - just in macros or other syntax representations (eg Datalog).
tialaramex 5y ago
> you'll be copying and re-allocating almost the whole thing on every loop iteration. This is true if the list is writeable, but, if so surely a Lisp has to also keep duplicating the list or else it will get into trouble? For reading the list why shouldn't Rust use a slice of the vector? The slice can't own anything, but that's OK, we aren't changing anything. The slice is very cheap, it's basically a pointer into the vector plus a length count.
- brundolf 5y ago
  > surely a Lisp has to also keep duplicating the list or else it will get into trouble? Nope, it doesn't traditionally duplicate the list. It certainly is possible to get into trouble in your logic, but those are the presented semantics, and debating their virtue is out of scope > why shouldn't Rust use a slice of the vector? You're gonna get into ownership-hell if you can't give a separate Rc to each list tail, because those can get passed around wherever
  - wizzwizz4 5y ago
    That's what Cow is for, surely?
    - brundolf 5y ago
      For the ownership thing? No, I don't think so. I haven't done much with Cow but my understanding is it doesn't do anything to help with cases where you have "multiple owners" of a value. It might allow you to use a slice up until it needs to be cloned, but you'll still have to clone it at that point.
      - tialaramex 5y ago
        Unlike the slice, a Cow made from that slice can be Owned. Unlike reference counting the underlying Vector, the Cow won't duplicate the slice until you modify it. This forces you to confront the reality you'd been dodging. Either you actually mutate this list in your program, and the "magic" of linked lists dissolves when it consumes all your memory, or as seems far more likely you get good performance from the better underlying data structure anyway and the "magic" of linked lists dissolves that way. You only get good performance from linked lists today on the rare occasion when their lack of data locality is outweighed by some other factor. Sprinkling the Lisp idiom over things doesn't change that. Here's an example where it's worth it: In highly concurrent systems you can't afford to use any sort of locking to protect data structures, the contention for the locks hurts too much, and you can't afford to reference count everything in those structures because even the contention on the reference counts also costs too much (everything looking at an item is storing to the reference count). So you use Hazard Pointers to avoid prematurely dropping anything. But any type of locking for your Hazard Pointers structure would have too much contention also, so you store the Hazard Pointers in a linked list, new ones can be slotted into place at the start of the list with an atomic compare-exchange. Each CPU core is writing to the Hazard Pointers it "owns" a lot, but they're deliberately too big to share with another CPU's cache, and any CPU cores that need to check the Hazard Pointers read from them all but never write so modern caches cope admirably.