Compiler

Columnar storage of struct arrays

How native builds lay out an array of simple structs column by column, when that applies, and how to turn it off.

since 0.1.0-alpha.1linux

Description

An Array<T> whose element type T is a simple value struct is stored by column on the native backends instead of by row. A row layout keeps each struct's fields together, one struct after another. The columnar layout keeps all the first fields together, then all the second fields, and so on, in a single allocation. It is the default and needs no change to your program: there is no new syntax, annotation or type, and the array has exactly the same methods and behaviour as before. The layout cannot be observed from the language, so a program prints the same output with it on or off, and on every engine.

An array of structs, read one field at a time

struct Sample {
    int hot;
    int cold;
    float weight;
}

Array<Sample> samples = [];
for (int i in 0..4) {
    samples = samples.add(Sample(i, i * 10, i.toFloat() / 2.0));
}

int total = 0;
for (int i in 0..4) {
    total = total + samples[i].hot;
}
console.writeln("hot total = ${total}");
console.writeln("cold of #3 = ${samples[3].cold}");
console.writeln("weight of #3 = ${samples[3].weight}");

Run it ▶

hot total = 10
cold of #3 = 30
weight of #3 = 1.500000

Which structs qualify

T must be a value struct with at least one field, and every field must be a plain number-like scalar: int, float, bool, char, or one of the sized numeric types (byte, int8, int16, int32, uint, float8, float16, float32). A struct with a weak field, an optional field, a union field, a field that is itself a struct, or a reference field such as a string keeps the ordinary row layout permanently. This is decided from the declaration, before the program runs.

When it is faster, and when it is not

Reading one field across many elements, as in samples[i].hot in a loop, touches only that field's column, so it reads far less memory. The array also takes less memory overall. The advantage grows with the number of fields in the struct.

Consuming whole structs is the opposite case. for (Sample s in samples) and closure pipelines such as map, where and reduce need a complete struct for every element, so the program assembles one from the columns each time, and those loops can be slower than they would be with the row layout. For a hot loop over a wide struct, prefer reading the fields you need through an index.

Behaviour that does not change: writing arr[i] = v still copies the array on write (in place when nobody else holds it, otherwise a copy), structs used as map keys still compare field by field, and Array(n, fill) still builds the array in one pass.

Turning it off

leviathan --no-columnar --build-native app app.lev

--no-columnar stores every struct array row by row. It exists to compare the two layouts or to rule the layout out while hunting a problem; the program's output is identical either way.

Rules

Columnar storage applies to Array<T> where T is a value struct with at least one field and only scalar fields (numbers, bool and char).
A struct with any string, optional, union, struct or reference field, or any weak field, is stored by row.
The layout is not observable: output is the same with and without --no-columnar, and on every engine.
It is a property of the native backends. The interpreters never use it.
--no-columnar applies to the whole program.

Examples

A struct that does not qualify, because one of its fields is a string. It behaves exactly as the qualifying one does and is simply stored by row:

A struct with a string field stays row-major

struct Entry {
    string name;
    int score;
}

Array<Entry> entries = [];
entries = entries.add(Entry("ada", 90));
entries = entries.add(Entry("grace", 95));

int best = 0;
for (int i in 0..1) {
    if (entries[i].score > best) {
        best = entries[i].score;
    }
}
console.writeln("best score = ${best}");

Run it ▶

best score = 95

Checking that the layout does not change the result:

leviathan --build-native with_columns samples.lev
leviathan --no-columnar --build-native with_rows samples.lev
./with_columns > a.txt
./with_rows > b.txt
cmp a.txt b.txt

Notes

On the LLVM backend each column is stored at the true width of its field type: one byte for byte, int8 and float8, two for int16 and float16, four for int32, uint and float32, and eight for int, float, bool and char. This only affects memory use. Values read back are always the canonical values of the language.