6 ms·

It's surprising people are arguing about this. That fact alone shows that lots of developers don't understand the relationship between L1/L2 cache, data access

by manv1 4y ago

It's surprising people are arguing about this. That fact alone shows that lots of developers don't understand the relationship between L1/L2 cache, data access patterns, and how prefetching works. That makes sense, given how abstract things have gotten. Decades ago there was an article that showed the penalty for non-linear data access was massive. That was before speculative access, branch prediction and cache prefetching were standard features. The performance hit today would be even more (except presumably for machines that have implemented the speculative execution security mitigations).

couchand 4y ago
As with any such subject, it's worth discussing the details but probably not the generalities really (except perhaps in the whimsical style of antirez). You're right to point out that given the performance characteristics of most modern CPUs, accessing memory linerally is optimum. But it doesn't necessarily follow that all collection data structures should be stored as a vector. Consider a collection traversed very slowly relative to the overall computation. There may not be any cache win if the line's always evicted by the time you come back to it.
- fiddlerwoaroof 4y ago
  I’ve always wondered about whether you could have your cake and eat it too with linked lists where nodes are allocated in contiguous blocks of N nodes. So, the normal case of traversing the next pointer is not a discontinuous memory access.
  - tsimionescu 4y ago
    That's quite likely to happen to a linked list when using a compacting GC (such as Java's or C#'s generational garbage collectors) (assuming the elements of the list are only reachable from the preceding element, not from many other places as well).
    - fiddlerwoaroof 4y ago
      That depends on the GC’s traversal strategy, I think. If you assume that linked lists are implemented as in lisps (a pair of pointers), then if you traverse the head pointer before the tail pointer, the compacting GC will tend to spread the linked list out over time.
pizza 4y ago
It’s hard for me to blame developers for their misaligned mental models since, as you yourself point out, the relationship between your mental model of the hardware’s behavior and what it actually does is complex and not really obvious. Mitigations etc means that the hardware you bought might totally change its behavior in the future. If all you can rely on is time measurements, it doesn’t explain that the software you wrote last year is now eg 40% slower due to bug mitigations. I think it’s easier to expect developers to put in the effort once they’re empowered with powerful tools to explain how the software gets mapped onto the hardware. I think tools that result in greater transparency at lower levels will probably emerge, something like a compiler-generated dynamic analysis + pre-flight checklist hybrid. But since it’s so low-level, it might actually affect results, which may be a problem. I think intel vtune seems interesting in that regard.
eru 4y ago
Well, ideally your programming language (and its standard library) should provide you with basic data structures that are cache oblivious (or optimized for your arrangements cache). So programmers wouldn't need to worry.
pencilguin 4y ago
The fact is that in 95+% of cases, the performance doesn't matter at all, and a linked list is fine. The only problem is that use cases evolve, and what was fine suddenly isn't, anymore.
teo_zero 4y ago
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.
simplotek 4y ago
> It's surprising people are arguing about this. That fact alone shows that lots of developers don't understand the relationship between L1/L2 cache, data access patterns, and how prefetching works. Your misconception lies in the assumption that the only conceivable use case is iterating over a preallocated data structure to do read-only operations. Once you add real world usages, with CRUD operations involving memory allocations/reallocations then your misconception about cache crumbles, and you start to understand why "people are arguing over this".
- Dylan16807 4y ago
  Which misconceptions? Messy memory allocations hurt lists even more.
- mannyv 4y ago
  You're expanding the scope of the problem. In real life nobody is pulling shit off of a database and stuffing it into a linked list. And if they are the performance will still be worse because each list will be allocated. Even if you do your own malloc you will blow cache with a linked list, because as time goes on your locality will be blown out. Iterating over a linked list will be worse as well. In fact, on modern architectures it may be faster to iterate over arrays just to take advantage of l2/l3 behaviors.

by manv1 4y ago

couchand 4y ago

As with any such subject, it's worth discussing the details but probably not the generalities really (except perhaps in the whimsical style of antirez). You're right to point out that given the performance characteristics of most modern CPUs, accessing memory linerally is optimum. But it doesn't necessarily follow that all collection data structures should be stored as a vector. Consider a collection traversed very slowly relative to the overall computation. There may not be any cache win if the line's always evicted by the time you come back to it.

fiddlerwoaroof 4y ago
I’ve always wondered about whether you could have your cake and eat it too with linked lists where nodes are allocated in contiguous blocks of N nodes. So, the normal case of traversing the next pointer is not a discontinuous memory access.
- tsimionescu 4y ago
  That's quite likely to happen to a linked list when using a compacting GC (such as Java's or C#'s generational garbage collectors) (assuming the elements of the list are only reachable from the preceding element, not from many other places as well).
  - fiddlerwoaroof 4y ago
    That depends on the GC’s traversal strategy, I think. If you assume that linked lists are implemented as in lisps (a pair of pointers), then if you traverse the head pointer before the tail pointer, the compacting GC will tend to spread the linked list out over time.

pizza 4y ago

It’s hard for me to blame developers for their misaligned mental models since, as you yourself point out, the relationship between your mental model of the hardware’s behavior and what it actually does is complex and not really obvious. Mitigations etc means that the hardware you bought might totally change its behavior in the future. If all you can rely on is time measurements, it doesn’t explain that the software you wrote last year is now eg 40% slower due to bug mitigations. I think it’s easier to expect developers to put in the effort once they’re empowered with powerful tools to explain how the software gets mapped onto the hardware. I think tools that result in greater transparency at lower levels will probably emerge, something like a compiler-generated dynamic analysis + pre-flight checklist hybrid. But since it’s so low-level, it might actually affect results, which may be a problem. I think intel vtune seems interesting in that regard.

eru 4y ago

Well, ideally your programming language (and its standard library) should provide you with basic data structures that are cache oblivious (or optimized for your arrangements cache). So programmers wouldn't need to worry.

pencilguin 4y ago

The fact is that in 95+% of cases, the performance doesn't matter at all, and a linked list is fine. The only problem is that use cases evolve, and what was fine suddenly isn't, anymore.

teo_zero 4y ago

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.

simplotek 4y ago

> It's surprising people are arguing about this. That fact alone shows that lots of developers don't understand the relationship between L1/L2 cache, data access patterns, and how prefetching works. Your misconception lies in the assumption that the only conceivable use case is iterating over a preallocated data structure to do read-only operations. Once you add real world usages, with CRUD operations involving memory allocations/reallocations then your misconception about cache crumbles, and you start to understand why "people are arguing over this".

Dylan16807 4y ago
Which misconceptions? Messy memory allocations hurt lists even more.
mannyv 4y ago
You're expanding the scope of the problem. In real life nobody is pulling shit off of a database and stuffing it into a linked list. And if they are the performance will still be worse because each list will be allocated. Even if you do your own malloc you will blow cache with a linked list, because as time goes on your locality will be blown out. Iterating over a linked list will be worse as well. In fact, on modern architectures it may be faster to iterate over arrays just to take advantage of l2/l3 behaviors.