Goose

Column arrays: minimal struct-of-arrays storage

This proposal adds column arrays. A T[||..] would store a struct element as one array per leaf field, each on its own data stack, with one shared length. Elements could be copied out as ordinary structs or written through field paths. Sorting, slicing, serialization, and passing an element by reference would require copying the data into ordinary storage. The feature is not implemented.

import std;
import vec;

struct Particle { pos: float3, vel: float3, age: i32 }   // seven columns

fn spawn(ps: Particle[||..]&, n: i64) {
    for i in n {
        let x = i as f32;
        ps.push(Particle { pos: float3 { x, 1.0, 0.0 },
                           vel: float3 { 0.0, i % 4, 1.0 }, age: 0 });
    }
}

fn step(ps: Particle[||..]&, g: float3) {
    for i in ps.len {
        ps[i].vel = ps[i].vel + g;          // three columns in, three out
        ps[i].pos = ps[i].pos + ps[i].vel;
        ps[i].age++;                        // one column
    }
    var i = 0;
    while i < ps.len {
        if ps[i].pos.y < 0.0 {
            ps[i] = ps[ps.len - 1];         // swap-remove: whole elements
            ps.pop();
        } else {
            i++;
        }
    }
}

fn main() {
    var ps: Particle[||..] = [];
    spawn(ps, 1000);
    for s in 8 { step(ps, float3 { 0.0, -0.5, 0.0 }); }
    var highest = ps[0];                    // lifted: an ordinary Particle
    for p in ps { if p.pos.y > highest.pos.y { highest = p; } }
    print(ps.len, " ", highest);
    var sorted: Particle[>..] = [];
    sorted.append(ps);                      // the whole array lifted, to sort
    sort(sorted) { a, b => a.pos.y > b.pos.y };
}

With [||..] replaced by [>..<], this program compiles and runs today. A column array changes where the elements live and what else may be done with them, never what the program means.

Why a new array kind

Today this layout is written by hand, one array per leaf:

var px: f32[>..] = []; var py: f32[>..] = []; var pz: f32[>..] = [];
var vx: f32[>..] = []; var vy: f32[>..] = []; var vz: f32[>..] = [];
var age: i32[>..] = [];

This requires seven pushes per element and seven parameters per helper. The programmer must keep all seven lengths equal. A struct cannot group the arrays because it can hold at most one resizable field (§3.4). The layout also has a performance cost. Every one of those arrays starts at the same page offset of its own stack, which costs 2x on a six-array version of the particles kernel through 4K aliasing (measurements below), and nothing tells the compiler the arrays are parallel.

A complete struct-of-arrays feature, where element references and slices become proxies that ordinary functions accept, layouts are chosen per specialization, and arrays are returned into column destinations, was estimated at about 2,300 lines, 90% of it codegen, and most of that is the cost of letting an element or a slice escape into code written for ordinary arrays. A column array never lets anything escape: it is its own array kind, it coerces to nothing, and no reference, slice or view into it can exist. The remaining implementation consists of storage handling and a few array members, at about a third of the estimated size.

Rules

The type. T[||..] is resizable (§1.1) and both grows and shrinks, like T[>..<]: || for the columns, .. for the changing length.

Elements. T must be fixed-size and flat (§1.1: no references, slices or relative references at any depth). A field whose type is a struct is split into its fields, recursively. Any other field is one column: a scalar, a bool, a fixed array, a static-capacity limited array (a u8[..16] name), or a fixed-mode enum. pad fields have no column. A T that is not a struct is one column, so generic code may write T[||..] for any fixed, flat T.

Where it lives. A local or global var or let, initialized with [] or an array literal. It is never a struct field, an array element, an ADT payload, a by-value parameter, a return value, a thread argument, a queue value, or a global that a thread program uses. Functions take it by reference: a T[||..]& parameter, or an untyped one, which binds the array by reference (§4.1). A reference to the whole array is an ordinary reference under the ordinary rules.

Element access uses paths. ps[i] followed by any field steps and fixed-array index steps (ps[i], ps[i].pos, ps[i].pos.y) is an element path. A path can be:

Nothing can refer to a path. &ps[i], var r .= ps[i], passing a path where a reference is expected (fn f(p: Particle&)), slicing (ps[a..b], or a slice of a fixed-array leaf), for over a leaf array and for &p in ps are compile errors that point at the copy-out and path forms. A path checks its index once against the one length, however many columns it touches, and the bounds-check pass elides that check as for any array.

Members.

Member Meaning
.len -> i64 the element count
.push(v) appends one element; no result (its index is len - 1)
.pop() -> T removes the last element and returns it by value
.resize(n, v), .resize(n), .clear() as on T[>..<]
.append(src) appends every element of src: any array or slice of T (a call's array result included), or another `T[

An ordinary growable array of T also accepts a column array in its own append (sorted.append(ps) above): that is the whole-array lift. for p in ps and for p, i in ps iterate by value (§6.5), re-reading the length as for any array. print, str and format render a column array as they render T[>..<].

Shrinking. pop, resize and clear are legal wherever a grow-shrink array's are: on a local, through a reference, on a global (§5.2). The §5.2 test is kept for what can still involve a column array, an element path of the same array held earlier in the statement: ps[i] = ps.pop() is rejected exactly as it is for T[>..<] today, and so is a call that shrinks ps in the same position. The scan of reference and slice variables is skipped, since none can point into a column array.

Not in v1. ==, copy(ps), whole assignment, index_of, slices and views, to_bytes, bytes_of and from_bytes, reusable, in pool references to its elements, and every function that takes T[:] (sort, find, filter and the other slice functions of std) are compile errors. To use these operations, copy the elements out: xs.append(ps) into an ordinary array, and back with ps.clear(); ps.append(xs) where needed.

What the checker does not need

Most of the checker's machinery is about references, and nothing refers into a column array:

Representation

Implementation

Estimates are rough (±30%). They come from the inventory of the full design, with everything a column array does not have taken out.

That is roughly 750–900 lines of compiler: about the size of to_bytes and from_bytes (+779 in src/), and a third of the full design.

Measurements

The hand-written six-array version of bench/goose/particles_scalar.goose is the layout Goose offers today, and it is compared with the array-of-structs original. N = 4,000,000, best of five, on a Ryzen 9 9950X3D. Checksums were identical, and repeated sessions varied by up to 8%.

ms MSVC 19.51 /O2 clang 20 -O2 clang 20 -O2 -march=native
array of structs (particles_scalar.goose) 1039 956 1375
six f32[>..] arrays, as generated today 2015 1968 674
the same C, column starts 688 bytes apart 1101 1063 691

The stagger belongs in any column layout the compiler controls. Whether ordinary data stacks should start at staggered offsets too is a separate question, since unrelated arrays that one loop reads and writes meet the same aliasing today.

Possible extensions, ordered by expected benefit

Extension What it adds Rough cost
for &p in ps as a place alias p stands for ps[i] in paths and still has no address; kernels then read like their array-of-structs versions ~100 lines
Column views a real slice over one column (ps.pos.x as an f32[:], in some spelling), for FFI and std kernels, held by variables only as §5.2's slices are, which brings back the variable scan at shrinks ~150
==, copy, whole assignment per-column compares and copies ~60
Reference and in pool leaves elements that hold links, checked as element fields of any array are probably small
Struct tails a frame object (C.2) whose tail is a column header ~200
Threads, queues, to_bytes images in array-of-structs order, since images carry no layout ~100
Returns and by-value parameters N destination stacks and named results placed in columns (§7.3); most of the full design's cost several hundred

Open questions

  1. Spelling. T[||..] reads as columns with a changing length. T[>..||] would keep the family's > for stack growth.
  2. push's result. Should push return the new index, the counterpart of the reference other arrays return?
  3. Split depth. Split struct fields only, or fixed arrays too (a f32[4] leaf as four columns)?
  4. append(f()). It builds the result on a scratch stack and then splits it into the columns. Is that acceptable against §4.3? Static-capacity limited arrays already take a call's array result that way (implementation.md §6.5). The alternative is for append to take stored sources only.
  5. The place alias. Should for &p in ps be in v1? It is what makes a kernel read like its array-of-structs version.