6 ms·

Theoretically expensive, but modern hardware is optimized for this case. Random access lookups and cache misses from the linked list will tank performance, even

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?
    - staticassertion 5y ago
      Sure, it's just a mark and sweep, but manually implemented (which is fine).
    - masklinn 5y ago
      It’s completely normal to have this sort of things in low-level code bases. Both C++ and Rust have refcounting smart pointers in their standard libraries, and bespoke refcounting schemes are regular occurrences in C codebases (the Linux kernel has tons of refcounting, so much so that it has a utility file for reference counters: https://github.com/torvalds/linux/blob/master/include/linux/refcount.h https://github.com/torvalds/linux/blob/master/include/linux/...)
      - mousepilot 5y ago
        thanks for the response! I'm a big fan of doubly linked lists, so it was interesting to see that there was extra work to get them going. I'm certainly going to read up on this "ownership" thing. I get the impression that its there for really good reasons, and I'm not going to argue with experts who are protecting users. I have a question for you, would you say that the increase of difficulties with doubly linked lists are incidental in nature, or is there something inherent with doubly linked lists that impact security? Like I said, I like the doubly linked lists for certain things, and the more I know about the impact of using them the better! I certainly will be reading up on this!
  - staticassertion 5y ago
    Or a Vec<T> for storage and a Vec<usize> for tombstoning. Lots of ways to solve this, and my experience is that you can beat a linked list approach with the 'Vec plus Vec' approach for a lot of data sizes/ operations. Or a custom Vec that has a lower maximum bound, at which point you can start doing things like integer encoding/ pointer swizzling.
- kllrnohj 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. It takes almost no time at all to do that, depending on the size of the elements. But you have a starting assumption there that the vector must always be stored sorted. Challenge that assumption. If insertion is perfectly balanced with traversal it may be true, but that's also rarely the case. It's fairly trivial to instead track if the vector is already sorted or not & sort when sorted access is actually needed. > Besides, linked lists aren't that bad if the nodes are close enough in memory (read: consecutive) Which doesn't really happen outside of a controlled benchmark. If the linked list is stored in a single consecutive allocation, then resizing has observable side effects (eg, pointers to elements become invalidated). You can do things like allocate chunks at a time so that some elements are consecutive, but you won't have all elements consecutive or close in memory.
  - titzer 5y ago
    >> you need to copy 500 of them > It takes almost no time at all to do that, Uh, 500 loads and dependent stores, at minimum, in the best case hitting L1 cache, which is 3 cycles. So you are talking about 1500 cycles to....avoid a single cache line miss due to chasing a linked list pointer? A miss to main memory is 100-200 cycles, maximum. More likely you are going to L2/L1 which is 12-50 cycles. So no, in no circumstances would I expect copying 500 elements to be faster than chasing a single pointer. > Challenge that assumption. You don't get to pick the application behavior. If it needs to a do a lot of inserts and traversals, it just does. >> are close enough in memory (read: consecutive) > Which doesn't really happen outside of a controlled benchmark. There is no supporting information for this statement at all. Of course a list created all at once using a bump-pointer allocator is going to be consecutive. And a (moving) garbage collector is going to dynamically reorganize the nodes of a list, generally in a breadth-first way, depending on the marking algorithm. That can result in the nodes of the list being laid out consecutively after compacting, no matter where they were originally organized. Memory behavior of programs is complicated. I find it surprising that we're having a conversation that we can't or shouldn't use linked lists now because vectors are universally better, or we can lazy sort or some other crazy workaround. I'm not sure what motivates this whole line of argumentation. Sometimes lists are just the best damn thing.
volta83 5y ago
Nobody here is talking about vectors of integers. From the first post, this is all assuming that the objects in the vector are "big". A modern CPU has 200Gb/s of bandwidth. If the objects in your array are 200 Gb in size each, then swapping the position of two elements in a vector is going to take O(seconds) at memcpy speeds, while doing this with a linked list is going to take ~1 * 10^(-11) seconds. That's a performance difference of 11 orders of magnitude... You can make the objects in the array smaller (e.g. 200Mb each instead of 200Gb each) and your two-element swap would still be 10^8 times faster with a doubly linked list. --- In the parallel threads, people seem to just be arguing that a vector is always faster than a list, without understanding "why" this is the case, and making claims about "what the hardware does" without doing basic rule-of-thumb calculations to verify their claims.
- myrrlyn 5y ago
  the good news is that a vector of any object can be reduced to a vector of integers by `Box`ing, and then you only incur a miss when you access the data, but not during every step you take to find the data
- kd5bjo 5y ago
  > A modern CPU has 200Gb/s of bandwidth. If the objects in your array are 200 Gb in size each, then swapping the position of two elements in a vector is going to take O(seconds) at memcpy speeds, Not necessarily. If those items are aligned to a memory-page boundary, memcpy will probably do a page table update instead of actually moving the values in RAM.

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?
  - staticassertion 5y ago
    Sure, it's just a mark and sweep, but manually implemented (which is fine).
  - masklinn 5y ago
    It’s completely normal to have this sort of things in low-level code bases. Both C++ and Rust have refcounting smart pointers in their standard libraries, and bespoke refcounting schemes are regular occurrences in C codebases (the Linux kernel has tons of refcounting, so much so that it has a utility file for reference counters: https://github.com/torvalds/linux/blob/master/include/linux/refcount.h https://github.com/torvalds/linux/blob/master/include/linux/...)
    - mousepilot 5y ago
      thanks for the response! I'm a big fan of doubly linked lists, so it was interesting to see that there was extra work to get them going. I'm certainly going to read up on this "ownership" thing. I get the impression that its there for really good reasons, and I'm not going to argue with experts who are protecting users. I have a question for you, would you say that the increase of difficulties with doubly linked lists are incidental in nature, or is there something inherent with doubly linked lists that impact security? Like I said, I like the doubly linked lists for certain things, and the more I know about the impact of using them the better! I certainly will be reading up on this!
- staticassertion 5y ago
  Or a Vec<T> for storage and a Vec<usize> for tombstoning. Lots of ways to solve this, and my experience is that you can beat a linked list approach with the 'Vec plus Vec' approach for a lot of data sizes/ operations. Or a custom Vec that has a lower maximum bound, at which point you can start doing things like integer encoding/ pointer swizzling.
kllrnohj 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. It takes almost no time at all to do that, depending on the size of the elements. But you have a starting assumption there that the vector must always be stored sorted. Challenge that assumption. If insertion is perfectly balanced with traversal it may be true, but that's also rarely the case. It's fairly trivial to instead track if the vector is already sorted or not & sort when sorted access is actually needed. > Besides, linked lists aren't that bad if the nodes are close enough in memory (read: consecutive) Which doesn't really happen outside of a controlled benchmark. If the linked list is stored in a single consecutive allocation, then resizing has observable side effects (eg, pointers to elements become invalidated). You can do things like allocate chunks at a time so that some elements are consecutive, but you won't have all elements consecutive or close in memory.
- titzer 5y ago
  >> you need to copy 500 of them > It takes almost no time at all to do that, Uh, 500 loads and dependent stores, at minimum, in the best case hitting L1 cache, which is 3 cycles. So you are talking about 1500 cycles to....avoid a single cache line miss due to chasing a linked list pointer? A miss to main memory is 100-200 cycles, maximum. More likely you are going to L2/L1 which is 12-50 cycles. So no, in no circumstances would I expect copying 500 elements to be faster than chasing a single pointer. > Challenge that assumption. You don't get to pick the application behavior. If it needs to a do a lot of inserts and traversals, it just does. >> are close enough in memory (read: consecutive) > Which doesn't really happen outside of a controlled benchmark. There is no supporting information for this statement at all. Of course a list created all at once using a bump-pointer allocator is going to be consecutive. And a (moving) garbage collector is going to dynamically reorganize the nodes of a list, generally in a breadth-first way, depending on the marking algorithm. That can result in the nodes of the list being laid out consecutively after compacting, no matter where they were originally organized. Memory behavior of programs is complicated. I find it surprising that we're having a conversation that we can't or shouldn't use linked lists now because vectors are universally better, or we can lazy sort or some other crazy workaround. I'm not sure what motivates this whole line of argumentation. Sometimes lists are just the best damn thing.

volta83 5y ago

Nobody here is talking about vectors of integers. From the first post, this is all assuming that the objects in the vector are "big". A modern CPU has 200Gb/s of bandwidth. If the objects in your array are 200 Gb in size each, then swapping the position of two elements in a vector is going to take O(seconds) at memcpy speeds, while doing this with a linked list is going to take ~1 * 10^(-11) seconds. That's a performance difference of 11 orders of magnitude... You can make the objects in the array smaller (e.g. 200Mb each instead of 200Gb each) and your two-element swap would still be 10^8 times faster with a doubly linked list. --- In the parallel threads, people seem to just be arguing that a vector is always faster than a list, without understanding "why" this is the case, and making claims about "what the hardware does" without doing basic rule-of-thumb calculations to verify their claims.

myrrlyn 5y ago
the good news is that a vector of any object can be reduced to a vector of integers by `Box`ing, and then you only incur a miss when you access the data, but not during every step you take to find the data
kd5bjo 5y ago
> A modern CPU has 200Gb/s of bandwidth. If the objects in your array are 200 Gb in size each, then swapping the position of two elements in a vector is going to take O(seconds) at memcpy speeds, Not necessarily. If those items are aligned to a memory-page boundary, memcpy will probably do a page table update instead of actually moving the values in RAM.