184. AoSoA and hot/cold in Rust

Four is fine, six is not

Put an annotation above a collection of {x, y, vx} records:

// @viscosity aosoa(4)
const ps = [];
for (let i = 0; i < 100; i++)
  ps.push({ x: i, y: 2 * i, vx: 1 });
for (let i = 0; i < ps.length; i++)
  ps[i].x += ps[i].vx;

viscosity explain (release build, rustc 1.97) answers ps (line 2) {x, y, vx} → AoSoA, blocks of 4. Change the 4 to a 6, and it refuses (wrapped):

ps (line 2) {x, y, vx} → kept as array
  of objects
  · annotated aosoa(6), but the block
    size must be a power of two (2, 4, 8,
    16, ...)

The same happens for 0, 1 and 3. Chapter 107 built this layout in TypeScript and measured that V8 rarely rewards it. This chapter reads the Rust that writes it, finds out why 6 is refused, and ends with the other split from Part VII, hot and cold, which the port does in a simpler way than its name suggests.

The slot of a field

With F fields and blocks of B elements, one Float64Array named data holds everything. Block i / B starts at (i / B) * F * B. Inside it, field k has its own run of B slots starting at k * B, and element i sits at lane i % B of that run. When B is 2 to the power sh, i / B is i >> sh and i % B is i & (B - 1):

For the program above the emitter writes (wrapped):

push(v0, v1, v2) {
  const n = this.length;
  if (n === this.cap) this.grow();
  const b = (n >> 2) * 12 + (n & 3);
  this.data[b + 0] = v0;
  this.data[b + 4] = v1;
  this.data[b + 8] = v2;
  return (this.length = n + 1);
}

and rewrites the loop body ps[i].x += ps[i].vx to (wrapped):

ps.data[((i) >> 2) * 12 + 0 + ((i) & 3)]
  += ps.data[((i) >> 2) * 12 + 8
    + ((i) & 3)];

The constructor rounds the capacity up to whole blocks (Math.ceil(cap / 4) * 4), and grow() copies the old array into the front of a bigger one. Slots depend on i and k, never on the capacity, so growing moves nothing.

fn main() {
    // fields x, y, vx; blocks of 4
    let names = ["x", "y", "vx"];
    let (f, b, sh) = (3, 4, 2);
    let n = 10; // elements pushed
    let cap = 12; // whole blocks
    let dash = String::from("-");
    let mut data = vec![dash; cap * f];
    for i in 0..n {
        for k in 0..f {
            let blk = (i >> sh) * f * b;
            let lane = i & (b - 1);
            let s = blk + k * b + lane;
            let nm = names[k];
            let v = format!("{nm}{i}");
            data[s] = v;
        }
    }
    for row in data.chunks(f * b) {
        println!("{}", row.join(" "));
    }
}

The arithmetic in Rust

emit.rs builds that text in a closure, slot, which every rewritten access calls (adapted):

let sh = log2_exact(b)
    .expect("checked by container_class");
let bf = b as f64;
let stride = js_number(nf * bf);
let off = js_number(k as f64 * bf);
let mask = js_number(bf - 1.0);
let at = if simple_idx {
    format!("(({idx}) >> {sh}) * \
        {stride} + {off} + \
        (({idx}) & {mask})")
} else {
    need_aosoa = true;
    format!("__vsc_aosoa({idx}, {sh}, \
        {stride}, {off}, {mask})")
};
format!("{arr}.data[{at}]")

A simple index (an identifier or a literal, already proven or assumed in bounds) is repeated twice in place. Anything else, such as a call to __vsc_bc, must run once, so it goes through the helper __vsc_aosoa(i, sh, stride, off, mask) instead, as in ps.data[__vsc_aosoa(__vsc_bc(ps, 10, 'y', false), 2, 12, 4, 3)]. The constants are computed as f64 and printed by js_number, so the text matches what the TypeScript reference computes with its doubles.

And log2_exact is one line:

fn log2_exact(b: u64) -> Option<u32> {
    b.is_power_of_two()
        .then(|| b.trailing_zeros())
}

is_power_of_two checks that exactly one bit is set, and trailing_zeros counts the zeros below it, which is the shift^[1].

Who refuses six?

Three places know the rule. The planner refuses first, with the message above: !(b >= 2 && b.is_power_of_two()) (chapter 182). 1 is a power of two, 2⁰, so it needs the extra b >= 2. container_class checks again and returns a CompileError, and slot then relies on it with expect. Because the planner went first, neither of those can fire for a program the CLI compiles. They are there so a mistake in one place shows up as an error, not as wrong arithmetic.

When this chapter was first written, there was no rule at the other end. Both engines accepted aosoa(1073741824), which is 2³⁰. The constructor then asked for new Float64Array(2³¹ * 2), and node reported RangeError: Array buffer allocation failed for a program whose original runs fine. From 2³² up, the arithmetic would be wrong as well, because JavaScript takes shift counts modulo 32^[2]: i >> 32 is i. At 2⁶⁴ the engines even disagreed: the port stored block sizes as u64, which saturates, and refused the result, while the reference accepted it. A real limit closes all three, and both engines now have one, 2¹⁶ (MAX_BLOCK_SIZE in Rust), checked before the power-of-two rule:

  · annotated aosoa(1073741824), but the
    block size must be at most 65536

A size that isn’t a whole number, such as aosoa(x), is refused too, quoted as written, instead of quietly becoming the default 8.

Hot and cold, by type

Chapter 108 described splitting a record into hot fields, used by the busy loops, and cold ones. The port has a split too. It is by type, not by heat. describe in plan.rs partitions the fields:

let (typed, generic): (Vec<&str>, Vec<_>) =
    c.fields.iter().map(String::as_str)
        .partition(|f| {
            c.numeric_fields.contains(*f)
        });

and container_class gives the first group Float64Array columns and the second plain arrays. In mixed_columns.js explain says (wrapped):

  · typed Float64Array columns for hp, x;
    plain array columns for id, tag (may
    hold non-numbers)

tag is read in the hottest loop and still gets a plain column, and a numeric field that no loop reads still gets a typed one. AoSoA has no plain part at all: its one data array is a Float64Array, so an annotation on records with a string field is refused: annotated aosoa, but fields name may hold non-numbers.

What would a real split by heat need? The access tables of chapter 181 already list, per loop, which fields are touched together. Nothing in plan.rs reads them for grouping today. Since every field already has its own column, grouping only matters where fields share storage: in AoSoA’s blocks.

Your turn

// Where field k of element i lives in
// AoSoA data with f fields, blocks of
// b. None if the planner refuses b.
fn slot(
    i: usize,
    k: usize,
    f: usize,
    b: usize,
) -> Option<usize> {
    todo!()
}

What you learned

• AoSoA puts field k of element i at (i >> sh) * F·B + k·B + (i & (B − 1)), in one Float64Array.
• A power of two turns division and remainder into a shift and a mask. log2_exact is is_power_of_two then trailing_zeros.
• The planner refuses other sizes, 1, and huge powers of two (above 65536), which once failed at run time.
• Viscosity’s “hot/cold” split is by type: typed columns for proven numbers, plain columns for the rest.