Parallel For

What you’ll build

A program that turns colored pixels into gray ones, and squares a million numbers, with each loop spread over all the cores. Then you’ll see the rules that make a parallel loop safe, and what the compiler says when a loop breaks them.

A loop on every core

Parallel For i = a Until b runs its passes on the worker pool at once, in chunks, with the calling thread taking some too. The statement after it waits until every pass is done.

Import std.core
Import std.collections

Function Brightness(r: Int, g: Int, b: Int): Int => (r * 299 + g * 587 + b * 114) / 1000

Local red: Int[] = [255, 0, 0, 128]
Local green: Int[] = [0, 255, 0, 128]
Local blue: Int[] = [0, 0, 255, 128]
Local gray: Int[] = []
gray.Resize(red.Count, 0)

Parallel For i = 0 Until gray.Count
    gray[i] = Brightness(red[i], green[i], blue[i])
End For
Print(gray)

[76, 149, 29, 128]

Each pass reads its pixel’s three colors and writes its own element of gray. No two passes touch the same element, so they can run in any order, all at once. Resize makes room first: a Parallel For can’t add to an array, only set its elements.

A big one

A loop is worth running in parallel when its passes add up to real work. A million squares split over the cores:

Import std.core
Import std.collections

Local squares: Int64[] = []
squares.Resize(1_000_000, 0)

Parallel For i = 0 Until squares.Count
    squares[i] = (i As Int64) * i
End For

Local total: Int64 = 0
For s In squares
    total += s
End For
Print(total)

333332833333500000

The passes write their results into the array, and an ordinary loop adds them up afterward. To works as well as Until, and the loop counts up by 1, with no Step.

The rules

A pass runs at the same time as others, so the compiler holds it to what’s safe:

• An array from outside the loop, whose elements are Sendable, is shared, not copied: a pass changes it only at its own index, a[i], and when it changes an array, it reads that array only there too, since another pass may be changing any other element at once. It reads any element of an array it doesn’t change, and never adds to or removes from one.
• Everything else it uses from outside is a Sendable copy, made once, which it can’t change.
• It can’t Break or Return out of the loop, or let an error out, since the other passes are already running. Continue goes on to the next index.
• It can’t use what only the main thread can, like a plain Global.

Each rule is a compile error, which says what’s wrong:

Import std.core

Local a: Int[] = [1, 2, 3, 4]
Local sum = 0

Parallel For i = 0 Until a.Count - 1
    a[i + 1] = i
End For

Parallel For i = 1 Until a.Count
    a[i] = a[i - 1]
End For

Parallel For i = 0 Until a.Count
    sum += a[i]
End For

Parallel For i = 0 Until a.Count
    If a[i] > 2 Then Break
End For

   Compiling main.fb
main.fb:7:5: error: a Parallel For's body changes 'a', an array from outside the body, only at its own index, a[i]
  |
7 |     a[i + 1] = i
  |     ^
main.fb:11:12: error: a Parallel For's body that changes elements of 'a', an array from outside the body, reads it only at its own index, a[i], since another pass may be changing this one at once
   |
11 |     a[i] = a[i - 1]
   |            ^^^^^^^^
main.fb:15:5: error: a Parallel For's body can't change 'sum', which is outside it
   |
15 |     sum += a[i]
   |     ^^^
main.fb:19:22: error: Break can't leave a Parallel For, whose passes run at once
   |
19 |     If a[i] > 2 Then Break
   |                      ^^^^^
error: couldn't build main.fb because of 4 errors

To add up as it goes, a loop writes each pass’s result to its element, as above, or adds to an Atomic, which Mutex and Atomic covers.

What you learned

• Parallel For runs a loop’s passes on every core at once, and the next statement waits for all of them.
• An outside array is shared: each pass changes only its own element, a[i], and reads an array it changes only there.
• A pass can’t change other outside variables, or leave the loop with Break, Return, or an error.
• The compiler checks every rule, so a parallel loop with a race doesn’t build.