from 0.56× to 2.10×: debugging a struct-of-arrays enum bottleneck

marl github

iterating over enums in marl ran at half the speed of a plain Vec, even though the data layout was already faster. the cause was one pointer computation in the wrong place, and how llvm orders its passes around it.

enum/scale_circles at n = 100,000, measured against Vec<Shape>: 0.56× → 2.10×. above 1× means marl is faster.

apple m1 pro · rustc 1.98.1 · llvm 22.1.8 · criterion 0.8 · release profile

how marl stores an enum

marl is a rust implementation of zig's std.MultiArrayList: a growable struct-of-arrays list. each field of T gets its own column, and all columns share a single allocation. a loop that touches one field reads only that field's bytes.

#[derive(MultiArrayList)] generates everything needed to access the columns type-safely. enums are supported the way zig supports a union(enum): a list of enums is stored as two columns, tags with the active variant and data with the payload minus its tag. iterating yields matchable reference enums such as ShapeRefMut::Circle { r: &mut f32 }.

here is the enum used by benches/enum.rs. variants are scrambled so the branch predictor can't learn their order.

enum Shape {
    Circle { r: f32 },
    Rect { w: f32, h: f32 },
    Triangle([f32; 2], [f32; 2], [f32; 2]),
    Empty,
}

stored two ways, with capacity 4 (T is a tag, D is a payload):

Vec<Shape>                28 bytes per element, tag inline
[T|DDDDDD] [T|DDDDDD] [T|DDDDDD] [T|DDDDDD]

MultiArrayList<Shape>     one allocation, columns ordered by alignment
[DDDDDD][DDDDDD][DDDDDD][DDDDDD] [T][T][T][T]
^ ptr + cap × 0                  ^ ptr + cap × 24

each column starts at ptr + cap × PREFIX[i], where PREFIX is a per-type constant. keep an eye on that multiply.

one benchmark ran backwards

the criterion suite compares every operation against the same data in a Vec<Shape>. most enum results looked as expected: push and count_variant were comfortably faster, since counting a variant only has to scan the 1-byte tag column. one benchmark was not. enum/scale_circles mutates the payload of one variant in place, and the two loops are the same code apart from the type names.

// Vec<Shape>
for shape in a.iter_mut() {
    if let Shape::Circle { r } = shape {
        *r *= 1.0001;
    }
}

// MultiArrayList<Shape>
for shape in s.iter_mut() {
    if let ShapeRefMut::Circle { r } = shape {
        *r *= 1.0001;
    }
}

before the fix (speedup is Vec time divided by marl time):

benchmark	n = 1,000	n = 100,000	n = 1,000,000
`enum/push`	1.35×	1.36×	2.06×
`enum/count_variant`	1.74×	1.80×	3.03×
`enum/total_area` (iter)	0.99×	0.99×	1.01×
`enum/scale_circles`	0.52×	0.56×	0.60×

the struct-of-arrays layout makes the tag scan in scale_circles cheaper, yet marl took almost twice as long.

finding it

criterion reports how long a whole benchmark takes, not why. to see what the compiler was doing, the loops were copied into a small standalone crate, each in its own #[inline(never)] function, so they could be timed per element and disassembled one at a time.

1. separate the layout from the abstraction

alongside the two benchmark loops, a third variant skipped the iterator entirely and walked the raw tags and data columns by hand. if the layout itself were the problem, it would be slow too.

time per element, n = 1,000. sorting the input makes every branch predictable.

loop	scrambled variants	sorted by variant
`Vec<Shape>`	0.66 ns	0.36 ns
marl `iter_mut()`	1.16 ns	0.69 ns
marl raw columns	0.25 ns	0.19 ns

[METHOD NEEDED: how many runs behind each probe figure, and what the spread was. step 4 leans on a 1.17 vs 0.26 ns split, which is wide enough to survive almost any noise — but say so rather than making the reader assume it.]

the layout was fine: the raw columns ran 2.6× faster than Vec. the time went into the iterator path. and since that path stayed slow on sorted input, branch misprediction couldn't be the main cost.

2. read the machine code

the Vec loop compiles to what you would write by hand: load the tag, skip unless it's Circle, scale.

; Vec<Shape>, per element
ldur  w10, [x9, #-0x4]   ; load tag
cbnz  w10, next          ; not Circle: skip
ldr   s1, [x9]
fmul  s1, s1, s0
str   s1, [x9]
next:
add   x9, x9, #0x1c      ; +28 bytes

the marl loop compares the tag against every variant, and for Rect and Triangle it computes payload pointers and writes them to the stack. nothing ever reads those stack slots again.

; marl iter_mut(), per element
ldrb  w14, [x12], #0x1   ; load tag
cmp   w14, #0x1
b.gt  tri_or_empty
cbz   w14, circle
rect:
add   x14, sp, #0x10
add   x15, sp, #0x18
mov   w17, #0x4
mov   x16, x13
b     store
tri_or_empty:
cmp   w14, #0x2
b.ne  next
madd  x14, x9, x11, x10  ; idx * 24 + base
add   x16, x14, #0x8
add   x14, sp, #0x8
add   x15, sp, #0x10
mov   w17, #0x10
store:
add   x17, x13, x17
str   x16, [x15]         ; dead write to stack
str   x17, [x14]         ; dead write to stack
b     next

aarch64 disassembly, trimmed to the loop body. circle does the same load/multiply/store as the Vec version.

3. ask llvm why the writes survive

the generated get_mut matches on the tag and builds a ShapeRefMut; the caller's if let then matches on that. after inlining, llvm should fold the two matches into one tag test and delete the fields nobody reads. the ir showed why it didn't:

%.sink6.i.sroa.phi = phi ptr [ %_13.sroa.10, %bb3.i ], [ %_13.sroa.7, %bb5 ]
%.sink4.ph.i.sroa.phi = phi ptr [ %_13.sroa.12, %bb3.i ], [ %_13.sroa.10, %bb5 ]
%__marl_field_1.i = getelementptr inbounds nuw i8, ptr %data.i, i64 %.sink
store ptr %data.sink.i, ptr %.sink6.i.sroa.phi, align 8
store ptr %__marl_field_1.i, ptr %.sink4.ph.i.sroa.phi, align 8

each %_13.sroa.* is a stack slot holding one field of the ShapeRefMut.

the Rect and Triangle arms end in similar code, so simplifycfg merged their tails into one block, which is what the .sink names record. after the merge, the destination of each store is a phi that picks between stack slots. mem2reg and dead-store elimination only handle stores to a known slot. so these stay. because the slots are still written, the ShapeRefMut is never fully eliminated, and the four-way switch survives into the loop.

4. bisect the generated code

hand-written copies of the iterator narrowed it down. a replica that took ready-made column pointers and ran the identical match was as fast as the raw loop. plain list.get_mut(i) in an index loop, with no iterator at all, was as slow as iter_mut(). the common factor was Soa::get_mut itself, and the one real difference was where it computed the column pointers:

// columns computed per element: 1.17 ns
for i in 0..len {
    let tags = ptr.add(cap * PREFIX[0]);
    let data = ptr.add(cap * PREFIX[1]);
    if let Circle { r } = get_mut(tags.add(i), data.add(i)) {
        *r *= 1.0001;
    }
}

// columns computed once: 0.26 ns
let tags = ptr.add(cap * PREFIX[0]);
let data = ptr.add(cap * PREFIX[1]);
for i in 0..len {
    if let Circle { r } = get_mut(tags.add(i), data.add(i)) {
        *r *= 1.0001;
    }
}

same arithmetic, same get_mut, same match. only the position of two lines differs (shown inlined here; in the experiment they sat inside a separate #[inline] function).

time per element, n = 1,000, scrambled variants:

variant	column pointers	time
`Vec<Shape>`	baseline	0.66 ns
marl `iter_mut()`	per element	1.17 ns
marl `get_mut(i)` loop	per element	1.18 ns
replica, columns inside call	per element	1.17 ns
replica, columns hoisted	once, before the loop	0.26 ns
replica iterator	stored in the iterator	0.26 ns
raw columns	no reference enum	0.26 ns

two clusters, no middle ground. every variant that computes ptr + cap × PREFIX[i] inside the per-element call lands at about 1.17 ns; every variant that doesn't lands at about 0.26 ns.

the trigger: llvm does eventually hoist that multiply out of the loop, but only in a later pass. by then simplifycfg has already merged the match arms around it and left stores llvm can no longer delete. the multiply is hoisted one pass too late.

the fix: pass columns, not the raw buffer

don't make element access rely on the optimiser to hoist the column computation: do it at the source level. Soa gained a hidden associated type holding a pointer to the start of every column, and get/get_mut now take those pointers instead of the raw buffer.

 // src/soa.rs
 pub unsafe trait Soa: Sized {
     // ...
+    /// Pointers to the start of every column, e.g. `(*mut u32, *mut bool)`.
+    type Columns: Copy;
+
+    unsafe fn columns(raw: Raw) -> Self::Columns;
-    unsafe fn get_mut<'a>(raw: Raw, idx: usize) -> Self::RefMut<'a>;
+    unsafe fn get_mut<'a>(cols: Self::Columns, idx: usize) -> Self::RefMut<'a>;
 }

get changes the same way. for a struct, Columns is a tuple with one pointer per field; for an enum it is (*mut ShapeTag, *mut ShapeData).

the iterators compute the columns once, in new():

 // src/iter.rs
 pub struct IterMut<'a, T: Soa> {
-    raw: Raw,
+    cols: T::Columns,
     front: usize,
     back: usize,
     // ...
 }

 fn next(&mut self) -> Option<T::RefMut<'a>> {
     // ...
-    T::get_mut(self.raw, self.front)
+    T::get_mut(self.cols, self.front)
 }

sort_by and sort_unstable_by do the same before sorting. list.get(i) calls T::columns on each lookup, so single-element access behaves as before.

what the derive now generates for Shape (simplified). the match is unchanged; there is no longer any multiply inside it.

unsafe fn get_mut<'a>(cols: Self::Columns, idx: usize) -> ShapeRefMut<'a> {
    let (tags, data) = (cols.0.add(idx), cols.1.add(idx));
    match *tags {
        ShapeTag::Circle => { let (r,) = &mut *(*data).Circle; ShapeRefMut::Circle { r } }
        ShapeTag::Rect => { let (w, h) = &mut *(*data).Rect; ShapeRefMut::Rect { w, h } }
        ShapeTag::Triangle => { let (a, b, c) = &mut *(*data).Triangle; ShapeRefMut::Triangle(a, b, c) }
        ShapeTag::Empty => ShapeRefMut::Empty,
    }
}

why this works

the pointers now live in the iterator struct. once next() is inlined into the loop, they are plain local values fixed before the first iteration, so no later pass has to hoist anything. each match arm is then just an offset from data, and the arms no longer share a computation for simplifycfg to merge around.

that is the expected mechanism. what was measured: the replica built this way compiles with no stack writes in the loop, and it runs at the same speed as the raw column loop, which needs only one tag test per element.

the same inlining, with and without a multiply inside the match:

before: inline get_mut → rect/triangle tails merged around the unhoisted multiply → store target is a phi → writes kept, 4-way switch kept
after: inline get_mut → pointers already invariant → ShapeRefMut split and removed → one tag test

the fix doesn't rely on llvm's pass ordering happening to line up. it removes the computation that the ordering depended on, so it should hold for other enum shapes and future compiler versions, rather than being tuned to this benchmark.

results

the full criterion suite was rerun with the fix applied. the existing tests, clippy and cargo fmt --check all pass.

speedup over Vec (the two runs were hours apart):

benchmark	n	before	after
`enum/scale_circles`	1,000	0.52×	2.37×
	100,000	0.56×	2.10×
	1,000,000	0.60×	1.55×
`enum/count_variant`	1,000,000	3.03×	3.35×
`enum/push`	1,000,000	2.06×	2.13×
`enum/total_area` (iter)	1,000,000	1.01×	0.99×
`struct/iter_all_fields`	100,000	1.42×	1.45×
`struct/sort_by_key`	100,000	1.67×	1.79×
`struct/random_get`	1,000,000	0.92×	0.71×¹

from twice as slow to more than twice as fast. the gain is smallest at a million elements; that size wasn't analysed further. everything outside scale_circles is within run-to-run noise.

¹ random_get looked like a regression, so it was rerun back to back against a clean checkout, twice. at 1M, the version before the fix measured 351 and 355 µs and the fixed version 349 and 377 µs: no measurable difference.

loose ends

total_area is still at parity, and that's not a marl problem. that benchmark matches every element and reads its whole payload. the Vec loop and marl's loop compile to essentially the same code, and the stored element only shrinks from 28 to 25 bytes, so splitting tags from payloads has nothing to save. an early guess that the running floating-point sum set the speed limit didn't hold up: splitting the sum across four accumulators made the loop slower, not faster.

index access still computes columns per call. list.get(i) can't cache anything between calls, so a hot loop over get_mut(i) can still hit the slow pattern. iterators, sorting and the column slices avoid it. if index loops over enums become common, a public way to hold on to Columns would be the next step.

for derive-generated accessors generally: anything derived from the container rather than the element, such as base pointers, offsets or capacity-scaled products, belongs outside the per-element function. it will usually get hoisted anyway. usually is exactly the gap this bug fell into.

measured on an apple m1 pro with rustc 1.98.1 (llvm 22.1.8) and criterion 0.8, default release profile. per-element timings come from a standalone probe crate built from the same code; speedups come from scripts/bench.py. the change is commit 4057689, "optimise: use columns instead of raw".