Part 4 · Where the fictions break
The listing is a dependency graph
Fiction two, dismantled. Instructions do not execute in the order they are written, and once you stop reading them as a script the whole subject reorganises.
What this lesson is trying to break (3)
- Instructions execute in the order listed.
- Reordering source lines changes what the CPU does.
- The CPU executes one instruction at a time.
This is a threshold concept: troublesome, transformative, and irreversible. You should expect to be genuinely stuck here, and being stuck is the mechanism rather than a sign that you are failing. Budget several sessions. Do not move on because you are bored — move on when you can explain it out loud without notes.
The CPU reads an instruction, does it, moves to the next. Assembly is a sequence of steps and the machine performs them in that sequence. This is what every explanation of a computer has told you since you started.
A modern core decodes many instructions at once, works out which depend on which, and executes each one as soon as its inputs are ready — which may be long before earlier instructions have finished. It also executes instructions past branches whose outcome is not yet known, and throws the work away if it guessed wrong.
Read a listing as a dependency graph, not a script. The vertical order is the order the compiler wrote things down; the edges — which instruction needs which result — are what determines time. Two adjacent instructions with no edge between them effectively happen at once.
Why the illusion is airtight
If execution is reordered, why has this never broken any program you have written?
Because retirement is in order. Execution happens whenever convenient; results become architecturally visible in strict program order. A correct single-threaded program cannot observe the difference — only timing reveals it.
That is the contract from 0.2 doing its job: behave as if sequential, perform as fast as possible. Which is why fiction 2 is perfectly safe for reasoning about correctness and completely useless for reasoning about speed.
(The exception is multiple threads, where another core can observe the
reordering. That is what memory ordering and fences exist for, and it is why
Ordering::SeqCst versus Relaxed is a real decision rather than paranoia.)
Reading the edges
Take two sequences with identical instruction counts.
; A — one chain
add eax, edi
add eax, esi
add eax, edx
add eax, ecx; B — two chains
add eax, edi
add ebx, esi
add eax, edx
add ebx, ecxFour adds each. In A every instruction needs the previous result: a chain of
length 4, so it takes four add-latencies end to end.
In B there are two independent chains of length 2. The core can run one from each chain simultaneously, so it finishes in roughly two add-latencies — about twice as fast, with the same instruction count and the same arithmetic.
Nothing about the text tells you this. The edges do.
// A
long chain(long *p) {
long acc = 0;
for (int i = 0; i < 1024; i++) acc = acc * 3 + p[i];
return acc;
}
// B
long indep(long *p) {
long a = 0, b = 0;
for (int i = 0; i < 1024; i += 2) { a += p[i]; b += p[i+1]; }
return a + b;
}Both touch 1024 elements. Both do roughly one arithmetic operation per element.
B is substantially faster, and A cannot be rescued by the compiler.
The difference is structural. In A, acc = acc * 3 + p[i] means iteration i
needs iteration i−1’s result before it can even start. That is a loop-carried
dependency, and it forms one chain 1024 links long. The loop runs at the latency
of a multiply-plus-add, repeatedly, no matter how much parallelism the core has
available.
In B the two accumulators are independent, so work overlaps — and because there is no loop-carried dependency, the compiler is also free to vectorise it, which it will.
This is why A is the shape to recognise and worry about: a loop-carried dependency defeats both out-of-order execution and vectorisation at once. It is the single most common reason a loop is slower than its instruction count suggests, and no compiler flag fixes it — only restructuring does, and only if the operation is associative enough to allow it.
Note that A’s operation genuinely is not reorderable in general, so this is not a compiler failing. Some algorithms are sequential.
How to read for the critical path
A practical procedure for a hot loop:
- Find the loop body — the backward jump.
- For each instruction, ask which earlier result it needs. Draw the edges.
- Find the longest path through one iteration, and check whether it connects to the next iteration. If it does, that is your loop-carried dependency and your floor.
- Count the resource users — loads, stores, multiplies. If you need three loads per iteration and the core has two load ports, you are port-limited regardless of dependencies.
- Only then think about instruction count.
Step 3 is where the money is. And you do not have to do it by hand: llvm-mca
does exactly this analysis and Compiler Explorer will show it in a pane beside
your code. It reports the critical path, port pressure, and an estimated
throughput.
With the caveat from Setup: llvm-mca models the core and knows
nothing about caches or branch prediction. It will confidently analyse a loop
whose real cost is entirely memory stalls. Use it for arithmetic-bound code and
distrust it elsewhere.
Explain to a colleague why these two facts are both true and not in conflict:
- Adding more instructions to a loop can make it faster.
- The CPU still executes your program exactly as written.
Two or three sentences. You need the words dependency and retire.
What you should now be able to say
- Instructions execute when their inputs are ready, not in listed order; they retire in order, which preserves the illusion.
- A listing is a dependency graph; the edges determine time, the order does not.
- Independent work overlaps and is nearly free; dependent work serialises.
- A loop-carried dependency defeats out-of-order execution and vectorisation, and no flag fixes it.
- The floor is the critical path plus resource limits (ports), not the instruction count.
llvm-mcacomputes this for you, and ignores memory.