Parallel Loops​

parallel_for, parallel_transform and parallel_reduce run a loop over an array on every core. The engine checks the body when the statement is reached, before any element runs. A body it cannot prove safe is refused with a catchable error that names the construct. It is never run serially in silence.

The model​

1. An iteration owns its element. The loop variables are the elements: auto& changes one in place, a by-value variable is the body's copy. Every element is a value, or a handle to an object no other element names.
2. Everything outside the loop is captured and read-only. The body reads enclosing state as it was when the statement was reached. A write to it is refused.
3. Results leave through writes that cannot collide: the element, the same position of a zipped array, out[i] where i is a loop variable and every element carries a different index, the array parallel_transform returns, or a parallel_reduce accumulator.
4. The rules follow the calls. They cover the functions the body calls, the methods it runs and the constructors and destructors of the objects it makes. An object the body makes belongs to its iteration.
5. The worker count never changes the result. thread_count() reports it: the count the host set, else the machine's performance cores, at most one fewer than its hardware threads.

With deterministic inputs, the elements, the index writes and the error (the first failing element in iteration order) are the serial loop's, on any number of workers. Four things are not the serial loop's:

• A captured random gives the same numbers at every worker count, but not the numbers a serial loop would draw (Random numbers).
• crypto:: calls, and a random the body makes without a seed, differ on every run, as they do anywhere.
• parallel_reduce folds by chunk. The result is bit-identical at every worker count, but a float fold is grouped differently from a left-to-right loop, and a non-identity init is counted once per chunk (Reductions).
• After an error, index writes hold up to the failing element, as in the serial loop, but an element changed in place past it may or may not have been written.

A read that would depend on scheduling, such as time::now(), is refused.

parallel_for and parallel_transform​

parallel_for runs its body once per element. parallel_transform(arr, fn) returns a new array with out[i] = fn(arr[i]).

var nums = [1, 2, 3, 4, 5, 6, 7, 8];
parallel_for (auto& x : nums) { x = x * x; }           // auto& is the element itself
print(to_json(nums));

int inc(int v) { return v + 1; }
print(to_json(parallel_transform(nums, inc)));         // a new array; nums is not touched

[1,4,9,16,25,36,49,64]
[2,5,10,17,26,37,50,65]

An element may be an instance of a class whose fields hold values. Math vectors are values (Math): an array of them, a class holding them and a captured one all qualify.

using math::vec2;
class Particle { vec2 pos; vec2 vel = vec2(0.0, 2.0); }
vec2 gravity = vec2(0.0, -0.5);
array<Particle> sparks;
for (int i = 0; i < 4; ++i) {
    Particle p;
    p.vel.x = i;
    sparks.push(p);
}
parallel_for (auto& p : sparks) {
    p.vel += gravity;             // gravity is captured: read, never written
    p.pos += p.vel;               // p is this iteration's element
}
print(sparks[0].pos, " ", sparks[3].pos);

(0.0, 1.5) (3.0, 1.5)

Counted loops​

parallel_for (int i = a; i < b; i++) runs its body once for each value the serial for gives i, with no array made and no memory per element. The form is kept to what provably visits each value once:

• one int (or auto) variable, never written by the body
• compared with a bound by <, <=, > or >=
• stepped toward the bound by i++, i--, i += k or i -= k, with k a constant or a name.

a, b and the step are evaluated once, in that order, before any element runs. Any other shape is refused when the script loads. A step that would never end the serial loop, or a last step that would overflow, is refused when the statement is reached.

int n = 8;
array<int> squares = [0, 0, 0, 0, 0, 0, 0, 0];
parallel_for (int i = 0; i < n; i++) { squares[i] = i * i; }
array<int> marks = [0, 0, 0, 0, 0, 0, 0, 0];
parallel_for (int i = n - 2; i >= 0; i -= 2) { marks[i] = 1; }
print(`${to_json(squares)} ${to_json(marks)}`);
int none = 0;
try { parallel_for (int i = 0; i < n; i += none) { } } catch (e) { print(e); }

[0,1,4,9,16,25,36,49] [1,0,1,0,1,0,1,0]
parallel_for: a counted loop's step of 0 never reaches its bound (the serial loop would not end)

The zip form​

The zip form walks several arrays of one length in lockstep, one loop variable per array. To produce several values per element, allocate the outputs before the loop and write them in place. Every zipped array is a separate array of the range's length.

class Body { float x = 0.0; float vx = 0.0; Body() {} Body(float px, float v) { x = px; vx = v; } }
class Sample { float pos = 0.0; bool moving = false; }
array<Body> bodies = [];
array<Sample> samples = [];
for (int i = 0; i < 4; i++) { bodies.push(Body(i * 10.0, i % 3 - 1.0)); samples.push(Sample()); }

parallel_for (auto& b, auto& s : bodies, samples) {
    b.x += b.vx * 0.5;            // the input, changed in place
    s.pos = b.x;                  // the output slot at the same position
    s.moving = b.vx != 0.0;
}
for (auto& s : samples) { print(`${s.pos:.1f} ${s.moving}`); }

-0.5 true
10.0 false
20.5 true
29.5 true

parallel_transform is that zip​

parallel_transform(xs, fn) is parallel_for (auto& x, auto& o : xs, out) { o = fn(x); } over a fresh out of xs.size() slots.

• fn is a script function or lambda that takes its element by value. One that only reads its parameter costs no call and no copy per element. One that changes its parameter changes a private copy, so the source array is never touched.
• Any result type works, objects included. The returned array holds copies that alias nothing.
• An optional third argument, weight_fn, balances the chunks by effort per element. It takes one parameter by value and returns a finite, non-negative number.

class Body { float x = 0.0; float vx = 0.0; Body() {} Body(float px, float v) { x = px; vx = v; } }
array<Body> bodies = [];
for (int i = 0; i < 4; i++) { bodies.push(Body(i * 10.0, 1.0)); }

float next_x(Body b) { return b.x + b.vx; }
Body stepped(Body b) { b.x += b.vx; return b; }          // changes its own copy

var xs = parallel_transform(bodies, next_x);
var moved = parallel_transform(bodies, stepped);
print(`${to_json(xs)} moved ${moved[3].x:.1f} source ${bodies[3].x:.1f}`);

var texts = ["7", "42", "1999"];
int digits(string s) { return s.size(); }
float cost(string s) { return s.size(); }                // longer strings weigh more
print(to_json(parallel_transform(texts, digits, cost)));

[1.0,11.0,21.0,31.0] moved 31.0 source 30.0
[1,2,4]

Control flow in the body​

continue, and a return at the body's top level, move to the next element. A loop-level break is a parse error, since iterations are independent. Inside a nested loop or switch, break and continue keep their usual meaning, and try/catch works. An element that throws fails the whole call with the first error in iteration order.

var words = ["keep", "", "skip", "keep", "", "keep"];
array<int> kept = [0, 0, 0, 0, 0, 0];
parallel_for (auto& w, auto& k : words, kept) {
    if (w == "") { continue; }
    if (w == "skip") { return; }      // the next element, like continue
    k = w.size();
}
print(to_json(kept));

[4,0,0,4,0,4]

Reductions: parallel_reduce​

parallel_reduce(xs, init, step, combine) folds an array on every core:

1. xs splits into chunks whose size depends on xs.size() alone, never on the worker count.
2. Each chunk folds its elements in order with step(acc, x), starting from its own copy of init.
3. The chunk results combine left to right with combine(a, b). An empty array returns init.

• step is a script function or lambda of two parameters and follows the body rules. It takes its element by value. The input may hold class instances, each its own object.
• A scalar accumulator suits the by-value form T step(T acc, x). A container or object accumulator is taken by reference (void step(T& acc, x), or -> T& returning acc) and folds in place with no copy in or out.
• combine is ordinary code of two parameters. It runs on the calling thread after the chunks join, so it may print or write enclosing state.

array<float> prices = [4.5, 12.0, 7.25, 3.0, 9.5];
float add(float a, float b) { return a + b; }
print(`total ${parallel_reduce(prices, 0.0, add, add):.2f}`);

class Span { float lo = 1000000.0; float hi = -1000000.0; }
void widen(Span& r, float x) { if (x < r.lo) { r.lo = x; } if (x > r.hi) { r.hi = x; } }   // folds in place
Span join(Span a, Span b) { if (b.lo < a.lo) { a.lo = b.lo; } if (b.hi > a.hi) { a.hi = b.hi; } return a; }
Span r = parallel_reduce(prices, Span(), widen, join);
float big = parallel_reduce(prices, 0.0, [](float a, float x) { return x > 5.0 ? a + x : a; }, add);
print(`span ${r.lo:.2f}..${r.hi:.2f} big ${big:.2f}`);

array<float> ones = [];
for (int i = 0; i < 100; i++) { ones.push(1.0); }
print(parallel_reduce(ones, 0.0, add, add), " ", parallel_reduce(ones, 100.0, add, add));   // 100.0 counted once per chunk

total 36.25
span 3.00..12.00 big 28.75
100.0 800.0

Captured reads​

The body reads enclosing scalars, strings, math vectors, arrays and maps, and runs the read-only builtins on them. Every worker sees their content as of the statement.

• A container of primitives or strings that the body only subscripts, or asks size(), length() or empty(), is read in place with no copy. Anything else captured is copied once per worker, and the copies count toward the memory cap.
• A function or method the body calls takes enclosing state through a const T& parameter as a captured read. A plain T& parameter could write it and is refused; when the function never writes through it, the error names the const T& to declare.
• The lambda given to parallel_transform or parallel_reduce reads its captures the same way.

Writes to enclosing state​

Every write to captured state is refused: assignment, compound assignment, ++/--, a mutating or unrecognized method (g.push(...)), a non-const reference that aliases it (var& r = g), an argument to a non-const reference parameter (directly or as an arm of c ? a : b), and for (auto& v : g). A const T& declaration or a const auto& loop reads it.

Index writes​

The one exception is out[i] = v (and op=, ++, --) into an enclosing array:

• i is a loop variable the body never writes, directly or through a T& parameter.
• Every element carries a different index, which the statement checks when it is reached. An index past the array raises the serial loop's error.
• The body touches out only as out[i]. Reading another slot would race the writes.

array<int> heights = [3, 9, 4, 7, 1, 8];
int peak(const array<int>& h, int i) {          // const T&: a captured read, no copy
    int best = h[i];
    if (i > 0 && h[i - 1] > best) { best = h[i - 1]; }
    if (i + 1 < h.size() && h[i + 1] > best) { best = h[i + 1]; }
    return best;
}
int tally(array<int>& h) { return h.size(); }   // never writes h, but does not say so
array<int> peaks = [0, 0, 0, 0, 0, 0];
parallel_for (int i = 0; i < 6; i++) { peaks[i] = peak(heights, i); }
print(to_json(peaks));
try { parallel_for (int i = 0; i < 6; i++) { peaks[i] = tally(heights); } } catch (e) { print(e); }
int total = 0;
try { parallel_for (int h : heights) { total += h; } } catch (e) { print(e); }
array<int> order = [3, 3, 1, 0];
try { parallel_for (int slot : order) { peaks[slot] = 1; } } catch (e) { print(e); }

[9,9,9,7,8,8]
parallel_for: argument passes enclosing state 'heights' to reference parameter 'h' of 'tally' (captured reads are read-only; 'tally' only reads it: declare it const array<int>& h) at 12:63
parallel_for: body writes enclosing state 'total' at 14:40
parallel_for: elements 0 and 1 write 'peaks' at the same index 3

Captured objects​

A captured object is read through its fields and methods and written by no iteration.

class Vec3 {
    float x = 0.0; float y = 0.0; float z = 0.0;
    Vec3(float a, float b, float c) { x = a; y = b; z = c; }
    float dot(Vec3 o) { return x * o.x + y * o.y + z * o.z; }   // writes nothing of its object
    void scale(float k) { x *= k; y *= k; z *= k; }
}
Vec3 sun = Vec3(0.0, 1.0, 0.0);
array<float> light = [0.0, 0.0, 0.0, 0.0];
parallel_for (int i = 0; i < 4; i++) { light[i] = sun.dot(Vec3(i * 1.0, i * 0.5, 0.0)); }
print(to_json(light));
try { parallel_for (int i = 0; i < 4; i++) { sun.scale(2.0); } } catch (e) { print(e); }
try { parallel_for (int i = 0; i < 4; i++) { sun.x = 1.0; } } catch (e) { print(e); }

[0.0,0.5,1.0,1.5]
parallel_for: method 'scale' of 'Vec3' writes its object, and captured 'sun' is read-only (write a local copy, or the element) at 11:50
parallel_for: member store reaches captured state 'sun' (captured reads are read-only) at 12:50

Calling functions​

A body calls named script functions (recursion included), the builtin container and string methods on its own values, and host functions the host did not register serial. The target of a call must be known when the statement is reached:

• A global name that holds a function or a lambda is called directly.
• A call through a local of the enclosing function, a local of the body or a parameter is refused.
• A function read as a value, to store it or to pass it, is refused. A body writes no lambda of its own.

int twice(int v) { return v * 2; }
var bump = [](int v) { return v + 1; };      // a global that holds a lambda
array<int> xs = [1, 2, 3, 4];
parallel_for (auto& x : xs) { x = bump(twice(x)); }
print(to_json(xs));

int apply(var f, int v) { return f(v); }
void local_target() {
    var pick = twice;
    try { parallel_for (auto& x : xs) { x = pick(x); } } catch (e) { print(e); }
}
local_target();
try { parallel_for (auto& x : xs) { x = apply(twice, x); } } catch (e) { print(e); }
try { parallel_for (auto& x : xs) { var keep = twice; } } catch (e) { print(e); }
try { parallel_for (auto& x : xs) { print(x); } } catch (e) { print(e); }

[3,5,7,9]
parallel_for: call target 'pick' is not a function known at admission time at 10:45
parallel_for: call target 'f' is not statically resolvable in a parallel body at 7:34
parallel_for: captured name 'twice' is a function value (only direct calls to statically-known functions are allowed in a parallel body)
parallel_for: host function 'print' is marked serial_function() and cannot be called in a parallel body at 15:37

C++ calls​

Bound C++ functions, static methods and methods run on the worker unless the host registered them serial_function, serial_static_method or serial_method (the binder).

• A serial function or static method refuses the statement before any element runs. A serial method is refused when it is called, since its receiver's class is known only then. The mark covers the method's non-const overloads, so a const getter of the same name stays parallel.
• A non-const C++ method, or a store to a C++ property, runs only on an object the body owns: its element, a parallel_reduce accumulator, or an object it made. On any other object only const methods run.
• The library's builtins follow the same rule. The table lists the serial ones; print is among them.

Constructing objects​

A body constructs script classes in every spelling: Hit(r, d), Hit h(r, d);, Hit h;, new Hit(r, d), and the converting constructor a typed slot runs (Box b = x;, an argument, a return, a store). The new object belongs to the worker that made it, so its constructor writes its fields freely. Everything else the construction runs follows the body rules, and the statement checks it before any element runs:

• every constructor the call's argument count admits
• the base constructors its initializer list names (an unnamed base is default-constructed)
• each level's field initializers
• the destructor of every class whose instance can die in the body: an object the body makes, an element it replaces, and whatever their fields hold.

An error from this code names where it sits: a constructor, a field initializer or a destructor.

string PREFIX = "hit-";
class Vec { float x = 0.0; float y = 0.0; Vec() {} Vec(float a, float b) { x = a; y = b; } }
class Hit {
    int ray = -1;
    Vec at;
    string tag = PREFIX;
    Hit() {}
    Hit(int r, float d) { ray = r; at = Vec(d, d * 2.0); tag = tag + to_string(r); }
}
array<Hit> hits = [Hit(), Hit(), Hit(), Hit()];
parallel_for (int r = 0; r < 4; r++) { hits[r] = Hit(r, r * 0.5); }
print("{} {} {}", hits[3].tag, hits[3].at.y, hits[0].ray);

hit-3 3.0 0

C++ classes and hybrids​

A class the host binds, and a script class over one, construct in a body too: the host's constructor and destructor are taken to be safe on any thread. A host class whose constructor or destructor touches shared state (a registry, a cache, a service) is bound with .serial_only_constructor() (the binder), and a body that constructs it, or a script class over it, is refused before any element runs. An object of such a class that dies on a worker anyway is released on the calling thread when the workers are done, in element order.

Random numbers​

crypto:: runs in a body too, apart from crypto::sha256_file, and is never reproducible. Random Numbers & Crypto has the generator's side of these rules.

random loot(5);
array<int> drops = [0, 0, 0, 0, 0, 0, 0, 0];
parallel_for (auto& d : drops) { d = loot.next_int(1, 100); }   // captured: one stream per element
print(drops.join(" "));
print(loot.next_int(1, 100));                                     // loot moved one draw for the loop

array<random> brains = [random(1), random(2), random(3)];        // owned: one generator per element
array<int> hp = [10, 10, 10];
parallel_for (auto& h, auto& brain : hp, brains) { h -= brain.next_int(1, 6); }
print(hp.join(" "));

try { parallel_for (auto& d : drops) { loot.seed(d); } } catch (e) { print(e); }

51 17 31 91 93 79 47 67
61
5 9 5
parallel_for: random::seed cannot be called on captured 'loot' in a parallel body (seed before the loop: each element draws its own stream from it) at 12:45

Handles as elements​

An array of shared_ptr<T> or weak_ptr<T> elements runs when no object appears at two elements of the range and its zipped arrays, which the statement checks when it is reached. Its class must still be a flat value class. Another holder of the object elsewhere in the program is fine, since nothing else runs during the loop.

Choosing a shape​

Use captured reads for shared inputs, a zipped output array or out[i] for per-element results, and parallel_reduce for a total. Where the output shape is not known up front, elements shaped [input..., tag] come back from parallel_transform as [tag, outputs...], collected from the result in iteration order.

What a parallel body may do​

One row per construct. The reference lists every refusal text with its cause (Parallel bodies); the last column links each row to its texts there.

• A text that starts with parallel_for: is raised when the statement is reached, before any element runs. parallel_transform and parallel_reduce raise the same texts under their own names.
• A text without the prefix is raised when the body runs the construct, because only then is the receiver known.
• Most texts end with the position of the construct, at LINE:COL.