Wait why do linked lists have bad cache locality? It depends on how your heap is set up. For example, you could have an allocator that gives relatively good locality by having high granularity and only bailing out if say your LL gets super long (so if your lists are usually short, they could have awesome locality)
That only works if you allocate lists all at once and never modify them.
If there are any other allocations taking place at the same time -- say, allocations from other threads, or for other data you had to create while building the list, that locality is shot. Same goes if you insert more elements to the list later, or if you perform an operation which changes its order (like sorting it).
I mean, if you modify the contents of the list nodes in place, sure. But at that point, you're just doing an array with extra steps.
Changing any of the pointers, however, will make memory prefetch much less efficient. CPUs like linear memory access patterns; they're easy to predict. Chasing pointers is much less predictable, even if the pointers are all to the same region of memory.
That doesn't seem to make much sense to me. LL are useful in cases where you deal with changing lists, where you'd be forced to allocate and deallocate memory often. If you know before hand the exact or approximate size of the list and it's contents you can store that continuously in memory with greater cache locality because you're not storing pointers in addition to data. Seems to me the use case of LL is perhaps as ill suited for cache locality as the structure itself
True. You could implement that using an array of structs where each struct contains indexes of the array to link other structures. instead of memory pointers, since they are 8 bytes in 64-bit applications. This way you get the nice properties of both linked lists and continuously allocated arrays
If your list is short then you won't have a problem. But if your list is long then traversing it can be a major problem.
For example, if your list item is page aligned like the task_struct in the Linux kernel, rescheduling the next process could traverse the process list. The process list links will be at the same page offset and associate with a restricted set of the L1/L2/L3 caches lines and thrash from memory. Worse, the TLB will thrash as well. This was actually the case for Linux until about 2000.
If you are in that place, you're probably using a linked list over small statically allocated memory, but you still need random ordering and fast remove or reorder.
