Explain the fork()/join() pattern in Fork/Join tasks. Why is the idiomatic ordering fork-one, compute-the-other, then join — and what goes wrong if you fork both then join both, or fork-then-immediately-join?

## The two primitives In the Fork/Join framework a task is split into subtasks, and two methods coordinate them: - **`fork()`** — pushes this task onto the **current worker thread's local deque** (double-ended queue) and returns immediately. The task is now *eligible to run asynchronously*: either the current thread will pop it later, or an idle worker thread will **steal** it. `fork()` does **not** start a new OS thread; it just queues work for the pool. - **`join()`** — waits until the task has completed and returns its result (for a `RecursiveTask`). While waiting, the calling worker doesn't just block uselessly — it may help by executing other queued tasks (this is part of why Fork/Join scales). ## Why the idiom is fork-one / compute-other / join-one The recommended shape inside `compute()` is: ```java left.fork(); // 1. make left available to other workers R rightResult = right.compute(); // 2. do right myself, right now R leftResult = left.join(); // 3. collect left's result return combine(leftResult, rightResult); ``` Reasoning step by step: 1. **fork-one** publishes `left` so an *idle* worker can grab it in parallel. 2. **compute-the-other** keeps *this* thread productive: instead of forking `right` and then standing idle, the current thread directly runs `right`. One thread, two subtasks, zero idle time — and `right` runs without any queueing overhead. 3. **join-one** then waits for `left`. By the time we get here we've already finished `right`, so ideally `left` is also done (or nearly), minimizing the wait. This maximizes the ratio of useful work to coordination overhead, and it respects the deque's **LIFO** discipline: the current thread tends to pop the most-recently-pushed task, so forking only one and computing the other avoids fighting the work-stealing structure. ## What goes wrong with the anti-patterns **(a) fork() then immediately join() the same task:** ```java left.fork(); R leftResult = left.join(); // BAD: nothing else happening meanwhile R rightResult = right.compute(); ``` The current thread forks `left`, then *immediately blocks* waiting for it. Nothing runs in parallel — you've serialized the work and *added* the cost of queueing `left`. This is strictly worse than just calling `left.compute()`. **(b) fork both, then join both:** ```java left.fork(); right.fork(); // wasteful second fork R l = left.join(); R r = right.join(); ``` This is **correct** but suboptimal. The current thread forks both and then has nothing to do but wait, so it relies on *other* threads to run *both* halves. The current worker could have executed one of them directly (saving a queue push/pop and not depending on a steal happening). Under load it usually still works because `join()` lets the waiting worker help, but the cleaner idiom avoids the redundant fork. **(c) Wrong join order:** If you do fork both, join them in **reverse** order (`right.join()` before `left.join()` when `right` was forked last) to match the LIFO deque — the last-forked task is most likely still on the local deque and can be run immediately by this thread rather than waited on. The fork-one/compute-other idiom sidesteps this entirely. ## The convenience shortcut `invokeAll(t1, t2, ...)` forks all but the first, runs the first in the current thread, and joins the rest — encapsulating the idiom for you. It throws on the first failing subtask. Use it to avoid hand-writing the ordering. ## Key takeaways - `fork()` = queue async, `join()` = await + result. - Never `fork()` a task you'll `join()` with nothing in between. - Keep the current thread busy: compute one subtask directly. - Prefer `invokeAll` or fork-left/compute-right/join-left.