Performance

Goose is meant to be fast in the way C is fast: values sit in contiguous memory, there is no garbage collector, and allocating is moving a pointer. Most of a Goose program's speed comes from that model without any effort. This chapter is about the remaining part: the checks that safety adds, how to see which of them are left, how to remove the rest, and how data layout affects speed more than any of them.

#Measure a real build23.1

goose file.goose compiles in process with a small, fast C compiler, which is the right tool for trying things out and the wrong one for timing them. For timing, build with the system's C compiler:

$ goose build flock.goose -o flock
$ ./flock

For the loops measured in this chapter, the in-process run was between three and eight times slower than goose build. A --debug build adds overflow and conversion checks to every operation, and was two to four times as slow as a normal build.

The os module's clock() returns seconds of processor time as an f64. When timing, make sure each repetition does work that the C compiler cannot skip or move. A loop that recomputes the same sum twenty times may compile to a loop that computes it once, before the first clock().

#Bounds checks23.2

Every index into an array or a slice is checked, and a failed check aborts the program. The compiler removes each check that it can prove can never fail. That analysis runs on every build, and you can ask it what it did. --bce-lines reports, for each line, how many checks were elided and how many were kept:

fn dot(a: f32[:], b: f32[:]) -> f32 {
    var t: f32 = 0.0;
    for i in a.len { t += a[i] * b[i]; }
    return t;
}

fn fill(n: i64) -> f32[>..] {
    var v: f32[>..] = [];
    for i in n { v.push(i); }
    return v;
}

fn main() {
    let a = fill(4);
    let b = fill(4);
    print(dot(a, b));
}

bce-line: main.goose:3: 1 elided, 1 kept

The check on a[i] went, because i counts up to a.len. The check on b[i] stayed, because nothing says that b is as long as a. The cheapest fix is to say so, once, before the loop:

fn dot(a: f32[:], b: f32[:]) -> f32 {
    assert(a.len == b.len);
    var t: f32 = 0.0;
    for i in a.len { t += a[i] * b[i]; }
    return t;
}

bce-line: main.goose:4: 2 elided, 0 kept

The assert is one comparison per call instead of one per element, and it documents the function's real precondition, which the original version left for a reader to discover. This is the most useful idiom in the chapter: state the lengths a kernel relies on at its top.

The summary the compiler prints on stderr after every compile gives the totals for the whole program instead, along with what the optimizer did:

$ goose check dot.goose -O2
parsed ok: 3 top-level declarations, 1 file(s)
typechecked ok: 3 specialization(s), 0 struct/0 enum instance(s); optimized -O2: 3 inlined, 0 base case(s), 0 folded, 2 propagated, 0 tail loop(s), 0 reassociated
bce: elided 2/2 index and 0/0 slice checks

#What the analysis knows23.2.1

The analysis knows the ordinary facts a loop and its conditions establish: a for i in a.len loop, an if i < a.len, an assert, a check already passed. The language adds some facts that C cannot offer:

• A grow-only array shrinks only at a pop, resize or clear that the analysis can see, so a length checked before a push still holds after it.
• Integer % is Euclidean, so x % a.len is a valid index for every x.
• A fixed array's length and a limited array's capacity are constants.
• The whole program is compiled at once, so facts cross calls. When every caller of a function passes two arrays of the same length, the function can use that, even without an assert.

The % rule makes wrapping around an array free of checks:

fn smooth(samples: f32[:], width: i64) -> f32[>..] {
    var out: f32[>..] = [];
    for i in samples.len {
        var t: f32 = 0.0;
        for k in width { t += samples[(i + k) % samples.len]; }
        out.push(t / width);
    }
    return out;
}

fn main() {
    let s: f32[6] = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0];
    print(smooth(s, 3));
}

bce-line: main.goose:5: 1 elided, 0 kept

[2.0, 3.0, 4.0, 5.0, 4.0, 3.0]

#How much a check costs23.2.2

Less than you might expect. A kept check is a comparison and a branch that is never taken, which a modern processor predicts perfectly. In the tests for this chapter, a random-access loop ran at the same speed with and without its checks, because its time went on cache misses. Where a check does cost something is in a tight loop over arrays, where the C compiler would otherwise turn the loop into vector instructions. A branch that might leave the loop part-way through can prevent that. So look at the --bce-lines report for your hot loops, and do not worry about the rest.

#Index types23.3

There is one kind of check that no analysis of the code can remove: an index that was read out of another array, as in weights[ids[k]]. Whether it is in range depends on the contents of ids, and the compiler reasons about lengths, not about every element of an array.

An index type moves that check to where the index is made. The type u32 in weights is a u32 that is always below weights.len. Converting a plain integer with as checks it once, and from then on indexing weights with it needs no check, since the array it names is a grow-only global and can never get shorter:

var weights: i32[>..] = [];
type Id = u32 in weights;

fn gather(ids: Id[:]) -> i64 {
    var t = 0;
    for id in ids { t += weights[id]; }
    return t;
}

fn main() {
    for w in [45, 52, 38, 41, 60] { weights.push(w as i32); }
    var ids: Id[>..] = [];
    for i in [4, 0, 2] { ids.push(i as Id); }
    print(gather(ids));
}

bce-line: main.goose:6: 1 elided, 0 kept
bce-line: main.goose:13: 0 elided, 1 kept

143

The check on line 6 is gone. The one kept on line 13 is the conversion i as Id. That conversion is where a bad index is caught:

fn main() {
    for w in [45, 52, 38] { weights.push(w as i32); }
    var ids: Id[>..] = [];
    for i in [2, 7] { ids.push(i as Id); }
}

goose runtime error: index 7 out of bounds (length 3)

The array named by an index type must be a global grow-only array, and it can then never be shrunk anywhere in the program. The type names the array, so u32 in weights and u32 in names cannot be mixed up. Index types fit graphs, meshes and other data where one table refers to rows of another. A field of a struct can be one, and an image loaded with from_bytes has every such field checked against its array.

There is also a bound type, u32 upto weights, which may equal the length. It is the type for the end of a range, such as a node's lo..hi range of edges.

#checkfree: no checks allowed23.4

Writing checkfree before fn turns "no checks left here" from a hope into a requirement. The function compiles only if no bounds check remains anywhere in it, and the error says which check stayed and why:

checkfree fn gather(xs: i32[:], ids: i64[:]) -> i64 {
    var t = 0;
    for k in ids.len { t += xs[ids[k]]; }
    return t;
}

fn main() {
    let xs: i32[5] = [1, 2, 3, 4, 5];
    let ids: i64[3] = [4, 0, 2];
    print(gather(xs, ids));
}

main.goose:3: error: checkfree fn gather keeps a bounds check: ids[k] is read out of an element, a field or a call result, whose value the analysis does not know; an index type (`u32 in a`) for what is stored there carries it (§3.11)

The gather that takes Ids above compiles as a checkfree fn. Facts from callers do not count here: even if every call passes arrays of equal length, a checkfree function must establish what it relies on itself, usually with an assert, so it stays check-free whoever calls it. A checkfree function can call only other checkfree functions, builtins and C functions, since a check in a callee would run inside it. It may still assert, and its asserts are how it states its preconditions.

checkfree does not change what the code computes or how it is compiled. It is a test that runs at compile time, and it protects a hot loop from a later edit that quietly brings a check back.

#Asking for inlining and vector code23.5

Two more qualifiers are hints to the code generator:

• inline fn asks for the function to be inlined at every call, however large it is. Without it, the compiler decides from size and the number of calls.
• simd fn asks for the function to be compiled several times, once for the baseline instruction set and once for each wider one (AVX2 and AVX-512 on x86-64), and for each call to run the widest version that the processor supports. It suits a function containing a long loop over bytes or numbers. It needs clang; other compilers and the in-process run ignore it.

simd fn brighten(px: u8[:], by: u8) {
    for i in px.len {
        px[i] = if px[i] > 255 - by { 255 } else { px[i] + by };
    }
}

inline fn clamp(x: i64, lo: i64, hi: i64) -> i64 {
    if x < lo { lo } else if x > hi { hi } else { x }
}

fn main() {
    var img: u8[8] = [0, 40, 100, 200, 250, 255, 7, 128];
    brighten(img, 30);
    var out: u8[>..] = [];
    for p in img { format(out, p, " "); }
    print(out, clamp(300, 0, 255));
}

30 70 130 230 255 255 37 158 255

Neither qualifier changes a program's results. A simd function computes exactly what its baseline version does, including the rounding of every floating-point operation. -O0, -O1 and -O2 set how much the Goose compiler inlines on its own; the default is -O2.

#Data layout23.6

The largest speedups usually come from arranging data so that a loop reads only what it needs. A loop that sums one field of an array of structs reads the whole struct into the cache, field by field, to use four bytes of it:

Here are both layouts. The code is the interesting part; the timings depend on the machine, so they are described below rather than printed:

import os;

struct Goose {
    x: f32, y: f32, vx: f32, vy: f32,
    weight: f32, age: i32, id: i64,
}

fn total_weight(flock: Goose[:]) -> f64 {
    var t: f64 = 0.0;
    for g in flock { t += g.weight; }
    return t;
}

fn total(weights: f32[:]) -> f64 {
    var t: f64 = 0.0;
    for w in weights { t += w; }
    return t;
}

fn main() {
    let n = 4000000;
    var flock: Goose[>..] = [];
    var weights: f32[>..] = [];
    for i in n {
        let w: f32 = 3.0 + i % 5;
        flock.push(Goose { x: 0.0, y: 0.0, vx: 0.0, vy: 0.0,
                           weight: w, age: 1, id: i });
        weights.push(w);
    }
    var a: f64 = 0.0;
    var b: f64 = 0.0;
    let t0 = clock();
    for r in 20 {
        flock[r].weight += 1.0;            // so no round repeats
        a += total_weight(flock);
    }
    let t1 = clock();
    for r in 20 {
        weights[r] += 1.0;
        b += total(weights);
    }
    let t2 = clock();
    print(a == b, " structs ", t1 - t0, "s, array ", t2 - t1, "s");
}

Built with goose build on the machine this book was tested on, the loop over the separate array of weights was between four and five times faster than the loop over the structs. Neither loop has a bounds check left. The difference is memory traffic alone.

Splitting a struct into parallel arrays, one per field, is called a structure of arrays. It is worth doing for the fields that hot loops read, and not otherwise, since code that works on one whole goose at a time reads better with a Goose. Goose has no special syntax for it, but grow-only global arrays and index types make it straightforward: the same u32 in xs index can serve every parallel array, after an assert that the others are as long.

A few more layout points follow from earlier chapters:

• Fixed-size elements can be indexed. Arrays of variable-size elements (u8[][>..], structs with inline strings, variable-mode enums) are compact but sequential, so they suit data that is read in order.
• varint fields and links narrower than 64 bits (T&<u32>, T&<u16>) make data smaller, and smaller data is often faster even with the decoding.
• Goose structs are packed. If a hot field is misaligned, reorder the fields from largest to smallest, or add a pad.

#Design note: safe by default, fast on request23.7

C makes the fast thing the default and leaves safety to the programmer. Goose does the reverse, but tries to make the cost of safety visible and removable. Every check is in the program unless the compiler proves it away, the compiler says which checks remain, and checkfree lets you insist that there are none. The language makes the proofs easier by design: grow-only arrays never surprise the analysis by shrinking, % never goes negative, and whole-program compilation means facts reach across calls. What it does not offer is a way to switch checks off for one function. Proving them unnecessary is always possible, and an assert is usually enough.

#Exercises23.8

1. Write fn add(a: f32[:], b: f32[:], out: f32[:]) that adds two arrays into a third. Run it with --bce-lines, then add an assert so that no checks are kept.

2. Make fn add from exercise 1 a checkfree fn. What happens if you remove the assert?

3. A graph stores its nodes in a global Node[>..] and its edges as a global array of target nodes. Give the edges an index type, and write a checkfree function that sums the weights of a node's neighbours.