The Scaly Programming Language

Chapter 4

Loops on All Cores

A Plain for

Scaly has no parallel loop. It has for, and the compiler decides for each for of a program whether its rounds may run at the same time. This chapter is built around one program: how many points of a grid lie in the Mandelbrot set. Each row of the grid is counted by a function, and a for over the rows puts each count into a slot of its own:

function row_count(y: int, n: int) returns int
{
    let ci (2.0 * (y as double) / (n as double)) - 1.0
    var count 0
    var x 0
    while x < n
    {
        let cr (2.0 * (x as double) / (n as double)) - 1.5
        var zr: double 0.0
        var zi: double 0.0
        var i 0
        var inside true
        while i < 50 and inside
        {
            let tr zr * zr - zi * zi + cr
            zi := 2.0 * zr * zi + ci
            zr := tr
            if zr * zr + zi * zi > 4.0
                inside := false
            i := i + 1
        }
        if inside
            count := count + 1
        x := x + 1
    }
    count
}

let n 2000
var counts Vector[int](n as size_t)
for y in n
    counts.put(y as size_t, row_count(y, n))

var total 0
for c in counts
    total := total + c
print "mandelbrot `n`: `total` points inside"
$ scaly run mandelbrot.scaly
mandelbrot 2000: 1588053 points inside
$ scalyc --task-plan mandelbrot.scaly
task-plan: 2 for-loops, 2 parallelizable
task-plan: mandelbrot.scaly:31:1: parallel
task-plan: mandelbrot.scaly:35:1: parallel
$ SCALY_WORKERS=1 scaly run mandelbrot.scaly
mandelbrot 2000: 1588053 points inside

Nothing in the program says that the rows may be counted side by side; the compiler sees it. row_count is a function, so it reads its arguments and nothing else, and the round for row y writes only slot y of counts. The second loop adds the counts up, which the compiler knows how to split as well. The while loops inside row_count run as written: only a for is ever handed to the cores.

Built with scaly build --release and n at 8000, the program took 4.1 seconds with SCALY_WORKERS=1 and 0.54 seconds without, on a laptop with eight performance cores and two efficiency cores: 7.5 times as fast, from the same source.

What a Round May Do

A round runs in parallel with the others when nothing it does can be seen by another round. The compiler checks each for for that, and it accepts a body whose rounds do only these things:

  • read anything that does not change while the loop runs: the loop variable, bindings made before the loop, the elements of a vector;

  • call functions, which read and return and do nothing else (Functions Read, Procedures Write), and procedures that write only what the round made itself;

  • make values of their own — bindings inside the body, strings, records — which are gone when the round ends unless the round keeps them;

  • write a slot of a vector made before the loop with put, at an index of which the compiler can see that no two rounds compute the same one: the loop's counter, the counter plus or minus a value that stays the same, or a row of a table, y * width + x with x counted below width inside the round;

  • add to a sum, a product or a maximum that the loop accumulates (Sums, Products and the Largest).

The first loop of mandelbrot.scaly does the first, second and fourth of them, the second loop the fifth.

What Keeps a Loop in Order

Everything else keeps a loop sequential: its rounds run one after the other, in the order they are written, exactly as they would in a language that never runs anything in parallel. Three loops that each look harmless:

function cube(x: int) returns int
    x * x * x

var cubes Array[int]()
for i in 6
    cubes.add(cube(i))

var last 0
for i in 6
    last := cube(i)

var first 0
for i in 6
{
    if cube(i) > 50
    {
        first := i
        break
    }
}
print "`cubes.length` cubes, the last `last`, the first above 50: `first`"
$ scaly run order.scaly
6 cubes, the last 125, the first above 50: 4
$ scalyc --task-plan order.scaly
task-plan: 3 for-loops, 0 parallelizable
task-plan: order.scaly:5:1: blocked: transitively impure call add
task-plan: order.scaly:9:1: blocked: writes loop-external last
task-plan: order.scaly:13:1: blocked: writes loop-external first

The first loop appends to an array it did not make: add is a procedure that writes cubes, and in which order the rounds append decides the order of the elements. The second leaves in last what the last round wrote there — run side by side, whichever round finished last would win. The third stops at the first round that finds what it looks for, and which round is the first is again a question of order. Each verdict names the first reason the compiler found; a loop may have more than one.

The other reasons are of the same kind. A loop keeps its order when a round reads a global that can change (mutable or shared), writes one, reaches the world outside the program, writes a slot of a vector at an index two rounds could share (i / 2, an element of another vector), reads the vector it writes at any other slot, calls a routine the compiler cannot see into (a delegate, a C function it does not know), or leaves the loop early with break, return or a throw. A while or a repeat is never split at all; a loop over a range is a for.

A loop that keeps its order is not an error and gets no warning: it was written to run in order, and it does. When a loop should run on all cores, --task-plan names what stands in the way, and the fix is usually to give each round its own slot: the cubes into a Vector of six with put, as the counts of the rows above.

Sums, Products and the Largest

A loop that folds its rounds into one variable writes something it did not make, and still runs in parallel when the fold is one the compiler knows: v := v + e and the same with - and *, the bitwise |, & and xor on integers, and if e > v followed by v := e for a maximum (< for a minimum) of integers. Each part of the range folds its own rounds, and the parts are folded together at the end. The rectangles of perimeter 40, their areas summed and the largest one found:

function area(width: int) returns int
    width * (20 - width)

var sum 0
var largest 0
for w in 20
{
    let a area(w)
    sum := sum + a
    if a > largest
        largest := a
}
print "the areas add up to `sum`, the largest is `largest`"
$ scaly run areas.scaly
the areas add up to 1330, the largest is 100
$ scalyc --task-plan areas.scaly
task-plan: 1 for-loops, 1 parallelizable
task-plan: areas.scaly:6:1: parallel

The variable must be a local of the routine the loop is in, and the body may use it only in its update: a round that also reads the running sum — to store it somewhere, say — sees a value that depends on which rounds ran before it, and the loop stays in order (reduction variable used outside its update). In a maximum, the value compared and the value taken must be the same expression, written alike on both sides — a name such as a, an element v[i], a field, a call of a function; a round that compares one value and takes another computes no maximum, and its loop stays in order.

Floating-point addition is not associative: added in another order, the same numbers give a slightly different sum. A parallel sum of floating-point numbers that depended on how the range was split would print different digits on another machine, or on the same one with another load. Scaly's does not: each round's contribution is kept, and they are added up in the order of the rounds, so the sum has every bit of the one a sequential loop computes.

function term(k: int) returns double
{
    let t 4.0 / ((2 * k + 1) as double)
    if k % 2 = 0: t else 0.0 - t
}

let n 1000000
var pi: double 0.0
for k in n
    pi := pi + term(k)
print "`n` terms of Leibniz's series: pi is about `pi`"
$ scaly run leibniz.scaly
1000000 terms of Leibniz's series: pi is about 3.1415916535897743
$ SCALY_WORKERS=1 scaly run leibniz.scaly
1000000 terms of Leibniz's series: pi is about 3.1415916535897743

Values a Round Keeps

A round may build a value and keep it: put a string or a record it made into its slot of a vector that outlives the loop.

function caption(i: int) returns String
    "row `i`: `i * i`"

let n 5
var captions Vector[String](n as size_t)
for i in n
    captions.put(i as size_t, caption(i))
print "`captions[0]` ... `captions[4]`"
$ scaly run captions.scaly
row 0: 0 ... row 4: 16
$ scalyc --task-plan captions.scaly
task-plan: 1 for-loops, 1 parallelizable
task-plan: captions.scaly:6:1: parallel

Run in order, each caption would be built on the page of the code around the loop and live as long as it. Run in parallel, the rounds of one part of the range build on a page of their own; when the loop ends, those pages are handed to the region of the code around the loop, and the captions live exactly as long as they would have. Nothing is copied, and the parts never share an allocator (Memory That Is Not Shared). What a round keeps must be a value it built — a reference to something else is refused, and so is a body that takes an address with &, which could point into the round's own stack frame.

When the Cores Are Worth It

That a loop may run in parallel does not mean that it should. Waking other cores costs time, and a loop of a few dozen cheap rounds is done before they would be awake. Whether the cores are worth it depends on how many rounds there are and how much each one does, and the compiler knows neither in general. So it does not decide; the running program does.

A loop the compiler accepted starts in order, on the core that reaches it. Now and then — at checkpoints that lie twice as far apart each time, the first one placed by what the compiler estimated for the body — it reads the clock and works out what a round costs. As soon as the rounds still to run promise more work than splitting costs, about a tenth of a millisecond of it, they are cut into parts and handed to a pool of workers, one per core. A short loop ends before its first checkpoint and pays nothing for having been eligible. A loop that has run often remembers what its rounds cost, and the next time it decides at its start, without measuring again.

That is why the squares of the previous chapter and the cubes above print instantly either way, and why the rows of the Mandelbrot set run on every core. The pool has as many workers as the machine has cores, or as many as SCALY_WORKERS says; with one, every loop runs in order, and the program prints the same.