Fewer operations, slower program
A Socratic walk-through of fewer operations, slower program — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why does the structure that does less work often finish last?
Here is an experiment people keep repeating because the result keeps surprising them. Take a sequence of numbers, and keep it in order while inserting new values at random positions. Do it once with a linked list, where an insertion is a couple of pointer assignments and nothing moves. Do it again with a plain array, where every insertion shifts the tail along by one slot.
Count the operations and the linked list should win comfortably; the array is doing enormous quantities of pointless copying. Time it, and on ordinary hardware the array wins, often by a lot, and often for sequences far larger than anyone expects. So what is the operation count failing to count?
Reasoning it through
REASONING #Start with the assumption hiding inside the phrase "count the operations". It treats every step as costing the same. That is a model — the machine where reading any memory address takes one unit of time. It was a reasonable description of a computer once. It is no longer a description of any machine you own.
What replaced it? A hierarchy. A small, very fast cache close to the core; a larger, slower one behind it; a larger, slower one behind that; and main memory behind everything. The spread from the top of that stack to the bottom is not ten or twenty percent. On a modern processor it is roughly two orders of magnitude — a handful of cycles for the nearest cache against a couple of hundred for a trip to DRAM. So if one structure's steps are mostly cheap and another's are mostly expensive, the operation count is measuring the wrong thing entirely.
Now ask what makes a step cheap. Two habits of the hardware, both of which the array satisfies and the linked list defeats.
The first is that memory does not move in bytes; it moves in cache lines, typically 64 bytes at a time. Touch one number in an array and its neighbours arrive with it, already paid for. Walk the array and most of your reads are free riders on a transfer you already made. The linked list's nodes were allocated at whatever addresses happened to be available, so a node's neighbour in the list is usually nowhere near it in memory. Each hop drags in a fresh line, of which you use the few bytes you wanted and discard the rest.
The second habit is anticipation. The processor watches your access pattern, and when it sees you marching steadily through addresses it fetches ahead of you, so the data is waiting before you ask. Can it do that for a linked list? Consider what it would need to know. The address of the next node is stored inside the current node — so you cannot even begin the next fetch until the previous one has come back. The stalls do not overlap; they queue. That is the specific reason pointer-chasing hurts more than scattered access in general, and it is worth separating from the cache-line point, because they are different failures.
So which structure is doing more "work"? The array does more instructions and less waiting. The list does fewer instructions and more waiting, and the waiting is both larger per event and impossible to overlap. Is it any wonder that the shifting — a long, predictable, streaming copy that the hardware is built to make fast — turns out to be cheaper than a walk of dependent loads?
Where does this reverse? Not never. If elements are large, shifting them costs real bandwidth. If you already hold a pointer to the insertion point and do not have to search for it, the list's advantage is real. And asymptotics do eventually assert themselves — the array's cost grows linearly in the sequence length while the list's does not, so a large enough case flips it back. The honest claim is not "arrays always win"; it is that the crossover sits far higher than the operation count predicts.
The analogy
THE ANALOGY #Think of fetching books. The array is a shelf: you walk along it and the librarian, seeing you move steadily left to right, has already wheeled the next trolley of neighbouring volumes to where you will be. The linked list is a treasure hunt in which each book contains a slip naming where the next one is kept — possibly three floors up. Nobody can pre-fetch anything, because nobody knows the next location until you have opened the book in your hand.
a librarian could in principle guess and pre-fetch several plausible next books at once, whereas the processor cannot chase a pointer it has not yet loaded — the dependency is absolute, not merely a shortage of helpers.
Clarifying the model
THE MODEL #The refinement that connects everything: complexity analysis is not wrong, it is silent. It deliberately hides constant factors so you can compare growth. When two structures have similar growth over the range you care about, the whole outcome lives in exactly the part that was hidden — and on real hardware that hidden part is a factor of a hundred, not a factor of two.
The misconception to correct is that this is about caching being a nice speedup on top of the real cost. It is closer to the reverse. For a great many programs, the arithmetic is nearly free and the entire runtime is the memory system delivering operands. Once you see it that way, "how many operations" stops being the interesting question and "how many cache lines does this touch, and can they be fetched in parallel" starts being it. That is not a fringe view; it is the premise of the external-memory and cache-oblivious models, which count block transfers rather than instructions.
The practical rule that falls out is unglamorous: prefer layouts that are contiguous and traversed in order, be suspicious of any structure whose steps are dependent loads into unpredictable addresses, and measure — the crossover depends on element size, allocation behaviour, and the machine.
A picture of it
THE PICTURE #How to readEach bar is one memory access — the same single "operation" in a complexity count. Read left to right as the data gets further from the core. The first bar is so short next to the last that the picture, not the prose, makes the point: an algorithm doing four accesses that all land in DRAM does far more waiting than one doing forty that all land in L1. The values are round approximations for a modern out-of-order x86 core, and the exact figures vary by chip — it is the shape of the gap, not the numbers, that decides which structure wins.
What became clearer
WHAT CLEARED #An operation count is a comparison of instructions, and modern programs are usually limited by memory traffic instead. A structure with fewer steps can lose because each of its steps is a cache miss that cannot be overlapped with the next, while its rival's many steps are contiguous, prefetchable, and mostly already paid for. Asymptotic analysis has not been refuted — it has simply been asked a question about constants, which it was designed not to answer.
Where to go next
ONWARD #- Why an array of structures and a structure of arrays perform so differently on the same data.
- What changes for a linked structure when its nodes come from a pool and land contiguously anyway.
Key terms
TERMS #| Term | What it means |
|---|---|
| Cache line | the unit in which memory is transferred, commonly 64 bytes, so neighbouring data arrives together. |
| Spatial locality | the tendency to use data near data recently used; what makes contiguous layouts fast. |
| Prefetching | hardware fetching data ahead of the program once it detects a predictable access pattern. |
| Pointer chasing | a chain of loads where each address is only known once the previous load returns, preventing overlap. |
| Cache-oblivious model | an analysis counting block transfers without being told the block size. |
Every term the collection defines is gathered in the glossary.