7 ms·

> Rust only ever allows one owner per data, so this will at least require a Rc or Arc to work. But even this becomes cumbersome quickly, not to mention the over

> Rust only ever allows one owner per data, so this will at least require a Rc or Arc to work. But even this becomes cumbersome quickly, not to mention the overhead from reference counts. This takes 50 LOC, gives you a doubly-linked list that's memory safe, thread safe, and that has pretty much the same efficiency as a doubly-linked list using raw pointers. (Feel free to prove me wrong here, but I've written one, and I couldn't measure the difference on x86, i'd expect ARM to be even better because it has weaker atomics). Compared with a Vec<T> or a HashMap<T>, what dominates the performance of a doubly-linked list is the pointer indirection to access the object, and the cost of that is pretty much the same whether you are using Arc<T>/Rc<T> or a raw pointer. Also, a doubly linked list only makes much sense for relatively large objects and when you want O(1) splice, so whether you store 64-bit or 128-bit wide pointers doesn't matter at all, because the objects are big, and O(1) splice just modifies 4 pointers...

imtringued 5y ago
Yeah, the article is weird about "But even this becomes cumbersome quickly, not to mention the overhead from reference counts." You pick the linked list because of better scalability as the data size grows bigger, you choose them precisely because you think the constant overhead vs contiguous lists is worth it. The most common example is an object that wants to remove itself from a big list. E.g. you have a OS with 10000 processes. 1000 processes die per second and they already know their position in the linked list so they remove themselves in O(1). An array would require leaving the slot empty and swapping in the last element (unordered list) O(1) or shifting entries to fill the gap (ordered list) O(n). The former breaks ordering, the latter leads to O(nm) removal costs where n is the number of live processes and m the number of dying processes. Paying reference counting costs is not a problem.
- IshKebab 5y ago
  A linked list is still a pretty terrible choice. You'd probably be better off with a Vec with tombstones and some kind of free list.
  - titzer 5y ago
    It really depends on what you are doing. If inserts into the middle are common, readjusting a vector gets really expensive.
    - rmdashrfstar 5y ago
      Theoretically expensive, but modern hardware is optimized for this case. Random access lookups and cache misses from the linked list will tank performance, even in most cases where a linked list is theoretically equivalent or preferred.
      - titzer 5y ago
        If you have a long vector, say, 1000 elements, and you need to copy 500 of them to shift them over for an insert, you are going to be very slow compared to a linked list. Besides, linked lists aren't that bad if the nodes are close enough in memory (read: consecutive), or they are hot enough to be in already in cache. But as always, measure instead of guessing.
        masklinn 5y ago
        > If you have a long vector, say, 1000 elements, and you need to copy 500 of them to shift them over for an insert, you are going to be very slow compared to a linked list. FWIW the original suggestion mentioned tombstoning so you'd have a Vec<Option<T>> instead of a `Vec<T>`, and "removing" an item would just set the `Option` to `None`. Of course this would increase iteration cost (as you'd have to skip the `None`), and you'd probably want to compact the vec once in a while.
        mousepilot 5y ago
        I probably shouldn't even be in this thread but isn't that creeping back toward garbage collection?
        5y ago
- kllrnohj 5y ago
  If objects know where they are, why do you need sorted ordering? If you need sorted ordering, it sounds like you're (regularly!) iterating over it. But iterating over a linked list is incredibly slow. This is where Big-O just really doesn't have a strong relationship with performance. Iterating over a linked-list is O(N), same as a vec. But in the real world it's nowhere close to as fast. So then if you're not regularly iterating over it a bag implemented with a vec is likely a better option. Then just have a bool that tracks if it's sorted or not, and in the (relatively) rare case you need sorted traversal just sort() it first.
  - xigoi 5y ago
    Ordered is not the same thing as sorted. If you do swap-removals, there's no way to sort the array back into the original order unless you also keep track of insertion time, which adds memory overhead.
    - kllrnohj 5y ago
      Storing pointers in a linked list also adds memory overhead, too. Insertion time in nanoseconds is only 8 bytes - same as a single pointer on 64-bits. So half the memory usage as a doubly linked list.
  - josephg 5y ago
    You can get the best of both worlds - fast iteration and fast insert speed - by using a tree. Essentially use a b-tree as a list, and in internal nodes count the number of items contained in each child. Inserts traverse down the tree to find the insert position, insert there and then traverse back up the tree updating indexes. Each leaf should contain a small array of items, and when inserting you can memmove the existing items to to make space. Tuning the size of that array lets you balance the cost of memcpy vs the cost of pointer indirection & allocations on insert. The whole construction ends up extremely efficient in practice for this kind of thing, since you get log(n) indexed lookup and log(n) insert time. I don’t know why they aren’t used more.
    - kllrnohj 5y ago
e12e 5y ago
I appreciate this comment, as there was (semi) recently som comments/posts about how linked lists in rust is hard - but this makes it sound more like "a linked list in rust looks a bit different (and is safer) than a linked list in c" (or: "rust is actually its own language, work with the grain").

imtringued 5y ago

Yeah, the article is weird about "But even this becomes cumbersome quickly, not to mention the overhead from reference counts." You pick the linked list because of better scalability as the data size grows bigger, you choose them precisely because you think the constant overhead vs contiguous lists is worth it. The most common example is an object that wants to remove itself from a big list. E.g. you have a OS with 10000 processes. 1000 processes die per second and they already know their position in the linked list so they remove themselves in O(1). An array would require leaving the slot empty and swapping in the last element (unordered list) O(1) or shifting entries to fill the gap (ordered list) O(n). The former breaks ordering, the latter leads to O(nm) removal costs where n is the number of live processes and m the number of dying processes. Paying reference counting costs is not a problem.

IshKebab 5y ago
A linked list is still a pretty terrible choice. You'd probably be better off with a Vec with tombstones and some kind of free list.
- titzer 5y ago
  It really depends on what you are doing. If inserts into the middle are common, readjusting a vector gets really expensive.
  - rmdashrfstar 5y ago
    Theoretically expensive, but modern hardware is optimized for this case. Random access lookups and cache misses from the linked list will tank performance, even in most cases where a linked list is theoretically equivalent or preferred.
    - titzer 5y ago
      If you have a long vector, say, 1000 elements, and you need to copy 500 of them to shift them over for an insert, you are going to be very slow compared to a linked list. Besides, linked lists aren't that bad if the nodes are close enough in memory (read: consecutive), or they are hot enough to be in already in cache. But as always, measure instead of guessing.
      - masklinn 5y ago
        > If you have a long vector, say, 1000 elements, and you need to copy 500 of them to shift them over for an insert, you are going to be very slow compared to a linked list. FWIW the original suggestion mentioned tombstoning so you'd have a Vec<Option<T>> instead of a `Vec<T>`, and "removing" an item would just set the `Option` to `None`. Of course this would increase iteration cost (as you'd have to skip the `None`), and you'd probably want to compact the vec once in a while.
        mousepilot 5y ago
        I probably shouldn't even be in this thread but isn't that creeping back toward garbage collection?
        5y ago
kllrnohj 5y ago
If objects know where they are, why do you need sorted ordering? If you need sorted ordering, it sounds like you're (regularly!) iterating over it. But iterating over a linked list is incredibly slow. This is where Big-O just really doesn't have a strong relationship with performance. Iterating over a linked-list is O(N), same as a vec. But in the real world it's nowhere close to as fast. So then if you're not regularly iterating over it a bag implemented with a vec is likely a better option. Then just have a bool that tracks if it's sorted or not, and in the (relatively) rare case you need sorted traversal just sort() it first.
- xigoi 5y ago
  Ordered is not the same thing as sorted. If you do swap-removals, there's no way to sort the array back into the original order unless you also keep track of insertion time, which adds memory overhead.
  - kllrnohj 5y ago
    Storing pointers in a linked list also adds memory overhead, too. Insertion time in nanoseconds is only 8 bytes - same as a single pointer on 64-bits. So half the memory usage as a doubly linked list.
- josephg 5y ago
  You can get the best of both worlds - fast iteration and fast insert speed - by using a tree. Essentially use a b-tree as a list, and in internal nodes count the number of items contained in each child. Inserts traverse down the tree to find the insert position, insert there and then traverse back up the tree updating indexes. Each leaf should contain a small array of items, and when inserting you can memmove the existing items to to make space. Tuning the size of that array lets you balance the cost of memcpy vs the cost of pointer indirection & allocations on insert. The whole construction ends up extremely efficient in practice for this kind of thing, since you get log(n) indexed lookup and log(n) insert time. I don’t know why they aren’t used more.
  - kllrnohj 5y ago

e12e 5y ago

I appreciate this comment, as there was (semi) recently som comments/posts about how linked lists in rust is hard - but this makes it sound more like "a linked list in rust looks a bit different (and is safer) than a linked list in c" (or: "rust is actually its own language, work with the grain").