What `arr[i]` Actually Compiles To
Indexing an array is not a lookup. It is arithmetic: base plus index times element size, computed in a single addressing mode on most architectures. That is why arrays are the cheapest random-access structure hardware supports.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
One addressing mode, no extra work
Most architectures provide an addressing mode of the form base + index * scale + displacement, where the scale is a small power of two. That covers arr[i] for any element whose size is 1, 2, 4 or 8 bytes exactly — which is most primitive types — and the address computation happens inside the load's address-generation hardware rather than as separate instructions.
When the element size is not a power of two, say a 12-byte struct, the compiler must emit an actual multiply or a shift-add sequence. This is a small cost, but it is one reason element sizes that are powers of two are mildly preferred in hot code, and it is why padding a struct to a power-of-two size is occasionally worth it despite the wasted bytes.
The consequence worth internalising is that the *index* is free but the *element size* is not: it scales how far apart consecutive elements sit, which determines how many fit per cache line and therefore how a scan behaves. Address arithmetic is cheap; the memory traffic it generates is not.
1// source2x = arr[i]3 4// address arithmetic5addr = base(arr) + i * sizeof(element)6 7// on x86-64 with a 4-byte element this is one instruction:8// mov eax, [rbx + rcx*4]9// base ^ ^ index, scaled by element size10//11// with a 12-byte element the scale is not encodable, so:12// lea rdx, [rcx + rcx*2] ; rdx = i*313// mov eax, [rbx + rdx*4] ; base + (i*3)*4 = base + i*12Two dimensions is the same arithmetic, twice
A two-dimensional array in row-major order is stored as one contiguous block, and m[r][c] becomes base + (r * columns + c) * sizeof(element). There is no array of pointers involved and no indirection — just a slightly longer arithmetic expression.
This is exactly why iteration order matters so much for matrices. Varying c in the inner loop walks consecutive addresses, so each cache line brings in several elements that will all be used. Varying r in the inner loop jumps by a whole row each step, touching a different cache line every iteration and using one element from each. Same element count, same complexity, dramatically different miss counts.
Note that row-major is a convention, not a law. C, C++, Python's NumPy by default and most systems languages use it; Fortran, MATLAB and Julia are column-major. Library code frequently supports both via explicit strides, so "the inner loop should vary the last index" is only correct once you know the layout.
| Traversal | Address stride per step | Cache lines touched | Elements used per line |
|---|---|---|---|
| Row-major array, inner loop over columns | One element | Few — consecutive | All of them |
| Row-major array, inner loop over rows | One full row | One per access | One, then the line is evicted |
| Column-major array, inner loop over rows | One element | Few — consecutive | All of them |
| Random index order | Unpredictable | One per access, unpredictable | One, and no prefetching |
Why this makes arrays special
The combination of computable addresses and contiguous storage is what makes arrays uniquely friendly to hardware. Because the address of element i is arithmetic rather than a value that must be loaded, the CPU can compute many addresses ahead of time, issue many loads concurrently, and let the prefetcher run ahead of the loop entirely.
Contrast a linked structure, where the address of the next element is a *value stored in memory* that must be loaded before the next address is even known. That single difference is the whole of Pointer Chasing: The Address You Do Not Have Yet and most of Both Are O(n). One Is Far Slower., and it is why two structures with identical asymptotic traversal complexity behave so differently.
The DSA framing — arrays are O(1) indexed, lists are O(1) inserted — is correct and remains useful. What it omits is that the constant factors differ by more than an order of magnitude in the traversal case, for reasons that live entirely at this level.
- Array element address: computed from the index — known arbitrarily far ahead.
- Linked node address: loaded from the previous node — not known until that load returns.
- Computable addresses enable prefetching, memory-level parallelism and vectorisation; loaded addresses enable none of them.
- This is a hardware property, not a language one: it applies equally to a C array, a Java array and a NumPy buffer.
Key points
arr[i]compiles tobase + i * sizeof(element), usually absorbed into a single addressing mode at no extra cost.- Non-power-of-two element sizes require explicit multiply or shift-add sequences, a small but real cost.
- Two-dimensional row-major indexing is the same arithmetic with an extra term, which is why loop order determines miss counts.
- Row-major versus column-major is a convention that differs between languages — check before assuming which index to vary innermost.
- Computable addresses are what let hardware prefetch and overlap accesses, and are the root reason arrays outperform linked structures on traversal.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Index → address generation: the load's addressing mode computes
base + index * scalein the address-generation unit. - 2Address → TLB: the virtual address is translated, usually hitting the TLB for a sequentially accessed array.
- 3Address → cache: the line containing the element is looked up; consecutive indices usually hit the line already fetched.
- 4Loop → prefetcher: because addresses follow a constant stride, the prefetcher predicts and fetches ahead of the loop.
- 5Concurrent loads → memory-level parallelism: multiple independent addresses can be in flight at once, overlapping any misses.
- • "Indexing is a lookup, so it costs a memory access to find the element." The address is computed arithmetically; only the element itself is fetched.
- • "Loop order does not matter because both versions are O(n·m)." Complexity is identical and runtime is not; the difference is entirely in cache behaviour.
- • "All languages store matrices the same way." C and NumPy default to row-major; Fortran, MATLAB and Julia are column-major.
Consequences, controls and cost
- • Array indexing costs effectively nothing beyond the memory access itself.
- • Loop nesting order over a multidimensional array changes cache miss counts by a large factor without changing complexity.
- • Element size directly controls how many elements share a cache line, so it drives scan throughput.
- • Iterate in the order that matches the storage layout so the innermost loop walks consecutive addresses.
- • Prefer element sizes that are powers of two in hot arrays, where the space cost is acceptable.
- • Shrink elements to fit more per cache line — see [[padding-and-struct-layout]].
- • For multidimensional work with unavoidable strided access, block the loops so a tile stays resident — see [[matrix-tiling]].
- • Compare the two loop orders over a large matrix and count cache misses — the ratio is usually dramatic and immediately explanatory.
- • Inspect the compiler's output to confirm the address arithmetic folded into an addressing mode rather than becoming a multiply.
- • Vary element size while holding element count constant to isolate the bytes-per-line effect from the count effect.
- • Padding elements to a power-of-two size wastes memory and can push a working set past a cache threshold.
- • Reordering loops to match layout sometimes conflicts with the order that is clearest for the algorithm.
Scope
§224 — what these claims are specific to.
- ISA-SPECIFICThe exact addressing modes differ: x86-64 encodes base+index*scale+displacement in one operand, AArch64 uses register offsets with optional shift. The address arithmetic itself is universal.
- PLATFORM-SPECIFICRow-major versus column-major storage is a language and library convention, not a hardware one — C and NumPy differ from Fortran and Julia.