* A developer who knows that an L3 cache miss and random main memory access typically takes about 100 ns, or
* A developer who learns from highscalability.com that he should "Stop Using Linked-Lists"
struct node {
void * data;
uint32_t idx_next;
};
You are still dereferencing pointers, of course, but you have better locality, even after doing a lot of insertions and deletions. struct node {
uint8_t r, g, b;
uint8_t idx_next;
};
Of course, a contiguous array uint8_t[256][3] might still be faster.{ l * next; x * data; } or { l * next; x data; }
array-based linked list would be an array where each element also has the index (or pointer) of the next element.
{ int next; x data; } [1000];
Now all your elements are packed together in a memory space that you can control.
I think of (array) deque as something that allows me to operate on the front and back, not necessarily traverse and insert/delete in the middle.
But it doesn't get you the same locality as an array at any rate. The idea is that, assuming your elements are smaller than a cache line and your array as a whole is larger, what you're avoiding with an array is N/M cache misses while you traverse rather than potentially (or even probably, depending on various other factors) having a cache miss on every nextItem(). You'll also miss more often because of the expansion of the elements.
There is a valid point, that a naive analysis of linked list vs. static array based on intro CS course descriptions of their properties isn't a good model for what is going on in a modern system.
The real lesson is: if you want to achieve high performance you simply must understand the impact of things like cache localization, vectorization, hardware prefetch, pipelining etc., and how your data structure operation will interact with them.
"Never use a linked list" is a silly lesson to take from this though. "In these situations, linked lists might not perform as well as you expect" is more like it.
"Use the right data structure for the job" is still as good advice as it ever was.