Re:Linked List Problems (2002) [pdf]
by avodonosov on Sunday November 26, 2017 @04:49AM
(#15780186)
Ah, yes.
Well, anyways I value code simplicity more than anything.
Maybe CPUs will learn to do cache prefetch for link oriented languages: if a "load and dereference" pattern is detected, CPU could prefetch the data referenced by pointers it has in registers or recently fetched cache line.
BTW, linked list elements are not necessary located far away from each other, if we allocated them one after another chance are they are near each other in memory.
Essentially, many workloads access data sequentially and therefore modern cache architectures have special optimizations to make these memory accesses as fast as possible, by prefetching the next item in the sequence before it is actually needed.