skip to content

Before spreading a column of pure cell formulas across workers, what must a scheduler establish about each one?

level: middleimportance: must knowfreq 58%

answer

  1. element-wise work splits trivially
  2. no row waits on its neighbour
  3. each worker owns its own slots
  4. nothing read is written mid-pass
  5. safe to split is not worth splitting

basics

~20 s

That each formula reads only its own row's inputs, writes only its own output slot, and reads nothing that the pass mutates. With all three true, workers can take any partition with no locks and no ordering.

solid answer

~40 s

Three conditions, all of them forms of the same property. First, the work must be **element-wise**: each result depends only on its own row's inputs, so no row waits on a neighbour. Second, each formula writes only its own output slot, so two workers never target the same location. Third, nothing read during the pass is written during the pass. When all three hold, any partition of the range is legal, the workers need no coordination whatsoever, and the parallel result is identical to the serial one — not approximately, exactly. Purity is what lets the scheduler establish this by inspection instead of guessing. Combining the per-row results into a single total is a further question: that needs an associative combine, not just purity.

code

pseudocode · 8 lines
pseudocode
function recalcRange(rows, from, to):
    for each i in from..to:
        # reads only rows[i], writes only slot i
        results[i] = evaluate(rows[i])

# ranges are disjoint, so the two workers never touch the same slot
spawn recalcRange(rows, 0, 4999)
spawn recalcRange(rows, 5000, 9999)

go deeper

for a junior

Know the shape that splits: one result per row, computed from that row's own inputs, written to that row's own slot. Anything that reaches across rows is not that shape.

for a middle

State all three conditions and name the chain as the case that fails the first one. Explain why disjoint writes into a shared array need no protection.

for a senior

Separate correctness from benefit. Show how chunk size, skew and the serial remainder decide whether a provably splittable pass actually gets faster.

for a principal

Decide where a system keeps element-wise shape on purpose. Data layouts and per-row independence are design choices that buy scheduling freedom later, and giving them up is rarely reversible cheaply.

## Element-wise is the shape that splits A recalculation pass is attractive to a scheduler because so much of it is **element-wise**: one formula per row, each producing its own row's answer from its own row's inputs. Element-wise work is the easy case of parallelism — nothing to communicate, no order to preserve, nothing to merge — but only if the shape really is element-wise. Establishing that, before any work is handed out, is the scheduler's whole job here. ## The three conditions 1. **Each result depends only on its own row's inputs.** If row *n* reads the result of row *n-1*, the column is a chain, not a set of independent items: it has one dependency edge per row and therefore exactly one legal order. Purity does not create parallelism the data does not have; it only reveals, precisely, which parallelism is there. 2. **Each formula writes only its own output slot.** Workers may share one results array as long as their index ranges are disjoint, because disjoint slots are not shared state in any meaningful sense. The moment two rows can write the same location, the scheduler is back to needing a protocol. 3. **Nothing read during the pass is written during the pass.** A lookup column that thousands of rows read is harmless while nobody writes it — many readers of an unchanging value impose no order on each other. A value that some row updates mid-pass turns every reader into a formula whose answer depends on when it ran. ## What no coordination actually means - **No locks.** There is no shared writable state to protect, so a lock would add contention and buy nothing. - **No ordering between workers.** Which worker finishes first is unobservable in the result. - **No merge step.** Element-wise output needs no combining; a merge appears only when the results are folded into a single value. - **Determinism.** The parallel result equals the serial result exactly. Re-running with a different worker count, or a different chunk size, produces the same sheet. - **Free choice of partition.** Because correctness does not depend on the split, the scheduler may choose chunk sizes purely for cache behaviour and load balance. ## Where purity alone is not enough | Shape of the work | Splittable on purity alone? | What else is required | |---|---|---| | One result per row from that row's inputs | Yes | Nothing | | Row *n* reads row *n-1* | No | A different algorithm; the dependency is real | | All rows combined into a single total | No | An associative combine, so partial results merge | | Per-row work using a scratch value private to one evaluation | Yes | That the scratch value is genuinely per-evaluation | The last row is worth dwelling on: local mutation inside a single evaluation, invisible from outside, does not make the formula impure and does not block splitting. What blocks it is state two evaluations can both reach. ## Splitting is also a cost decision Correctness and benefit are separate questions, and a candidate who only answers the first is half done. Splitting carries fixed costs: partitioning the range, dispatching tasks, and waiting for the slowest worker to finish. Those costs are paid whether or not the work was worth splitting. - **Per-item work must clearly exceed the overhead.** A few arithmetic operations per row will lose to dispatch cost, which is why schedulers hand out chunks of many rows rather than single rows. - **Skew matters more than average cost.** One row that takes as long as all the rest means the pass finishes when that row finishes, however many workers exist. - **The gain is bounded by the serial remainder.** Whatever the pass does before splitting and after joining caps the speed-up regardless of worker count. ## How this is asked The question is a filter for two failure modes. The first is answering *purity, therefore parallel* without checking the shape — the chain in condition 1 is the counter-example every interviewer has ready. The second is the reverse: demanding a lock around disjoint writes, which shows the candidate is pattern-matching on the word *shared* rather than reasoning about who can write what. A strong answer states the three conditions, gives the chain as the case that fails, and closes on the cost question: proving it is safe to split does not prove it is worth splitting.

  • The rows are pure, but each one reads the previous row's result. What changes?
    It stops being element-wise. A chain of that shape carries one dependency edge per row, so the column is a single sequential path and no partition of the range is legal. Purity still helps — it lets the engine see the chain exactly, with no hidden edges — but it cannot manufacture parallelism the data does not contain.
  • Every row is pure and independent, yet the parallel pass is slower than the serial one. Why?
    Per-row work is too small to repay the fixed costs of splitting: partitioning, dispatching tasks, and waiting for the last worker. Parallelism pays only when per-item work clearly exceeds that overhead, which is why schedulers give each worker a chunk of many rows rather than one row at a time.

saying these in an interview costs you the question

  • Believes purity alone makes any parallel computation correct, reductions included.
  • Says disjoint writes into one results array still need a lock around them.
  • Treats a formula that reads the previous row's result as element-wise work.
  • Thinks splitting always helps, ignoring per-item work against coordination cost.
  • Claims parallel evaluation may legitimately change results, so differences are expected.