parallel each

Some work is one big job made of many small ones that do not depend on each other: the same test for every number in a range, the same change to every order in a list. Put the word parallel in front of an each, and every core of the machine works on the loop at once. There are no threads to start and no work to share out by hand: it is the loop you would have written anyway. Here it finds the primes below a million:

mod primes;

import stdio use *;
import collections use *;
// parallel each runs on the same worker threads as actors
import actors;

// Is n a prime? Try every divisor up to its square root
fn isPrime(n u64) bool {
  var d = 2u64;
  while d * d <= n {
    if n % d == 0 { return false; }
    d += 1;
  }
  true;
}

fn main() {
  // Every core tests numbers at once, and the list keeps
  // the primes in order, as a plain each would
  let primes = new List[u64] <- parallel each n in 2u64 ..< 1000000u64 if isPrime(n) yield n;
  print <- "There are ", primes.len(), " primes below a million\n";
  print <- "The largest is ", primes[primes.len() - 1], "\n";

  // Adding them all up, on every core too
  print <- "They add up to ", primes.parallel().sum(), "\n";
}

It prints:

There are 78498 primes below a million
The largest is 999983
They add up to 37550402023

Try this: take the word parallel out of the loop, and the answers stay the same, with one core doing all the work. Then search below ten million, with and without it. On a 16-core laptop, the parallel loop takes about half a second, and the plain one about five.

One loop, every core#

A parallel each suits work where each pass stands on its own. Whether 7919 is a prime has nothing to do with whether 7920 is, so the numbers can be tested in any order, on any core, all at once.

You do not say how to split the work. The loop starts as one piece covering the whole range, and a worker with a big piece cuts it in half and leaves one half for an idle worker to take. So the work spreads evenly even when some passes take longer than others, as testing a big number takes longer than a small one. When the program reaches the statement after the loop, every pass has finished.

So the source has to be something that can be cut into pieces and says how big it is: a number range counting up by one, an array, a slice or a list. A generator, a cursor or a file hands out its items one after another and cannot be split, and the compiler says to collect it into a list first and walk the list. parallel is a keyword only directly before each; anywhere else it is an ordinary name.

The if after the range keeps only the numbers it holds for, as it does in a plain each. And the list is built just as Collections built one, with parallel in front of the each: each piece of the loop collects its own primes, and the pieces are joined in order at the end, so the list is the one a plain loop would have made, whichever pass finished first.

Getting the results out#

Because the passes really do run at the same time, a pass may not change a variable declared outside the loop: if two passes added to one total at the same moment, one of the additions could be lost. The compiler refuses it, and says what to do instead:

var total = 0;
parallel each n in 0 ..< 1000 {
  total = total + n;                 // refused
}

A 'parallel each' body may not write total, which is declared outside the loop: the passes run at the same time. Outside variables are read-only for the loop. Hand results back with the parallel builder, or 'mutItems()' on the items, or count with an Atomic.

The program above uses the parallel builder. A total such as the sum of the primes is a reduction, which boils a whole list down to one value: primes.parallel().sum() has each core add up a stretch of the list, and then adds the stretches' totals together. The stretches are cut by the list's length alone, so the answer is the same on every run, on any machine, a float sum included, though a float sum's last digits may differ from a plain loop's, which adds in another order. An Atomic is a number that every pass may add to safely, and Concurrency has it.

The rest of the body's rules follow from the passes running at once. continue skips the rest of a pass, but break, return and await are refused, since which passes had already run when one was reached would differ from run to run. A value from outside that holds an Rc may not be used in the body (copy what the loop needs into a local first); an Arc, an Atomic and a number are fine. A pass may send a message to an actor, and the messages go out after the loop, in the order a plain each would have sent them, so the actor sees the same order every run. Data parallelism in depth has every rule, and filling a buffer a row at a time.

Changing every item at once#

Sometimes the job is not to find anything, just to update everything. Back at the bakery, the year ends with ten percent off every order of $50 or more:

// A made-up year of the bakery's orders: what each customer spent, in dollars
var orders = new List[i32] <- each i in 1 .. 100000 yield i % 90 + 3;
print <- "Takings: $", orders.parallel().sum(), "\n";      // Takings: $4749610

// Ten percent off every order of $50 or more, all at once
parallel each o in orders.mutItems() {
  if *o >= 50 { *o -= *o / 10; }
}
print <- "After the discount: $", orders.parallel().sum(), "\n";   // $4430753

mutItems() gives each pass one order of its own to change, and no two passes are ever given the same one, so they can all change their orders at once. o stands for the order where it sits in the list, not a copy of it, and *o reaches through to the order itself; references like this one come later, in Memory.

Actors or a parallel each?#

Both put every core to work, and they suit different shapes of work. When the job is the same thing done to many items, with nothing to remember between them, a parallel each is the simplest thing to write. When the work falls into parts that each keep their own state and have an ongoing job, like the stock room, give each part to an actor. The two mix: a behaviour may run a parallel each over its actor's own data (below), and a pass may send a message to an actor.

A parallel each written in a behaviour pauses the behaviour where the loop ends, as an await does: the passes run on the workers, and the rest of the behaviour runs once the last has finished. Until then the actor runs nothing else, and the messages that arrive meanwhile wait their turn (In an actor's method).

Note: Not built yet: parallel each inside a generator; a source of your own that can be split; the parallel builder inside an actor's method; and a reduction over a number range. The actors package it runs on runs on Windows and Linux (x86-64), not yet on macOS.

You can now put every core of the machine to work, with actors for the standing roles and parallel each for the big loops. Every program so far has been one file; the last page of the Guide shows how a program grows past that, into modules, packages and tests.