Dependency Graphs: The Real Shape of Your Code
Program order is a line. What the machine actually obeys is a graph — and the longest path through that graph, not the number of nodes in it, is what sets the floor on how fast a loop can run.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Program order versus data flow
Consider four operations where B and C both read A's result and D combines theirs. Written down, that is four sequential lines. As a graph it is a diamond: after A, the machine can run B and C at the same time, and only D has to wait for both.
The time to execute the diamond is not the sum of four latencies. It is latency(A) + max(latency(B), latency(C)) + latency(D) — the longest path. Add a fifth independent operation hanging off A and, if a port is free, it costs nothing at all. This is why "I added a line, so it must be slower" is unreliable reasoning about a hot loop.
The graph also explains the shape of the fix. To speed up a chain-limited loop you either shorten the critical path (cheaper operations, fewer indirections, data already in cache) or you create additional independent paths for the scheduler to interleave. Nothing else helps, and in particular a faster clock helps only proportionally while a shorter chain can help far more.
Latency and throughput are different numbers for the same instruction
Every execution unit has two characteristics that novices routinely conflate. Latency is how many cycles pass before the result is usable by a dependent operation. Throughput is how often a new, independent operation of that type can be started. A pipelined multiplier might accept a new multiply every cycle while each individual multiply takes several cycles to produce its answer.
That gap is the entire opportunity. A chain of n dependent multiplies costs roughly n × latency. A batch of n independent multiplies costs roughly n / throughput — potentially several times less for the same arithmetic. Which number you pay is determined solely by whether the operations depend on each other.
This is also the reason two microbenchmarks of "how fast is this instruction" can disagree by a large factor and both be correct: one measured a dependent chain and reported latency, the other measured independent work and reported throughput. When reading any instruction-cost table, the first question is always which of the two it lists — a trap Every Way a CPU Microbenchmark Lies covers in general.
Finding the critical path in real code
The practical procedure is short. Take one iteration of the hot loop. Draw an edge from every value produced to every operation that consumes it. Then find the longest path that also carries across iterations — the *loop-carried* dependency — because that one repeats n times and dominates everything else.
In the pointer-walk below, the loop-carried dependency is p = p->next. Every iteration must finish loading the next pointer before the following iteration can even begin computing its address, so the loop runs at one memory latency per element no matter how many execution ports sit idle. This is the mechanism behind Pointer Chasing: The Address You Do Not Have Yet and the reason a linked list loses to an array at identical asymptotic complexity (Both Are O(n). One Is Far Slower.).
In the indexed loop, the loop-carried dependency is only i = i + 1 — a cheap register increment. All the loads are independent of one another, so several can be outstanding simultaneously and the hardware prefetcher can run ahead. Same O(n), same element count, completely different graph.
1p = head2while p != null:3 sum = sum + p->value4 p = p->next # <-- next address is not known5 # until this load completes6 7# critical path per element: one full memory access8# outstanding loads possible: one1for i in 0..n:2 sum = sum + a[i] # address is i * size + base,3 # computable immediately4 5# critical path per element: one add6# outstanding loads possible: manyBoth are O(n) with one add per element. In the first, the address of the next access is itself the result of a memory load, so accesses strictly serialise and the machine can never have more than one outstanding. In the second, every address is known in advance from the index, so many loads proceed concurrently and the prefetcher can work. The difference is entirely in the shape of the dependency graph.
Key points
- The machine obeys the dependency graph, not program order; the longest path through it bounds how fast the code can run.
- Latency and throughput are different properties of the same instruction, and which one you pay depends on whether your operations are independent.
- The loop-carried dependency is the one that matters, because it repeats once per iteration.
- A dependency that runs through memory is dramatically worse than one that runs through a register, because its latency is orders of magnitude larger.
- Adding independent work to a chain-limited loop is often free; adding it to a throughput-limited loop is not.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Decode → rename: false dependencies from register reuse are removed, leaving only true producer-to-consumer edges.
- 2Rename → scheduler: each operation records which physical registers it is still waiting on.
- 3Producer completes → wakeup: dependents whose last operand just arrived become eligible to issue.
- 4Scheduler → ports: eligible operations are selected each cycle, so independent branches of the graph proceed concurrently.
- 5Loop-carried edge → next iteration: if that edge passes through memory, the next iteration cannot start its address computation until a full memory access completes.
- • "This loop does fewer operations, so it is faster." Fewer operations on a longer chain is usually slower.
- • "The instruction table says this costs 4 cycles." That is latency or throughput, and the two can differ by a large factor.
- • "Unrolling helps by removing the loop counter." Usually it helps by creating independent chains; the counter was cheap.
- • "O(n) is O(n), so traversal cost is comparable." Complexity counts operations, not the latency of the edges between them.
- • "The CPU is idle, so I am not compute-bound." Idle ports with a full window means you are dependency-bound, which is neither classic compute-bound nor memory-bandwidth-bound.
Consequences, controls and cost
- • Two loops with identical instruction counts can differ several-fold in runtime purely from graph shape.
- • Reduction loops (sum, max, dot product) are chain-limited by default and respond well to multiple accumulators.
- • Data structures that store the next address inside the current node cap memory parallelism at one outstanding access.
- • Instruction-cost tables are ambiguous unless they say whether they list latency or throughput.
- • Speedups from unrolling often come from breaking the dependency chain, not from removing loop overhead.
- • Identify the loop-carried dependency first — it is the only edge that repeats n times.
- • Break reduction chains into several independent accumulators, then combine at the end.
- • Replace memory-carried dependencies with index arithmetic where the data structure allows it.
- • Hoist invariant computations out of the chain so the repeated path is as short as possible.
- • Prefer data layouts that let addresses be computed rather than loaded ([[data-oriented-design]]).
- • Time a dependent chain against independent work for the same operation; the ratio exposes latency versus throughput on your machine.
- • Add independent accumulators to a reduction and re-measure — a large improvement with identical instruction counts confirms a chain limit.
- • Read IPC ([[ipc]]): a low IPC with low cache-miss counts and idle ports points at a dependency chain rather than memory.
- • Count outstanding memory requests if your counters expose it; a value pinned near one during a traversal is the pointer-chasing signature.
- • Compare against a version with the same accesses issued from precomputed indices to isolate the memory-carried edge.
- • Multiple accumulators change floating-point results by regrouping the sum; that may or may not be acceptable.
- • Restructuring for independence usually costs readability and can obscure the algorithm being implemented.
- • Layouts that make addresses computable (arrays, indices instead of pointers) trade insertion and deletion cost for traversal speed.
- • Aggressive unrolling grows code and can turn a front-end-friendly loop into an instruction-cache problem.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICOperation latencies, throughputs and the number of ports of each type vary by core. The ratio between a dependent chain and independent work is large on every out-of-order core, but its exact size is not portable.
- GENERALThe graph model itself — longest path bounds runtime, loop-carried edges dominate — holds for any machine that overlaps execution at all, including in-order superscalar and VLIW designs.