News for hackers. Stuff that matters.
Re:Ropes, an Alternative to Strings [pdf] (1995) by kazinator on Sunday November 01, 2020 @11:33AM (#24960549)
The exact same things about arrays and linked lists were said in 1995 about 1995 machines. They ring true, if you pin down exactly what you mean by your choice of pathological cases.

Even if we completely eliminate all caching effects, so that every memory access is uniform, regardless of past access history, then arrays are still going to be faster in many cases than linked lists. Obviously, in the random access case: fetching the n-th element. Pointers are metadata; a linked list has metadata for every node, and that requires memory bandwidth to suck through the processor. If every list node has a word of pointer for a word of data, then it means scanning through a million word list means we are loading two million words. If the data is aggregated into an array, then scanning it means we are loading only one million words. That's half the cycles. Likely fewer instructions executed in the loop and so on.

Note that arguments like, "but in year 20XX, such a case now fits into my Ln cache" work toward arguing that caching is less relevant. The more cache you have, the less relevant it is. As a cache gets bigger, more and more situations that previously exhibited "poor locality" now have "good locality" of reference.

Your 2016 machine can cache much more of a given linked list than your 1995 machine; it performs relatively better with linked lists than the 1995 machine, even if we account for basic differences of instruction issue rate (pipelining, branch prediction, etc).

There are no comments on this comment yet.