# 11. Parallelism without threads

> Chapter 11: how Alice runs code on all cores without threads: forked recursive calls, parallel loops, par for, par let, the Par library, and data-parallel primitives such as prefix_sum and histogram.

Canonical: https://alice-lang.org/documentation/learn/parallelism/

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

A modern computer has many cores, often 8, 16 or more. A program that uses one of them leaves most of the machine idle. The usual answer is threads, and threads bring locks, races and deadlocks.

Alice takes a different route, inspired by the Bend language. You write ordinary code. When the compiler can **prove** that two pieces of work are independent, it runs them in parallel for you. When it cannot prove it, the code stays serial, and nothing breaks. Chapter 10 showed why this is safe: data races do not compile.

## 11.1 Recursion that forks

Here is the textbook recursive Fibonacci function:

```alice
def fib(n : Int32) : Int64
  return n.to_i64 if n < 2
  fib(n - 1) + fib(n - 2)
end

puts fib(30)
```

```text title="Output"
832040
```

Look at the last line. `fib(n - 1)` and `fib(n - 2)` do not depend on each other, and `fib` has no side effects. So they can run at the same time. Alice sees this and **forks** the two calls: one goes to another core while this core computes the other, and the results are **joined** with `+`.

`alice explain` shows what it decided:

```alice cmd="explain"
def fib(n : Int32) : Int64
  return n.to_i64 if n < 2
  fib(n - 1) + fib(n - 2)
end

puts fib(30)
```

```text title="Output"
╭─────────────┬────────────────────────────────────────────────────────╮
│ method      │ optimizations                                          │
├─────────────┼────────────────────────────────────────────────────────┤
│ fib         │ fork/join: independent recursive calls run in parallel │
│ fib__serial │ none                                                   │
│ Main        │ none                                                   │
╰─────────────┴────────────────────────────────────────────────────────╯
```

Why is there a `fib__serial`? Forking has a cost. Near the top of the call tree each fork creates a lot of work, so it pays off. Deep down, a fork would cost more than the work it splits. So Alice forks only near the root, and the deeper calls use a serial copy of the method that never checks. The program keeps all cores busy and pays nothing extra in the leaves.

A fork happens when the calls are pure, independent and at least one is recursive. This shape is common: sorting by halves, walking trees, divide-and-conquer search.

## 11.2 Loops that spread out

Loops are the other big source of parallel work. A counted loop whose iterations do not depend on each other can be split into chunks, one per core:

```alice
def sum_of_squares(xs : Array(Int64)) : Int64
  s = 0_i64
  for i in 0...xs.size
    s += xs[i] * xs[i]
  end
  s
end

xs = Array(Int64).new(1_000_000) { |i| (i % 10).to_i64 }
puts sum_of_squares(xs)
```

```text title="Output"
28500000
```

Each iteration reads its own `xs[i]` and adds to one sum, a **reduction**. The compiler gives each core a private partial sum and adds them at the end. `alice explain` reports it as "parallel loop".

A loop is parallelized automatically only when it is large, about 65,536 iterations or more, or when its body is heavy. Smaller loops run faster on one core.

### Making it a requirement: `par for`

Automatic parallelism is silent, so a small change can turn it off without anyone noticing. When a loop must run in parallel, write `par for`. Then the compiler either proves independence or stops with an error:

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

puts gradient(4, 3)
```

```text title="Output"
[0, 0, 0, 0, 0, 1, 2, 3, 0, 2, 4, 6]
```

Each value of `y` writes only its own row, `img[y * w + x]`, so rows can be computed in any order. Now a loop where each step needs the previous one:

```alice fail="AL0209"
def running(n : Int32) : Array(Int32)
  a = Array(Int32).new(n, 1)
  par for i in 1...n
    a[i] = a[i - 1] + 1
  end
  a
end
```

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

`a[i]` needs `a[i - 1]` from the iteration before. That is a real dependency, and the error says so instead of silently running the loop serially. For running totals like this, there is a parallel tool: `prefix_sum`, in 11.4.

## 11.3 Forking any two calls: `par`

Automatic forking needs a recursive call. For two independent, non-recursive pieces of work, write Bend's **parallel let**: `par a, b = f(x), g(y)`.

```alice
pure def checksum(n : Int64) : Int64
  s = 0_i64
  for i in 0...n
    s += i % 7
  end
  s
end

def both(n : Int64) : Int64
  par a, b = checksum(n), checksum(n * 2)
  a + b
end

puts both(1_000_000_i64)
```

```text title="Output"
8999992
```

The two calls must be pure, and the second may not use the first one's result. Otherwise it is an error rather than a silent serial run:

```alice fail="AL0211"
def log_and_return(n : Int64) : Int64
  puts "working on #{n}"
  n
end

def both(n : Int64) : Int64
  par a, b = log_and_return(n), log_and_return(n * 2)
  a + b
end
```

```text title="Error"
error[AL0211]: cannot fork `par`
```

Printing is a side effect: two prints in parallel could come out in either order.

## 11.4 Data-parallel building blocks

Some problems look serial but have well-known parallel algorithms. The Connection Machine, a 1980s supercomputer with 65,536 processors, was programmed with a handful of such **primitives**. Alice has them as array methods:

```alice
cups = [3, 1, 4, 1, 5, 9, 2, 6]
puts cups.prefix_sum

tea_ids = [2, 0, 1, 2, 2, 0]
puts tea_ids.histogram(3)

puts cups.compact { |n| n > 3 }

ids = [3, 1, 2]
cents = [300, 100, 200]
puts ids.sort_by_key(cents)
```

```text title="Output"
[3, 4, 8, 9, 14, 23, 25, 31]
[2, 1, 3]
[4, 5, 9, 6]
{[1, 2, 3], [100, 200, 300]}
```

| Method                   | Computes                                                  |
| ------------------------ | --------------------------------------------------------- |
| `prefix_sum`             | running totals: element `i` is the sum of elements `0..i` |
| `segmented_sum(flags)`   | one sum per segment; a `true` flag starts a new segment   |
| `histogram(k)`           | how often each key `0...k` occurs                         |
| `compact { \|x\| ... }`  | the elements that pass the test, in order                 |
| `scatter_add(idx, vals)` | adds each value at its index                              |
| `sort_by_key(vals)`      | sorts keys and carries the values along, stably           |

Each one splits the work over all cores. Integer results are exact. Float results are identical for any number of cores, though they may differ from a simple serial loop in the last digits, because additions happen in a different order.

## 11.5 The `Par` library

When you want to decide yourself, the runtime's `Par` class has the explicit forms. You saw `Par.For` in chapter 10:

```alice
sales = [3, 1, 4, 1, 5, 9, 2, 6]
puts Par.Sum(sales)
puts Par.Map(sales) { |x| x * 2 }
```

```text title="Output"
31
[6, 2, 8, 2, 10, 18, 4, 12]
```

The race checker applies to every block you pass to `Par`. [Chapter 15](https://alice-lang.org/documentation/learn/async.md) covers the other kind of concurrency, waiting for many things at once, with async code and actors.

## Project: a year of sales on all cores

The shop has a year of per-order sales and wants three numbers: the total, the running total at the end of each quarter, and which tea sold most. Each is a data-parallel operation:

```alice
def sales_data(n : Int32) : Array(Int32)
  Array(Int32).new(n) { |i| (i * 37 + 11) % 900 + 100 }
end

def tea_of(n : Int32) : Array(Int32)
  Array(Int32).new(n) { |i| (i % 13) * (i % 7) % 5 }
end

orders = 400_000
cents = sales_data(orders)
teas = tea_of(orders)

running = cents.prefix_sum
quarter = orders / 4
puts "total: #{cents.sum}"
puts "after Q1: #{running[quarter - 1]}, after Q2: #{running[2 * quarter - 1]}"

counts = teas.histogram(5)
best = (0...5).max_by { |t| counts[t] }
puts "orders per tea: #{counts}"
puts "best tea: #{best}"
```

```text title="Output"
total: 219796200
after Q1: 54948900, after Q2: 109897900
orders per tea: [180220, 57142, 57140, 52749, 52749]
best tea: 0
```

Nothing in this program mentions threads, and nothing can race.

:::caution\[Common mistakes]

- **Expecting small loops to run in parallel.** Automatic parallelism waits for enough work. Use `par for` when you require it.
- **A loop-carried dependency in `par for`.** `error[AL0209]`. Use `prefix_sum` or `segmented_sum`, or a plain `for`.
- **Side effects in forked calls.** `par` needs pure calls: `error[AL0211]`.
- **Measuring parallel speed with one tiny input.** Forking and chunking pay off on large work. Measure with realistic sizes.
  :::

## Exercises

1. Write a recursive `count_nodes(depth : Int32) : Int64` for a full binary tree (1 node at depth 0, `1 + 2 * count_nodes(depth - 1)` otherwise), structured so that it forks. Check with `alice explain`.
2. Given daily cups `[5, 3, 8, 6, 2, 7]`, print the running total with one method call.
3. Why can `for i in 0...n; b[i] = a[i] * 2; end` run in parallel, but `for i in 1...n; a[i] = a[i] + a[i - 1]; end` cannot?

<details>
<summary>Answers</summary>

1. Two independent recursive calls in one expression fork:

   ```alice cmd="explain"
   def count_nodes(depth : Int32) : Int64
     return 1_i64 if depth == 0
     1_i64 + count_nodes(depth - 1) + count_nodes(depth - 1)
   end

   puts count_nodes(20)
   ```

   ```text title="Output"
   ╭─────────────────────┬────────────────────────────────────────────────────────╮
   │ method              │ optimizations                                          │
   ├─────────────────────┼────────────────────────────────────────────────────────┤
   │ count_nodes         │ fork/join: independent recursive calls run in parallel │
   │ count_nodes__serial │ none                                                   │
   │ Main                │ none                                                   │
   ╰─────────────────────┴────────────────────────────────────────────────────────╯
   ```

2. Answer:

   ```alice
   puts [5, 3, 8, 6, 2, 7].prefix_sum
   ```

   ```text title="Output"
   [5, 8, 16, 22, 24, 31]
   ```

3. In the first loop, each iteration reads `a[i]` and writes `b[i]`: no iteration touches another's data. In the second, iteration `i` reads `a[i - 1]`, which iteration `i - 1` writes. The order matters, so the iterations are not independent.

</details>

## Summary

- Alice parallelizes only what it proves independent, so parallel code cannot race.
- Two independent pure calls with recursion fork automatically; deep calls run a serial copy.
- Large counted loops with independent iterations and reductions run on all cores. `par for` requires it (`AL0209`).
- `par a, b = f(x), g(y)` forks any two pure, independent calls (`AL0211`).
- `prefix_sum`, `segmented_sum`, `histogram`, `compact`, `scatter_add` and `sort_by_key` are parallel building blocks with reproducible results.
- `alice explain` reports forks and parallel loops.

[Chapter 12](https://alice-lang.org/documentation/learn/performance.md) looks at speed in general: how to measure it and what else the compiler does.

## Continue reading

- Previous: [10. Safety as compile errors](https://alice-lang.org/documentation/learn/safety.md)
- Next: [12. Performance](https://alice-lang.org/documentation/learn/performance.md)