skip to content

In a straight-line stretch of a payroll routine, when may two adjacent statements be swapped safely?

level: middleimportance: should knowfreq 42%

answer

  1. a shared place, and someone writes it
  2. two reads always commute
  3. read-after-write pins the order
  4. two writes to one place pin it too
  5. effects and failures are ordered as well

basics

~20 s

Only when neither depends on the other's effect: neither reads what the other writes, neither writes what the other reads, and they do not both write the same place. Observable effects count as a shared place too.

solid answer

~40 s

Order inside straight-line code is pinned by **data dependence**, and there are three kinds. A *true* dependence — the second reads what the first writes. An *anti*-dependence — the second writes what the first reads. An *output* dependence — both write the same location. If none of the three holds, the two statements are independent and may be swapped. The traps are the dependencies the names do not show: two names may refer to the same storage, a call may touch state neither statement mentions, and observable effects like emitting a payslip or appending an audit line are ordered against each other even when no variable connects them. A statement that can fail is also pinned, because moving it changes which effects have already happened when the failure is seen.

code

pseudocode · 4 lines
pseudocode
gross = hours * rate          // nothing above it here
tax = gross * taxRate         // reads gross: must follow it
processed = processed + 1     // touches nothing else in the block
net = gross - tax             // reads both: must follow both

go deeper

for a junior

Learn the everyday half: a statement that uses a value must come after the statement that computes it.

for a middle

Name all three dependencies — read after write, write after read, write after write — and say that two reads commute. That is the mechanical core of the answer.

for a senior

Demonstrate the traps you have actually been bitten by: aliasing, state reached through a call, observable effects, and the failure point that moved.

for a principal

The real question is how much reordering freedom a codebase should have. Code with fewer hidden effects licenses more restructuring, and that is a design property worth buying deliberately.

## Order inside a block is a constraint, not a decoration Inside one basic block every statement runs exactly once, in written order. That makes the block the natural place to ask a question that comes up constantly in review and refactoring: *is this order load-bearing, or is it an accident of how the code was typed?* The answer is not a matter of taste. It is decided by what each statement reads and writes. ## The three dependencies that pin an order | kind | pattern | payroll example | may swap? | |---|---|---|---| | **true** (read after write) | S2 reads what S1 writes | `gross = hours * rate` then `tax = gross * taxRate` | no | | **anti** (write after read) | S2 writes what S1 reads | `bonus = base` then `base = 0` | no | | **output** (write after write) | both write the same place | `total = 0` then `total = gross` | no | All three are the same underlying fact — the two statements touch a common location, and at least one of them writes it. Only when a pair shares no written location is the order free. A fourth case is often listed as "no dependence": both statements only *read* the same location. Two reads commute, so shared reads never pin an order. ## The dependencies the names do not show This is where the question is actually decided in real code, and where a weak answer stops. - **Aliasing.** Two different names may refer to the same storage — a field reached through two handles, an element reached through two indices. If you cannot rule that out, you cannot call the statements independent, whatever the names look like. - **State reached through a call.** A statement that calls something may read or write locations it never mentions. `recordAttempt()` and `gross = hours * rate` look independent; they are only independent if the call touches nothing the rest of the block does. - **Observable effects.** Emitting a payslip, appending an audit line, sending a notification: these are ordered against each other because the outside world records the order, even though no variable connects them. Treat the outside world as a location that every effect writes. - **Failure points.** A statement that can fail partway pins the statements around it: move it earlier and effects that used to be complete before the failure are now missing; move it later and the opposite. The set of states an observer can see has changed even if the success path has not. - **Resource lifetimes.** Acquiring, using and releasing a resource is a chain of true dependencies through the resource itself, whether or not that shows up as a variable. ## What independence licenses Once two statements are genuinely independent, several things become legal at once, and this is why the analysis is worth doing: 1. **Reordering** — put the cheap guard first, or group the lines that belong together in the reader's mind. 2. **Extraction** — an independent run of statements can be lifted into a named routine without dragging its neighbours along. 3. **Sinking and hoisting** — a computation that nothing below it needs can move out of the block entirely; one that nothing above it feeds can move up. 4. **Deletion** — a statement whose result nothing reads and whose effects are not observable is dead, and independence is how you prove it. Every one of those is a routine refactoring, and every one of them is wrong if you got the dependence analysis wrong. ## How to answer this at a whiteboard Name the reads and writes of each statement, including the ones hidden behind calls and the ones that land outside the program. Then say the rule in one line: *the order is fixed exactly when the two touch a common location and at least one of them writes it*. Then name the two traps by hand — aliasing and observable effects — because that is what separates someone reciting a definition from someone who has moved a line and broken a nightly run. One last discipline: state what you are assuming. "These two are independent *provided* the two record handles cannot refer to the same record" is a complete, honest answer. "These two are independent" without the proviso is a guess dressed as an analysis.

  • Two adjacent statements write through different names that might refer to the same storage. What must you establish first?
    That the two names cannot alias. Until that is established the pair has a possible output dependence, and swapping them could change which write survives. Where the language or the surrounding code cannot rule aliasing out, the honest answer is that the order must stay.
  • A statement in the middle of the block can fail partway. How does that constrain moving it?
    It pins its neighbours. Moving it earlier means fewer of the block's effects have happened when an observer sees the failure; moving it later means more have. The success path is unchanged, but the set of observable intermediate states is not, so the move is not behaviour-preserving.
  • Both statements only read the same variable. Does that pin their order?
    No. Two reads commute, because neither changes what the other sees. A dependence needs a shared location with at least one write to it, which is why read-read pairs are the one shared-location case that leaves the order free.

saying these in an interview costs you the question

  • Thinks different variable names always mean independent statements
  • Believes only read-after-write can forbid a swap
  • Treats two writes to one location as safe to reorder
  • Assumes a call returning nothing has no effects
  • Says statement order only matters once threads appear