In a recursive divide-and-conquer task that splits work in two, why is the pattern 'fork the left half, compute the right half on the current thread, then join the left' preferred over forking both halves and joining both? And what goes wrong if you join a subtask immediately after forking it?

## The three shapes Consider a task that has split its input into halves `a` and `b`. **Shape 1 - fork both, join both** ``` left = fork(solve(a)) right = fork(solve(b)) return combine(join(left), join(right)) ``` Both halves are parallel-eligible, but the calling worker now has nothing to do except block on the first join. You have paid two task submissions to occupy at most two other workers. **Shape 2 - fork one, run one (the idiomatic form)** ``` left = fork(solve(a)) right = solve(b) // executed by this worker, right now return combine(join(left), right) ``` One submission, and the calling worker stays productive. Across the whole recursion this halves the number of task objects created, queued and possibly stolen. It also has better locality: the worker that just split the range immediately processes one of the halves, whose data it has already touched. **Shape 3 - fork then immediately join (the bug)** ``` left = fork(solve(a)); leftResult = join(left) right = fork(solve(b)); rightResult = join(right) ``` Here `solve(b)` is not even submitted until `solve(a)` has finished. The two halves cannot overlap. You have written a sequential algorithm with a task-scheduling tax on every level of the recursion - typically several times slower than simply calling `solve(a)` and `solve(b)` directly. ## Why shape 3 is so easy to write It reads naturally: create work, get its result, create the next work, get its result. The parallelism only exists in the *gap* between fork and join, and shape 3 has no gap. The rule to remember is: **everything you want to overlap must be forked before the first join.** A join is a hard boundary; nothing submitted after it can overlap with work before it. ## Why shape 2 beats shape 1 in practice Both expose the same *logical* parallelism - the two halves are independent either way. The difference is cost and scheduling: - **Task count.** Shape 2 creates one task per internal node instead of two. Over a recursion producing a million leaves that is hundreds of thousands fewer allocations, queue pushes and potential steals. - **Worker utilization.** In shape 1 the parent blocks. Good runtimes mitigate this - a joining worker will typically execute the pending child itself rather than idle - which in effect converts shape 1 into shape 2 at runtime. But relying on that mitigation is worse than writing the intent directly, and it does not help runtimes that simply park the thread. - **Locality.** The worker that split the range still has the range metadata and part of the data in cache; running one half locally exploits that. ## Join order and result combination Joins hand results back to the parent, which combines them. Two rules: 1. **Combine positionally, not by completion order.** For a sum it does not matter, because addition is commutative. For a concatenation, a merge, or building an ordered list, `combine(leftResult, rightResult)` and `combine(rightResult, leftResult)` are different answers. A subtle version of this bug is combining results as they complete - the output then depends on scheduling and varies between runs. 2. **Join in a sensible order but do not confuse order with dependency.** Joining `left` before `right` does not force `left` to finish first; both are already running. It only determines when the parent resumes. ## A related anti-pattern: joining too early in a loop When a task splits into many pieces rather than two, the same mistake appears as: ``` for part in parts: join(fork(solve(part))) // sequential ``` versus ``` handles = [fork(solve(part)) for part in parts] results = [join(h) for h in handles] // parallel ``` Fork the entire batch first, then join the batch. The shape is identical to the two-way case: no join before all the forks you want to overlap. ## What an interviewer is checking That you understand fork and join as the *boundaries of an overlap window*, not as a call-and-return pair. Candidates who see `fork` as 'run this in the background' and `join` as 'get the answer' usually write shape 3 without noticing, then conclude that parallelism 'did not help'.