Column arrays: minimal struct-of-arrays storage

Deprecated language features: reusable and reusable[]. Use slot_pool<T> for slots and slice_pool<T> for contiguous runs. Builtin behavior and historical examples below remain relevant to existing code; removal is planned separately, after the remaining migration gaps.

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, but 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, and through 4K aliasing this makes a six-array version of the particles kernel 2x slower (measurements below). Nothing tells the compiler that the arrays are parallel either.

A complete struct-of-arrays feature was estimated at about 2,300 lines, 90% in codegen. That design lets ordinary functions accept element references and slices through proxies. It also chooses layouts per specialization and returns arrays into column destinations. Most of the code supports using an element or slice in functions written for ordinary arrays.

The proposed column array avoids that requirement. It is a separate array kind with no implicit conversions and no references, slices, or views into its elements. Its implementation needs storage handling and a few array members, at about a third of the full design's 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 column array is 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: through a T[||..]& parameter, or through an untyped parameter, 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:

• read as a value (let p = ps[i], ps[i].pos + d, f(ps[i]) into a by-value parameter, print(ps[i].vel)): a copy, loaded from the columns the path spans;
• written (ps[i] = p, ps[i].pos = v, ps[i].pos.y = 0.0), with compound assignment and ++/-- on a numeric leaf.

Nothing can refer to a path. The following are compile errors, and each error points at the copy-out and path forms:

• &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;
• for &p in ps.

A path checks its index once against the shared length, however many columns it touches, and the bounds-check pass elides that check as for any array.

Members.

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 the one case that can still involve a column array: an element path of the same array that is held earlier in the statement. So 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 into an ordinary array with xs.append(ps), and copy them 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:

• Roots and lifetimes (§9.2). A column array is only ever the root of a reference to the whole array, which no shrink invalidates. Its elements hold no references, are never a read-back candidate, and are never the target of a relative reference, so read-back roots, holders and the liveness scans at shrinks never involve them.
• Growth during construction (§4.2). A pushed element is fixed-size and holds no relative references, so it is evaluated before its slot is claimed, and append of a call result builds the result first. No column array is ever under construction while an expression runs.
• Bounds-check elimination (§10.5). A column array is a place with one length, changed by the same operations as a T[>..<]'s.

Representation

• The header lives in the owning frame, or in the program instance's globals: one typed pointer per column plus the count, { float *pos_x; ... int32_t *age; int64_t len; }. A T[||..]& is a plain pointer to it.
• Columns each take a data stack: a local takes N stack indices from its function's block (§10.3), and a global takes N reservations of its own. Column k's first element sits at its own page offset, k × 4096 / N past a page boundary, so parallel columns never share their low 12 address bits at the same index. This costs at most a page of address space per column.
• Stack tops are never used. A column is the only value on its stack for the array's whole life, and its elements are fixed-size, so its next slot is always base + len * size. Push stores N leaves and increments len; pop, resize and clear store len (resize also fills). The stack's top is read once, at the declaration, and never written. Column arrays therefore need none of the stack-top caching and synchronization of implementation.md §6.10, no watermark restores, and no stack identity in references: pushing through a T[||..]& needs only the header.
• Element paths are one new codegen location: the header, the checked index held in a temporary, and the range of columns the path spans. A field step narrows the range, and a path that reaches a leaf is an ordinary C lvalue (ps.pos_y[ix]), so compound assignment, ++, match on an enum leaf and indexing into a fixed-array leaf need nothing new. A path spanning several columns has two consumers: a load gathers the columns into a C value, and a store scatters a C value out into the columns. Elementwise math between paths of one array goes through GenElemwiseInto with column-mapped members, so ps[i].pos = ps[i].pos + ps[i].vel compiles to per-column loads and stores with no gathered temporaries, as the array-of-structs form does today.
• Loops. Column pointers never change while the array lives (growth never moves, and there is no whole assignment), so a loop reads each one into a local once. They are declared restrict where the loop reaches the array only through them. That holds when the loop contains no growth, shrink or call that can reach the array (the hoistrefs conditions, implementation.md §5.10), and no second column array that could be the same array.

Implementation

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

• Parser, AST, dump (~10 lines): [ || .. ] in the type postfix loop (|| already lexes as T_OROR), an A_COLS array kind, and how --dump prints it.
• Checker (~150–200):
  • ValidateType: the element is fixed-size and flat, and the type appears only as a variable's type or a reference's pointee. ClassOf makes it resizable. CanContain leaves it out, so it is never a read-back candidate.
  • CheckLValue: an element-path bit on LVal, set at the index step and kept through field and fixed-array index steps. CheckRefOf, AutoRef/BindsRef, .= declarations and rebinds, slices and for over a path reject it, with one diagnostic naming the copy-out and path forms.
  • Builtins: a BR_COLS receiver bit on len, push (no result), pop, resize, clear and append (its three source forms), plus a column-array source for append on ordinary arrays. Shrinks go to ShrinkGrowShrink with the variable scan off. for & is rejected and rendering is allowed.
  • Calls: no array-to-slice coercion for A_COLS, neither in overload tiers nor in BindTypes. Thread arguments, queues, thread-program globals and extern fn reject it.
  • BCE and the optimizer: their array-kind switches only.
• Codegen (~550–700):
  • codegen_types.h: the header typedef, and a per-element-type leaf table giving each column's C type, size and index, and each struct field's column range.
  • codegen_values.h: VarLoc/DerefLoc for the header, the IndexLoc branch returning an element path, FieldLocAt narrowing it, the gather in LoadLoc, a scatter helper, and column-mapped GenElemwiseInto.
  • codegen_nodes.h, codegen_stmts.h: the scatter in Assign::CgStmt; ForLoop::CgStmt's by-value binding with hoisted, restrict columns; BindLocal taking N stack indices and placing the columns.
  • codegen_builtins.h: the members. append has three sources: an array view, a call result built on a scratch stack, and another column array. It also covers an ordinary array appending a column array.
  • codegen_emit.h, codegen_render.h, codegen_frames.h: globals, printing, and the plain-pointer parameter.
• Tests (~350 lines):
  • a runtime fixture exercising every member and path form on a local, through a reference, on a global and inside a generic function, with // bce: annotations on its loops;
  • a check that pushes interleaved with calls through a reference keep the columns aligned;
  • test/errors_tc/ fixtures for each rejected use.
• Documentation: a row in the §3.3 table and a subsection after §5.3, the §12 member table, a tutorial paragraph, and an entry in implementation.md §6.1.

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%.

• The 2x at the default targets is 4K aliasing. Every array starts at offset 0 of a fresh stack, so px[i] and vx[i] share their low 12 address bits. For each load after a store, the CPU then predicts a store-to-load forward that is not there. Moving the starts apart removes the aliasing.
• Placed apart, the columns stay within 6–11% of the array of structs at the default targets. The loop touches every field on every iteration and branches, which is the array-of-structs layout's best case, and at clang's default target it does not vectorize: turning vectorization off changes nothing.
• With -march=native (AVX-512) the columns vectorize: 691 ms, against 1033 with vectorization off. The array of structs gets slower there (1375 ms, against 917 with vectorization off), so the fair margin is about 1.3x.
• The elementwise loop also needed restrict under MSVC. A six-column lowering of particles.goose's elementwise loop reads the global G inside the loop, and without restrict a C compiler must assume any float store may change it. That version took 3317 ms as is, 1623 staggered, 1295 with restrict and 1005 with both, against 1182 for the array of structs.

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 run into the same aliasing today.

Possible extensions, ordered by expected benefit

Open questions

1. Syntax. 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.