# Fork/join and parallel loops

> How Alice runs independent recursive calls and counted loops across cores, what it must prove first, and how par for makes the decision explicit.

Canonical: https://alice-lang.org/documentation/concurrency/fork-join/

[Documentation index](https://alice-lang.org/documentation/llms.txt) · [Complete book](https://alice-lang.org/llms-full.txt)

Alice parallelizes code that is already parallel in shape. You do not create threads: the compiler proves two calls, or the iterations of a loop, independent, and the runtime spreads them over the .NET thread pool. Code it cannot prove safe stays serial. The [race checker](https://alice-lang.org/documentation/concurrency/race-safety.md) and the purity gate decide eligibility, never a guess.

The idea of a cheap fork that only becomes a real task near the root of a call tree comes from Victor Taelin's [Bend and BendRT](https://github.com/bendlang/bend). Bend asks you to write the parallel call; Alice infers it and keeps the .NET garbage collector.

## Forked recursive calls

Two consecutive bindings whose values are calls fork when they are independent and at least one is recursive:

```alice
def radix(values : Array(Int64), shift : Int32) : Array(Int64)
  # ... split values into left and right ...
  sorted_left = radix(left, shift - 1)     # offered to another core
  sorted_right = radix(right, shift - 1)   # runs here meanwhile
  # ... concatenate ...
end
```

The single-statement form is Bend's parallel call written the Alice way:

```alice
def pow2(n : Int32) : Int64
  return 1_i64 if n == 0
  a, b = pow2(n - 1), pow2(n - 1)
  a + b
end
```

| Rule                                                                     | Why                                                                            |
| ------------------------------------------------------------------------ | ------------------------------------------------------------------------------ |
| Both calls go to methods proven pure                                     | Impure code never runs in parallel.                                            |
| The second call does not read the first result                           | `b = f(a)` is sequential by definition.                                        |
| At least one call is recursive                                           | Recursion is what makes the work divide; two small calls are not worth a task. |
| Arguments are pure reads, no blocks or named arguments                   | They are evaluated inside the task.                                            |
| Not inside `async`, generic methods, lambdas, or another parallel helper | A task boundary must not cross them.                                           |

A pure method may write into arrays it allocated itself; writing into a parameter's array is an effect. Runtime functions marked pure, such as `Digest::SHA256.hexdigest`, may be called from forked code. Arbitrary .NET methods are never trusted.

### What a fork costs

Only the top `log2(cores) + 3` levels of the call tree fork; deeper calls are plain calls behind one thread-static check. A fork offers its left half to the pool as a single work item and runs the right half on the current thread. At the join, a left half no worker has started runs inline on the joining thread, so an unneeded fork costs one small allocation and one compare-and-swap. Exceptions surface as themselves, and when the right half throws, the left half finishes before the exception continues.

An expression containing two recursive calls, such as `fib(n - 1) + fib(n - 2)`, does not fork yet. Bind the two results to names.

## Parallel counted loops

A `for i in a...b` loop runs in chunks across cores when its iterations are independent:

| An iteration may                       | Example                                                  |
| -------------------------------------- | -------------------------------------------------------- |
| Write locals declared in the body      | `d = xs[i] - mean`                                       |
| Write the array cell it owns           | `out[i] = f(xs[i])`                                      |
| Write its own row of a row-major array | `img[y * w + x] = shade(x, y)` with `x` counting `0...w` |
| Accumulate one numeric reduction       | `total += d * d`                                         |
| Read anything it does not write        | `src[i - 1] + src[i + 1]`                                |
| Call pure methods                      | `noise(x, y, seed)`                                      |

A loop that reads the array it writes at another index is a scan and stays serial:

```alice
for j in 1..n
  row[j] = [row[j - 1] + 1, previous[j] + 1].min   # depends on the previous iteration
end
```

A stencil over a *different* array stays parallel. When two array variables could name the same array, the generated code checks `ReferenceEquals` before taking the parallel path, so an aliased call takes the serial loop.

### When it pays

A loop needs 65,536 or more iterations to receive a parallel path. A body with nested loops or user calls is heavy work, so two iterations are enough. A loop nested inside another serial loop uses the large threshold, because a dispatch per outer iteration would cost more than it saves.

Reductions combine per-chunk partial results in index order. Integer results are exact; a floating-point sum is reassociated, like any SIMD sum.

## `par for`: parallel on request

`par for` removes the size heuristic and turns the independence proof into a requirement:

```alice
def render(w : Int32, h : Int32) : Array(Int32)
  img = Array(Int32).new(w * h)
  par for y in 0...h
    for x in 0...w
      img[y * w + x] = escape_time(x, y)
    end
  end
  img
end
```

A `par for` whose iterations are not provably independent is a compile error, not a silent serial loop:

```text
error[AL0209]: cannot parallelize `par for`: iterations are not provably independent
```

Use it when you know the body is expensive enough to benefit at small trip counts, or when you want a guarantee that a loop stays parallel as the code changes.

## The scheduler

Parallel loops run on a chunk scheduler in the Alice runtime: one job object per loop, an atomic chunk counter, and the calling thread working through chunks itself. A loop therefore completes even when every pool thread is busy, so nested parallel loops cannot starve the pool, and the first exception reaches the caller unwrapped, exactly as from the serial loop.

The standard library uses the same machinery: `sort` of a large primitive array is a parallel merge sort, and `sum`, `min`, `max` of arrays with 2^20 or more elements split into SIMD chunks across cores.

## Check what happened

```sh
alice emit program.al
```

Parallel loops appear as `__parfor_*` helpers guarded by a trip-count test, forks as `__fork_*` helpers behind `Par.Forkable`. If a loop you expected is missing, `par for` reports that its iterations are not provably independent, which tells you to look for a write outside the iteration's cells or a call the purity gate cannot prove.

## Continue reading

- Previous: [Race safety and AL0202](https://alice-lang.org/documentation/concurrency/race-safety.md)
- Next: [Use .NET and NuGet](https://alice-lang.org/documentation/guides/dotnet.md)