The Scaly Programming Language

Chapter 5

Recursion That Forks

Two Calls at Once

A recursion that splits its problem in two and calls itself on each half has the same independence a loop has: the two calls read their arguments and nothing the other one writes. When the function is declared a function, the compiler knows it, and the two calls may run on two cores. The classic example does nothing but call and add:

function fib(n: int) returns int
{
    if n < 2
        return n
    fib(n - 1) + fib(n - 2)
}

print "fib(35) is `fib(35)`"
$ scaly run fib.scaly
fib(35) is 9227465
$ scalyc --task-plan fib.scaly
task-plan: 0 for-loops, 0 parallelizable
fork-plan: 1 fork pairs
fork-plan: fib.scaly:5:5: fib + fib
$ SCALY_WORKERS=1 scaly run fib.scaly
fib(35) is 9227465

Again there is no annotation. --task-plan, which reports the loops of a file, reports its recursion as well: below the loops, one line for each pair of calls that may run on two cores. Built with scaly build --release and asked for fib(42), the program took 0.83 seconds on one core and 0.14 seconds on the ten of the laptop of the previous chapter. That is six times as fast for a function that is the worst case for forking, because each call does almost nothing besides calling again.

What Forks

The compiler looks for two shapes in a function that calls itself: the two calls on both sides of one operator, as in fib, and two bindings in a row, each a call, the second one not using the first:

function count_multiples(lo: int, hi: int) returns int
{
    if hi - lo < 4096
    {
        var count 0
        var i lo
        while i < hi
        {
            if i % 7 = 0 or i % 11 = 0
                count := count + 1
            i := i + 1
        }
        return count
    }
    let mid (lo + hi) / 2
    let left count_multiples(lo, mid)
    let right count_multiples(mid, hi)
    left + right
}

let n 200000000
print "below `n`, `count_multiples(0, n)` numbers are multiples of 7 or 11"
$ scaly run multiples.scaly
below 200000000, 44155845 numbers are multiples of 7 or 11
$ scalyc --task-plan multiples.scaly
task-plan: 0 for-loops, 0 parallelizable
fork-plan: 1 fork pairs
fork-plan: multiples.scaly:16:5: let left count_multiples, let right count_multiples
$ SCALY_WORKERS=1 scaly run multiples.scaly
below 200000000, 44155845 numbers are multiples of 7 or 11

With scaly run on that laptop, one core took 0.33 seconds and all of them 0.09. The rules are narrow, and each of them has a reason:

  • The function is a function, so that the two calls cannot see each other.

  • It calls itself, twice, in one expression or in two let bindings that follow each other directly. Two different functions side by side do not fork, nor does a function that reaches itself through another one; of three calls, f(a) + f(b) + f(c), only the first two form a pair.

  • The operator between the calls is not and or or: their right side runs only when the left side does not decide, so running it early would run it where the program does not.

  • Its parameters are numbers or pointers, its result a number. A function that takes or returns a string or a record runs as written: the value a call on another core builds would have to be handed over, which loops do (Values a Round Keeps) and recursion does not yet.

  • It is a free function, not a method, and it cannot throw.

A function outside these rules runs as written, and nothing is wrong with it; --task-plan simply lists no pair for it:

function both(n: int) returns bool
{
    if n < 2
        return n = 1
    both(n - 1) and both(n - 2)
}

function three(n: int) returns int
{
    if n < 2
        return n
    three(n - 1) + three(n - 2) + three(n - 3)
}

function even(n: int) returns int
{
    if n < 2
        return n
    odd(n - 1) + odd(n - 2)
}

function odd(n: int) returns int
{
    if n < 2
        return n
    even(n - 1) + 1
}

function name(n: int) returns String
{
    if n < 1
        return String("x")
    let a name(n - 1)
    let b name(n - 2)
    a
}

print "`both(10)` `three(10)` `even(10)` `name(3)`"
$ scaly run others.scaly
false 68 31 x
$ scalyc --task-plan others.scaly
task-plan: 0 for-loops, 0 parallelizable
fork-plan: 1 fork pairs
fork-plan: others.scaly:12:5: three + three

both joins its calls with and, even and odd call each other, and name returns a string; of the three calls in three, the first two form a pair.

Forks Nobody Waits For

A recursion has many more pairs of calls than a machine has cores: fib(35) makes some thirty million calls. Handing each pair to the pool would cost far more than the additions it spares, and deciding at each pair whether it is worth it costs too much as well — the frames entered in the first microseconds would decide before any clock could tell. Scaly does neither.

At each pair near the top of the recursion, the running call notes its first call as one another core could take — a few writes into a list of its own thread, no lock —, runs the second call itself, and then takes the first back and runs it, unless someone took it meanwhile. While such a recursion runs, a clock beats every tenth of a millisecond. On a beat, if a worker of the pool has nothing to do, the oldest noted call of a thread is offered, and the idle worker takes it: the oldest is the one nearest the top of the recursion, the biggest piece of work still waiting. A call whose first half was taken does not wait idly for it; it helps the core that took it.

So a fork happens only where a core is free to take it, and the noting costs a few writes per call. Below the twelfth level the function runs as a plain copy without even those. What is left of the cost shows where the calls do no work of their own: when the engine was built, 200 000 separate runs of fib(15) took about three times as long as the plain function. A recursion whose calls compute something pays nothing measurable.

Three things keep a recursion on one core: a pool of one worker (SCALY_WORKERS=1), a call made inside a try — a fault on another core could not reach its handler —, and a build with -g, whose debugger expects one body per function. The last one the compiler knows when it compiles, so scalyc --task-plan -g lists no pair; the first two are decided when the program runs.

An Uneven Tree

A loop splits its range into parts of equal size; a recursion splits where the problem does, and the halves may differ by orders of magnitude. Adaptive integration is such a problem: it halves an interval until two estimates of the area agree, so it goes deep where the function bends and stops early where it is flat. Here the function has forty narrow peaks on a slow ramp:

; forty narrow peaks on a slow ramp
function g(x: double) returns double
{
    var y x * 0.1
    var k 0
    while k < 40
    {
        let d x - ((k as double) * 0.0731 + 0.05)
        y := y + 1.0 / (d * d + 0.00001 * ((k % 7 + 1) as double))
        k := k + 1
    }
    y
}

function simpson(a: double, b: double) returns double
    (b - a) / 6.0 * (g(a) + 4.0 * g((a + b) * 0.5) + g(b))

function area(a: double, b: double, whole: double, eps: double, depth: int) returns double
{
    let m (a + b) * 0.5
    let l simpson(a, m)
    let r simpson(m, b)
    let diff l + r - whole
    if depth = 0 or (diff < 15.0 * eps and diff > 0.0 - 15.0 * eps)
        return l + r + diff / 15.0
    area(a, m, l, eps * 0.5, depth - 1) + area(m, b, r, eps * 0.5, depth - 1)
}

let total area(0.0, 3.0, simpson(0.0, 3.0), 0.0000000001, 60)
print "the area under g from 0 to 3: `total`"
$ scaly run area.scaly
the area under g from 0 to 3: 23048.968067792208
$ scalyc --task-plan area.scaly
task-plan: 0 for-loops, 0 parallelizable
fork-plan: 1 fork pairs
fork-plan: area.scaly:26:5: area + area
$ SCALY_WORKERS=1 scaly run area.scaly
the area under g from 0 to 3: 23048.968067792208

Nobody has to tell the engine where the work is. A call that turns out to be big is still noted while it runs, so it is offered on the next beat a core is free, however deep the recursion below it goes. With scaly run, one core took 0.35 seconds and all of them 0.09.

The result has every digit of the sequential one. The two halves of an interval may be computed on two cores, but their sum is formed where it is written, left half plus right half, so the floating-point additions happen in the same order either way.