Addressing Modes: How an Index Becomes an Address
Instructions do not just name registers — they name ways of computing an address from registers, constants and a scale factor. The reason arr[i] costs one instruction rather than three is that the hardware performs exactly the arithmetic that array indexing requires.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The modes, from simplest to most useful
An addressing mode is a rule for computing an operand's location. The simplest is immediate: the value is encoded in the instruction itself. Register means the operand is in a named register. Neither touches memory. The memory modes are where the interesting arithmetic lives.
Base + displacement adds a constant offset to a register — the natural fit for struct field access, where the base register holds the struct's address and the displacement is the field's fixed offset (Padding: Why Your Struct Is Bigger Than Its Fields). Base + index × scale + displacement adds a second register multiplied by a small power-of-two scale factor, which is exactly the shape of array element access.
The scale factor is the elegant part. Element sizes are typically 1, 2, 4 or 8 bytes, so multiplying an index by the element size is a shift by 0, 1, 2 or 3 — cheap enough to fold into address generation without a separate multiply. The instruction set exposes exactly the arithmetic that array indexing needs, because array indexing is what programs spend their time doing.
| Mode | Address computed | Typical use |
|---|---|---|
| Immediate | None — value is in the instruction | Constants: x + 1 |
| Register | None — value is in a register | Locals held in registers |
| Base | [reg] | Dereferencing a pointer |
| Base + displacement | [reg + const] | Struct field access at a fixed offset |
| Base + index | [reg + reg] | Element access when the scale is already applied |
| Base + index × scale + displacement | [base + idx*k + const] | Array element access — the common case |
The whole calculation, in one instruction
Putting it together: a load from arr[i] where elements are four bytes needs the base address of arr, the index i, a scale of 4 and a displacement of 0. All of that is encoded in a single memory instruction, and the address-generation hardware computes it while the memory access is being initiated.
The comparison below shows what the same access looks like without the folded mode — which is what you would see on an ISA lacking a scaled-index mode, or in unoptimised output. Three instructions become one, and more importantly, two ALU operations disappear entirely, freeing those slots for actual work.
This is the concrete mechanism behind a claim usually stated abstractly. When DSA says array indexing is constant time, this is what makes it true on real hardware: the address of any element is one arithmetic expression away from the base, and the hardware computes that expression for free as part of the access (What `arr[i]` Actually Compiles To).
1; load arr[i] without a scaled-index addressing mode2 shl rcx, 2 ; i * 4 <- ALU3 add rcx, rdi ; base + (i*4) <- ALU4 mov eax, [rcx] ; load5 6; 3 instructions, 2 ALU slots consumed before the load can issue1; the same load with base + index*scale2 mov eax, [rdi + rcx*4]3 4; 1 instruction. The scale-and-add happens in address generation,5; not in the ALU, so both ALU slots stay free for real work.Identical memory access, identical result. The folded form performs the address arithmetic in dedicated address-generation hardware rather than the ALU, which both shortens the instruction stream and leaves execution units free — which matters precisely in the tight loops where array indexing appears.
Why this makes arrays and pointer structures differ
The consequence reaches well beyond instruction counting. For an array, the address of element i is computable from the base and the index — arithmetic, available immediately, with nothing to wait for. The hardware can therefore compute several element addresses ahead of time and issue their loads in parallel, and the prefetcher can see the stride and fetch ahead (Prefetching: The Hardware Guesses What You Will Read Next).
For a linked structure, the address of the next node is *in the current node* and must be loaded before it can be used. That is a dependency, not arithmetic. The processor cannot compute where to look next until the previous load returns, so the loads serialise and neither parallelism nor prefetching helps (Pointer Chasing: The Address You Do Not Have Yet).
This is the hardware root of one of the most-cited performance results in the domain: traversing an array beats traversing a linked list at the same asymptotic complexity, often by a wide margin. It is not because pointers are slow. It is because one access pattern produces independent addresses and the other produces a dependency chain (Both Are O(n). One Is Far Slower.).
Key points
- An addressing mode is a rule for computing an operand address from registers, a scale factor and a constant.
- Base + index × scale + displacement is exactly the arithmetic array element access requires.
- The scale is a shift because element sizes are powers of two, which is why it folds in for free.
- Folded addressing keeps the calculation out of the ALU, leaving execution slots for real work.
- Array addresses are computable and independent; linked-node addresses must be loaded first, which serialises them.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Instruction → decode: the addressing mode and its base, index, scale and displacement fields are identified.
- 2Register file → address generation: the base and index register values are read.
- 3Address generation → address:
base + index × scale + displacementis computed, with the multiply as a shift. - 4Address → load/store unit: the memory access is initiated against the data cache.
- 5Data cache → register: on a hit the value returns; on a miss the request descends the hierarchy.
- • "
arr[i]needs a multiply." The scale is a shift by a constant, folded into address generation — there is no multiply. - • "Pointer dereference and array indexing cost the same." The instruction may look similar; the dependency structure does not.
- • "Complex addressing modes are slow." They fold work into dedicated hardware; the explicit alternative is usually worse.
Consequences, controls and cost
- • Array indexing costs one instruction and no ALU slots, which is what makes tight indexed loops so cheap.
- • Struct field access compiles to a base plus a constant displacement, so field offsets are free at runtime.
- • Pointer-chasing cannot use these modes to run ahead, because each address depends on the previous load.
- • Prefer indexable contiguous structures in hot loops so addresses stay computable rather than loaded.
- • Keep element sizes at powers of two where practical so the scale factor folds into the addressing mode.
- • Read the disassembly to confirm address arithmetic was folded rather than emitted separately.
- • Where a pointer structure is required, consider an arena with index-based references instead of raw pointers.
- • Disassemble the loop and check whether the address arithmetic appears as separate instructions or folded into the access.
- • Compare an indexed traversal against a pointer traversal over the same data; the gap is the dependency effect.
- • Watch load counters and stall cycles — a serialised pointer chase shows low IPC with modest load counts.
- • Index-based references instead of pointers add an addition on every access and buy independence and compactness.
- • Padding element sizes up to a power of two makes addressing cheaper and wastes memory, which can cost more than it saves.
Scope
§224 — what these claims are specific to.
- ISA-SPECIFICAvailable modes differ: x86-64 offers base + index × scale + displacement in one instruction, while some load/store architectures offer a narrower set and require explicit arithmetic for the rest.
- GENERALThe underlying point — computable addresses can be issued in parallel, loaded addresses cannot — holds on every machine regardless of which modes exist.