3 ms·

I think the argument of locality and linearity and cache hits is valid, but specific for one access pattern: reading items in order and adding to the tail. If t

I think the argument of locality and linearity and cache hits is valid, but specific for one access pattern: reading items in order and adding to the tail. If that's what your code ends up doing most of the time, then an array wins over a linked list hands down. As soon as you start adding or deleting items in the middle, the game changes because the data you need to move is not contained in the cache anymore (except for small arrays). I can even imagine a workflow that uses both data structures: an app could build up a linked list with the data it reads from an external file, for example, where they can be scattered and not in order; when the file is finally closed, the data are considered read-only and rearranged into an array for the remaining part of the execution. So don't dismiss linked lists as inefficient "a priori", which is exactly what antirez claims in the article.

tsimionescu 4y ago
That analysis is lacking. Linked lists turn out to be inferior to arrays for essentially any access pattern, at least when the linked list can be assumed to be randomly stored and not accidentally sorted. Say you want to add an element in the middle of an N-element ll/array. For the linked list, this means you need to do 2 * N/2 memory reads (read value, read next pointer), which will mean on average N/2 cache misses, to reach the element at index N/2. Then you'll do O(1) operations to add your new element. So, overall you've done O(N) operations and incurred O(N) cache misses. For an array, there are two cases: 1. In the happy case, you'll be able to re-alloc the array in-place, and then you'll have to move N/2 elements one to the left to make room for your new element. You'll incur one cache miss to read the start of the array, and one cache miss to read the middle of the array, and one cache miss for realloc() to check if there is enough space. The move itself will not incur any more cache misses, since your memory access pattern is very predictable. So, overall you've done O(N) operations, but incurred only O(1) cache misses - a clear win over the linked list case. 2. Unfortunately, sometimes there is no more room to expand the array in place, and you actually have to move the entire array to a new place. Here you'll have to move N elements instead of N/2, but you'll still incur only 1 cache miss for the same reason as above. Given the massive difference between a cache miss and a memory access, doing N operations with 1 cache miss should easily be faster than doing N/2 operations with N/2 cache misses. The only access patterns where the linked list should be expected to have an advantage are cases where you are adding elements very close to an element which you already have "in hand" (e.g. at the head, or at the tail if you also keep a pointer to the tale, or to the current element if you're traversing the list while modifying it). In those cases, the linked list would need O(1) operations and cache misses, while the array would need O(N) operations and O(1) cache misses, so it would start to lose out.
- teo_zero 4y ago
  > The only access patterns where the linked list should be expected to have an advantage are... Exactly my point: such access patterns exist.

tsimionescu 4y ago

That analysis is lacking. Linked lists turn out to be inferior to arrays for essentially any access pattern, at least when the linked list can be assumed to be randomly stored and not accidentally sorted. Say you want to add an element in the middle of an N-element ll/array. For the linked list, this means you need to do 2 * N/2 memory reads (read value, read next pointer), which will mean on average N/2 cache misses, to reach the element at index N/2. Then you'll do O(1) operations to add your new element. So, overall you've done O(N) operations and incurred O(N) cache misses. For an array, there are two cases: 1. In the happy case, you'll be able to re-alloc the array in-place, and then you'll have to move N/2 elements one to the left to make room for your new element. You'll incur one cache miss to read the start of the array, and one cache miss to read the middle of the array, and one cache miss for realloc() to check if there is enough space. The move itself will not incur any more cache misses, since your memory access pattern is very predictable. So, overall you've done O(N) operations, but incurred only O(1) cache misses - a clear win over the linked list case. 2. Unfortunately, sometimes there is no more room to expand the array in place, and you actually have to move the entire array to a new place. Here you'll have to move N elements instead of N/2, but you'll still incur only 1 cache miss for the same reason as above. Given the massive difference between a cache miss and a memory access, doing N operations with 1 cache miss should easily be faster than doing N/2 operations with N/2 cache misses. The only access patterns where the linked list should be expected to have an advantage are cases where you are adding elements very close to an element which you already have "in hand" (e.g. at the head, or at the tail if you also keep a pointer to the tale, or to the current element if you're traversing the list while modifying it). In those cases, the linked list would need O(1) operations and cache misses, while the array would need O(N) operations and O(1) cache misses, so it would start to lose out.

teo_zero 4y ago
> The only access patterns where the linked list should be expected to have an advantage are... Exactly my point: such access patterns exist.