5 ms·

If your primary operation is inserting at a random location in the list, linked lists are faster than arrays at large sizes. You avoid having to move all the me

If your primary operation is inserting at a random location in the list, linked lists are faster than arrays at large sizes. You avoid having to move all the memory after the index you are modifying (to make space for the inserted element). A linked list also avoids copying the entire array when you need to insert more elements than you have allocated space for.

cma 6y ago
Depends on element size and some other stuff, but if it is a singly linked list, and truely random insertion location, iterating to that location is N/2 on average, where inserting and copying the rest of the array is also N/2. Small elements and the array could still be much faster since they are all prefetched during the copy, vs jumping all over memory during the list iteration and potentially stalling on each for ~200 instructions waiting on main memory.
- saagarjha 6y ago
  You can imagine a linked list whose “API” is “take this node and insert after it”.
  - cma 6y ago
    If a bunch of insertions happen like that, based on some other data structure, and then a periodic iteration eventually happens at some point, you could also imagine an array version being batching together all the array inserts in another simple array and applying them all at once before iteration.
whimsicalism 6y ago
B-tree would be faster than either
reificator 6y ago
> If your primary operation is inserting at a random location in the list, linked lists are faster than arrays at large sizes. You avoid having to move all the memory after the index you are modifying (to make space for the inserted element). This is false. Big O notation says it should be true, you'll get marked wrong if you say arrays are faster in your algorithms & data structures final, but when you're running on actual hardware the array is faster at all sizes of n and as n becomes larger so does the gap in performance. Here is a talk[0] by Bjarne Stroustrop (Creator of C++) that even includes imaginary graphs demonstrating this phenomenon. If you want a visual for what the missing graph was supposed to look like, here's a similar one.[1] Here's another video[2] by Scott Meyers (Author of Effective C++) that goes into more detail about why this happens. [0]: https://www.youtube.com/watch?v=YQs6IC-vgmo https://www.youtube.com/watch?v=YQs6IC-vgmo [1]: https://airspeedvelocity.files.wordpress.com/2015/08/pasted_image_8_2_15__1_17_pm.png https://airspeedvelocity.files.wordpress.com/2015/08/pasted_... [2]: https://www.youtube.com/watch?v=WDIkqP4JbkE https://www.youtube.com/watch?v=WDIkqP4JbkE
- jodrellblank 6y ago
  Summary of the Stroustrop video - inserting or removing an item at a point in an array of 100k items needs a linear scan from the start of the data structure to get to the point - an array does that very quickly, a linked list is much slower, lots of random memory indirection, a pointer for every list node blowing out the cache - in practice this linear scan to to the change point dominates the runtime, and arrays come out much faster. While the array change does need on average 50k items to be shuffled up to make room or close the gap, modern caches are very good at that. If the array is sorted it can be binary searched to get to the change point, which improves its performance even more, linked lists can’t do that. Interesting.
  - tmd83 6y ago
    I can definitely see in modern cpu array scanning being faster than pointer chasing but I wouldn't have expected that to survive insertion with 50K move wow! And if you not doing ordered insertion you wouldn't have to move the data in the array anyway, you would keep track of the size and jump to the end, so not sure I understand the binary search comment. The next question is at what level of growth the waste of empty space in the array becomes too much. Some kind of data structure (tree/linked list) with largish (whatever size applicable for modern cpu) as probably mentioned in other comments does seem the most versatile approach while keeping the performance. Or perhaps the handling of that data structure might overwhelm the array advantage?
    - reificator 6y ago
      > > If the array is sorted it can be binary searched to get to the change point, which improves its performance even more, linked lists can’t do that. > And if you not doing ordered insertion you wouldn't have to move the data in the array anyway, you would keep track of the size and jump to the end, so not sure I understand the binary search comment. It just means that if I want to view the nth element of an array, that's a constant time operation. I just take the pointer and add n times the size of the elements. But for a linked list if I want to view the nth element of the list, I have to view the (n-1)th element first, all the way back until the first element I have a reference to. > The next question is at what level of growth the waste of empty space in the array becomes too much. Everything I've tried and everything I've seen from people testing on real hardware is that the gap in performance widens with larger values of n. You might expect different performance as the system runs out of memory. But arrays have a size of n * element size, and linked lists have a size of n * (pointer(s) + element size), so the linked list would hit memory limitations more quickly regardless.

cma 6y ago

Depends on element size and some other stuff, but if it is a singly linked list, and truely random insertion location, iterating to that location is N/2 on average, where inserting and copying the rest of the array is also N/2. Small elements and the array could still be much faster since they are all prefetched during the copy, vs jumping all over memory during the list iteration and potentially stalling on each for ~200 instructions waiting on main memory.

saagarjha 6y ago
You can imagine a linked list whose “API” is “take this node and insert after it”.
- cma 6y ago
  If a bunch of insertions happen like that, based on some other data structure, and then a periodic iteration eventually happens at some point, you could also imagine an array version being batching together all the array inserts in another simple array and applying them all at once before iteration.

whimsicalism 6y ago

B-tree would be faster than either

reificator 6y ago

> If your primary operation is inserting at a random location in the list, linked lists are faster than arrays at large sizes. You avoid having to move all the memory after the index you are modifying (to make space for the inserted element). This is false. Big O notation says it should be true, you'll get marked wrong if you say arrays are faster in your algorithms & data structures final, but when you're running on actual hardware the array is faster at all sizes of n and as n becomes larger so does the gap in performance. Here is a talk[0] by Bjarne Stroustrop (Creator of C++) that even includes imaginary graphs demonstrating this phenomenon. If you want a visual for what the missing graph was supposed to look like, here's a similar one.[1] Here's another video[2] by Scott Meyers (Author of Effective C++) that goes into more detail about why this happens. [0]: https://www.youtube.com/watch?v=YQs6IC-vgmo https://www.youtube.com/watch?v=YQs6IC-vgmo [1]: https://airspeedvelocity.files.wordpress.com/2015/08/pasted_image_8_2_15__1_17_pm.png https://airspeedvelocity.files.wordpress.com/2015/08/pasted_... [2]: https://www.youtube.com/watch?v=WDIkqP4JbkE https://www.youtube.com/watch?v=WDIkqP4JbkE

jodrellblank 6y ago
Summary of the Stroustrop video - inserting or removing an item at a point in an array of 100k items needs a linear scan from the start of the data structure to get to the point - an array does that very quickly, a linked list is much slower, lots of random memory indirection, a pointer for every list node blowing out the cache - in practice this linear scan to to the change point dominates the runtime, and arrays come out much faster. While the array change does need on average 50k items to be shuffled up to make room or close the gap, modern caches are very good at that. If the array is sorted it can be binary searched to get to the change point, which improves its performance even more, linked lists can’t do that. Interesting.
- tmd83 6y ago
  I can definitely see in modern cpu array scanning being faster than pointer chasing but I wouldn't have expected that to survive insertion with 50K move wow! And if you not doing ordered insertion you wouldn't have to move the data in the array anyway, you would keep track of the size and jump to the end, so not sure I understand the binary search comment. The next question is at what level of growth the waste of empty space in the array becomes too much. Some kind of data structure (tree/linked list) with largish (whatever size applicable for modern cpu) as probably mentioned in other comments does seem the most versatile approach while keeping the performance. Or perhaps the handling of that data structure might overwhelm the array advantage?
  - reificator 6y ago
    > > If the array is sorted it can be binary searched to get to the change point, which improves its performance even more, linked lists can’t do that. > And if you not doing ordered insertion you wouldn't have to move the data in the array anyway, you would keep track of the size and jump to the end, so not sure I understand the binary search comment. It just means that if I want to view the nth element of an array, that's a constant time operation. I just take the pointer and add n times the size of the elements. But for a linked list if I want to view the nth element of the list, I have to view the (n-1)th element first, all the way back until the first element I have a reference to. > The next question is at what level of growth the waste of empty space in the array becomes too much. Everything I've tried and everything I've seen from people testing on real hardware is that the gap in performance widens with larger values of n. You might expect different performance as the system runs out of memory. But arrays have a size of n * element size, and linked lists have a size of n * (pointer(s) + element size), so the linked list would hit memory limitations more quickly regardless.