Parallel Loops​

parallel_for, parallel_transform and parallel_reduce run a loop over an array on every core with deterministic results: the same output at every thread count, byte-identical to the serial loop. The engine checks the body when the statement is reached, before any element runs, and a body it cannot prove safe is refused with a catchable error that names the construct; it is never run serially in silence. The table below is that contract, and the rest of the chapter walks through each form.

What a parallel body may do​

A text that starts with parallel_for: is raised when the statement is reached, before any element runs; most of them end with the position of the construct, at LINE:COL, left off here. 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. The rules cover everything a body reaches: the functions it calls, the methods it runs and the constructors and destructors of the objects it makes.

parallel_for and parallel_transform​

parallel_for runs a loop body over the elements of an array on every core. The loop variable is the element, so auto& mutates it in place. parallel_transform(arr, fn) returns a new array with out[i] = fn(arr[i]); it is the same loop in a different spelling, as below shows. thread_count() reports the worker count: the count the host set, else the machine's performance cores, at most one fewer than its hardware threads. Results never depend on it.

var nums = [1, 2, 3, 4, 5, 6, 7, 8];
parallel_for (auto& x : nums) {
    x = x * x;                    // each element mutated in place, across workers
}
print("squares: {}", to_json(nums));

int inc(int v) { return v + 1; }
print("mapped:  {}", to_json(parallel_transform(nums, inc)));

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

Counted loops​

parallel_for (int i = a; i < b; i++) runs its body once for each value the serial for loop gives i, split across the workers exactly as the range form splits an array holding those values (no such array is made: each element's value is computed from its position, so the loop takes no memory per element), and under the same body rules: out[i] = v is an index write. a, b and the step are evaluated once, in that order, before any element runs; a loop the serial form would run zero times runs no element. The form is kept to what provably visits each index once: one int variable, compared with <, <=, > or >=, stepped toward the bound by i++, i--, i += k or i -= k with k a constant or a name, and never written by the body. 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; }   // each index once, split across the workers
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 the same length in lockstep, one loop variable per array. Worker n owns segment n of every array, so a pre-allocated array of output structs is written in place: no construction per element, no result marshalling. This is the emitter shape, one input array and one output array of the same length, and the preferred way to produce several values per element.

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 < 6; i++) { bodies.push(Body(i * 10.0, i % 3 - 1.0)); samples.push(Sample()); }

parallel_for (auto& b, auto& s : bodies, samples) {   // one loop variable per array, walked in lockstep
    b.x += b.vx * 0.5;                                 // the input mutated in place
    s.pos = b.x;                                       // the pre-allocated output written in place
    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
40.0 false
50.5 true

Arrays of different length, the range itself as a zipped array, or a non-array raise a catchable error when the statement is reached, before any element runs: parallel_for: zipped array 2 has 1 elements, the range has 3 (zipped arrays must have the same length), parallel_for: zipped array 2 is the range itself, parallel_for: zipped array 2 is not an array.

parallel_transform is that zip​

parallel_transform(xs, fn) is parallel_for (auto& x, auto& o : xs, out) { o = fn(x); } over a fresh output of xs.size() slots, and it costs exactly that loop plus the output. When fn only reads its parameter, its body runs inlined in the loop with the parameter bound to the element in place, so there is no call and no copy per element. A fn that mutates its parameter works on a private copy, so the source array is never touched either way. Any result type works, objects included: the returned array holds copies that alias nothing.

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; }              // reads its parameter: the body runs inlined in the loop
Body stepped(Body b) { b.x += b.vx; return b; }         // mutates its copy: the source is untouched

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}`);

[1.0,11.0,21.0,31.0] moved 31.0 source 30.0

An optional third argument, parallel_transform(arr, fn, weight_fn), balances chunks by per-element effort (e.g. weigh strings by length):

var texts = ["7", "42", "1999", "3", "250"];
int parse_one(string s) {                            // digits -> int, no host calls
    var n = 0;
    for (var i = 0; i < s.size(); i++) { n = n * 10 + (s[i] - '0'); }
    return n;
}
float w(string s) { return s.size(); }               // heavier strings, fatter chunks
var parsed = parallel_transform(texts, parse_one, w);
print("parsed: {}", to_json(parsed));

parsed: [7,42,1999,3,250]

Control flow in the body​

The body is the loop's body: continue moves to the next element, and so does a return written at the body's top level (iterations are independent, there is nothing to return to). A loop-level break is a parse error, 'break' is not allowed in a parallel_for body: iterations are independent; use 'continue' for the next element. Inside a nested loop or switch, break and continue keep their usual meaning.

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; }        // next element
    if (w == "skip") { return; }      // also the next element: the body is the loop's body
    k = w.size();
}
print("{}", to_json(kept));

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

A throwing element fails the whole call with the first error in iteration order, so the error is as deterministic as the results: it is the serial loop's first error. Index writes come back up to the failing element, exactly the serial loop's stores; an element the body changes in place past the failing one may or may not have been written, since other workers keep running their elements until the region joins.

Captured reads​

The body may read enclosing globals: scalars, strings, and value-semantic containers. Every worker sees the content as of the call (the "barrier"), identical at every worker count. Provisioning is automatic and tiered: a container of primitives or strings touched only by subscript reads and size(), length() and empty() is a zero-copy borrow (workers read the shared storage in place; a string read copies its bytes into a worker-owned string); anything else (nested containers, iterated or whole-value reads) is copied once per worker at the barrier and charged to memory_cap. This is what makes the "shared read-only grid" and "shared palette" renderer shapes cheap:

var gw = 4;
var grid = [];                       // the shared input: three rows of gw cells
for (var i = 0; i < gw * 3; i++) { grid.push(i); }
int row_sum(int row) {
    var total = 0;
    for (var x = 0; x < gw; x++) { total += grid[row * gw + x]; }   // captured reads
    return total;
}
var row_indices = [0, 1, 2];
var sums = parallel_transform(row_indices, row_sum);   // grid rides along for free
print("row sums: {}", to_json(sums));

row sums: [6,22,38]

A function or method the body calls may take enclosing state through a const T& parameter: that is a captured read, provisioned by the same tiers, so a helper that only subscripts its parameter (directly or by handing it on to another const T&) reads the shared storage in place. A lambda's captures given to parallel_transform or parallel_reduce follow the same tiers. A plain T& parameter could write the argument, so it is refused, and when the function never writes through it the error names the const T& to declare instead:

array<int> heights = [3, 9, 4, 7, 1, 8];
int peak(const array<int>& h, int i) {      // reads its argument in place: 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> spots = [0, 1, 2, 3, 4, 5];
array<int> peaks = [0, 0, 0, 0, 0, 0];
parallel_for (int i : spots) { peaks[i] = peak(heights, i); }
print(to_json(peaks));
try { parallel_for (int i : spots) { peaks[i] = tally(heights); } } 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 13:55

Captured objects​

A body reads a captured object through its fields and its methods, with no write to it from any lane. That holds by construction for a value class, an instance whose fields hold values only (primitives, strings, containers of them, nested value-class instances), and for a shared_ptr to one: each worker reads its own view, a copy taken when the statement is reached. A script method called on it may run when it writes no part of the object, which the statement checks before any element runs. A C++ class's instance is captured too: every worker reaches the same C++ object, so its binding decides, as for any C++ call: methods the host left unmarked run (on a captured object only the const ones), and a method registered serial_method is refused when it is called (the binder). A captured handle is used through its members and methods only, since a worker's view is not the object itself, and the statement refuses a range whose elements reach a captured object, since an element's lane may write it while the others read their views. A captured object holding a handle, a function, a var field or a C++ object, one whose class runs a destructor, and a weak_ptr, stay refused.

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); }

[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

Writes to enclosing state​

Writes to enclosing state are errors, with one proven exception, the index write below. The elements behind the loop variables are what a body mutates. Assigning to captured state in any other shape (g = ..., g[j] = ... with an index that is not a loop variable, compound stores, g.push(...) (any mutating or unrecognized method on a captured value), var& r = g aliases, passing captured state to a non-const reference parameter (a const T& one reads it, above), or for (auto& v : g)) raises an error like parallel_for: body writes enclosing state 'total' at 3:33. A captured object is read-only like any captured value: cam.x = 1.0 raises parallel_for: member store reaches captured state 'cam' (captured reads are read-only) at 4:45; per-element object state goes through the arrays. Calls to other script functions (including recursion) and builtin container/string methods are fine.

Index writes​

out[i] = v (and op=, ++, --) is legal when out is an enclosing array and i a loop variable the body never writes (directly, or through a function's or method's T& parameter that writes it). The loop variable's values must name distinct slots, which the statement checks when it is reached: two elements carrying one index raise parallel_for: elements 2 and 5 write 'out' at the same index 4. The body may touch out only as out[i], since reading another slot would race the writes (parallel_for: body touches 'out' beyond the slot it writes, out[i] at 4:20). Each worker writes a private copy of out, and the statement copies every element's slot back in element order, up to the first failing element: exactly the stores the serial loop makes.

array<int> order = [3, 0, 2, 1];
array<int> placed = [0, 0, 0, 0];
parallel_for (int slot : order) {
    placed[slot] = slot * 10;          // each element writes the slot its value names
}
print("{}", to_json(placed));

[0,10,20,30]

Constructing objects​

A body constructs objects in every spelling: Hit(r, d), Hit h(r, d);, Hit h; and new Hit(r, d), and through a converting constructor wherever a value converts into a slot of the class: a declaration (Box b = x;), an argument, a return value or a store. The new object belongs to the worker that made it, so its constructor writes its fields freely; everything else that construction runs follows the body's rules. When the statement is reached, before any element runs, it checks the constructor each call can reach (every one its argument count admits), the base constructors its initializer list names (a base it does not name is default-constructed), each level's field initializers, and 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. Class code may call script functions, methods on the object, and the same pure host functions a body may.

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<int> rays = [0, 1, 2, 3];
array<Hit> hits = [Hit(), Hit(), Hit(), Hit()];
parallel_for (int r : rays) {
    hits[r] = Hit(r, r * 0.5);         // each worker constructs the hit its ray owns
}
print("{} {} {}", hits[3].tag, hits[3].at.y, hits[0].ray);

hit-3 3.0 0

Construction code that writes state the body does not own refuses the statement, and the error names where that code sits: a constructor, a field initializer or a destructor.

int next_id = 0;
int deaths = 0;
class Tick { int id = 0; Tick() { id = next_id; next_id++; } }
class Tag { int id = next_id++; }
class Res { int v = 0; ~Res() { deaths++; } }
array<int> xs = [1, 2, 3];
try { parallel_for (auto& x : xs) { Tick t; x = t.id; } } catch (e) { print(e); }
try { parallel_for (auto& x : xs) { Tag t; x = t.id; } } catch (e) { print(e); }
try { parallel_for (auto& x : xs) { Res r; x = r.v; } } catch (e) { print(e); }

parallel_for: body writes enclosing state 'next_id' in the constructor of 'Tick' at 3:49
parallel_for: body writes enclosing state 'next_id' in a field initializer of 'Tag' at 4:22
parallel_for: body writes enclosing state 'deaths' in the destructor of 'Res' at 5:33

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, while the script levels follow the rules above. A host class whose constructor or destructor touches state other objects share (a registry, a cache, a service) is bound with .serial_only_constructor() (see the binder); a body that constructs it, or a script class over it, is refused before any element runs, with parallel_for: C++ class 'Sprite' is marked serial_only_constructor() and cannot be constructed in a parallel body at 3:48 or parallel_for: class 'Glowing' has a C++ base 'Sprite' marked serial_only_constructor() and cannot be constructed in a parallel body at 4:49. An object of such a class that dies on a worker anyway is released when the statement's workers are done, on the calling thread, in element order.

C++ calls​

Bound C++ functions, static methods and methods are parallel unless the host registered them serial (the binder). The library's own builtins are serial apart from pure math, to_string, the web:: text functions and crypto:: (all but crypto::sha256_file), so print in a body is refused before any element runs: parallel_for: host function 'print' is marked serial_function() and cannot be called in a parallel body at 3:5, and a serial static method reads parallel_for: C++ static method 'Sound::play' is marked serial_static_method() and cannot be called in a parallel body at 3:5. A method's mark covers its non-const overloads, so a const getter of the same name stays parallel. A method's receiver class is known only when it is called, so a serial method is refused then: C++ method 'publish' of 'Meter' is marked serial_method() and cannot be called in a parallel body. A non-const C++ method, or a store to a C++ property, runs only on an object the body owns: its element (a range or zipped element, which the statement proves the only element of its object, or a parallel_reduce accumulator) or one it made. On any other object, such as one a C++ function returns, only const methods run, and anything else is refused with C++ method 'add' of 'Meter' changes an object this parallel body did not make (only its const methods may run on it) or C++ property 'level' of 'Meter' is stored on an object this parallel body did not make (only an object it made takes stores).

Random numbers​

A body draws from a random it captures, in the body and in the functions, methods and constructors it calls. The statement takes one draw from the captured generator to seed the streams, and each element (the chunk, for parallel_reduce) draws from its own stream, which depends only on that draw and the element's index. So the loop gives the same numbers on any number of cores, and the generator after it is the same too: it has moved one draw for each statement that captured it. The numbers are not the ones the serial loop would draw, since a serial loop takes its draws in the order its elements run and a parallel one has no such order. A random an element owns (an array<random> zipped beside the data, or a field of the element's class) or one the body makes draws as it would anywhere. The statement proves each element's generator its own object, as it does every C++ value an element holds, and refuses two elements holding one generator with parallel_for: elements 1 and 2 share one 'random' in field 'brain' (an element owns the C++ values it holds: give each element its own, or capture one from outside the loop). Reseeding a captured generator in a body is refused before any element runs; seed before the loop (Random Numbers & Crypto has the exact rule).

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); }   // the same drops on any number of cores
print(drops.join(" "));
print(loot.next_int(1, 100));                                     // the generator moved one draw for the loop

array<random> brains = [random(1), random(2), random(3)];        // one stream per monster
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); }

class Monster { int hp = 10; random brain; }                       // or a field: each monster's own generator
array<Monster> pack = [];
for (int i = 1; i <= 3; ++i) { Monster m; m.brain.seed(i); pack.push(m); }
parallel_for (auto& m : pack) { m.hp -= m.brain.next_int(1, 6); }
print(to_string(pack[0].hp) + " " + pack[1].hp + " " + pack[2].hp);

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 11:45
5 9 5

Handles as elements​

An array of shared_ptr<T> or weak_ptr<T> elements runs when they name distinct objects. The statement checks, once when it is reached, that no object appears at two elements of the range and its zipped arrays, and raises parallel_for: elements 0 and 3 hold the same object (an object a body reaches through a handle element belongs to one element) otherwise. The check proves that one worker reaches each object. It proves nothing about what the object holds: its class must still be a flat value class (fields that are values, no handles), as for an element held by value. Another holder of the same object elsewhere in the program is fine, since nothing else runs during the loop.

Reductions: parallel_reduce​

parallel_reduce(xs, init, step, combine) folds an array on every core: xs splits into chunks whose size depends on xs.size() alone, each chunk folds its elements in order with step(acc, x) starting from its own copy of init, and the chunk results combine left to right with combine(a, b). The chunking never depends on the worker count, so a float sum is bit-identical on every machine. init should be combine's identity (0 for a sum), since every chunk starts from it; an empty array returns it. The accumulator may be a container or an object, and step is admitted like a parallel_for body: it may not write enclosing state, and a throw from it fails the call as from parallel_for. step may be a lambda, its captures provisioned as a parallel_for body's are. combine is ordinary code: it runs on the calling thread after the chunks join, left to right, so it may print, count its calls or write enclosing state. step's body runs grafted into the chunk loop, so no call is paid per element; a step that takes its accumulator by reference (void step(T& acc, x), or -> T& returning acc) folds the chunk's accumulator in place with no copy in or out, the form for a container or object accumulator, while the by-value form T step(T acc, x) suits a scalar. The element x is taken by value. The input may hold class instances: step reads their fields and runs their methods and operators under the body rules, and every element must be its own object, as a zipped array's are, so an input holding one shared_ptr twice is refused with parallel_reduce: input elements 0 and 1 hold the same object (an object the step reaches through a handle element belongs to one element).

array<float> prices = [4.5, 12.0, 7.25, 3.0, 9.5];
float add(float a, float b) { return a + b; }
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; }
print(`total ${parallel_reduce(prices, 0.0, add, add):.2f}`);
Span r = parallel_reduce(prices, Span(), widen, join);   // an object accumulator
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}`);

total 36.25
span 3.00..12.00 big 28.75

The long form is the same loop written out: a zipped array of per-chunk accumulators and their chunk numbers, each chunk folding its slice in place, then a serial fold of the partial results. A body that adds into a captured total instead raises the enclosing-state error.

array<float> prices = [4.5, 12.0, 7.25, 3.0, 9.5];
int size = 2;
array<float> partial = [0.0, 0.0, 0.0];   // one accumulator per chunk of `size` elements
array<int> chunk_ids = [0, 1, 2];
parallel_for (auto& p, int c : partial, chunk_ids) {
    for (int i = c * size; i < c * size + size && i < prices.size(); i++) { p += prices[i]; }
}
print(`total ${partial.reduce((s, p) => s + p, 0.0):.2f}`);

total 36.25

Choosing a shape​

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