Rust reflection and a multi-array list

Rust reflection and a multi-array list

Mar 25, 2026 · 7 minute read

· rust

Rust is experimenting with compile-time reflection in the form of type_info (Tracking issue #146922).<br>It's far from finished, but the other day more than a month ago1 the pull request for Support ADT types in type info reflection landed.<br>With that PR the types expose enough information about structs to be useful to play around with.

This is what the type info looks like for some types:

u32<br>Type {<br>kind: Int(<br>Int {<br>bits: 32,<br>signed: false,<br>},<br>),<br>size: Some(<br>4,<br>),

bool<br>Type {<br>kind: Bool(<br>Bool,<br>),<br>size: Some(<br>1,<br>),

struct Foo {<br>a: u32,<br>Type {<br>kind: Struct(<br>Struct {<br>generics: [],<br>fields: [<br>Field {<br>name: "a",<br>ty: TypeId(0x1378bb1c0a0202683eb65e7c11f2e4d7),<br>offset: 0,<br>},<br>],<br>non_exhaustive: false,<br>},<br>),<br>size: Some(<br>4,<br>),

This code snippet shows the structure of several more types.

The full type information is available at compile-time, so in const fn and const { } blocks.<br>The const functions need to be called in a const context though.<br>TypeId::info panics if called at runtime.

Whereas currently anything that wants to act on the shape of types usually works as a proc-macro,<br>the new reflection allows const code to do it without external crates nor external types to cooperate, e.g. by also annotating types using the proc-macro.

Building a multi-array list

Inspired by Zig's MultiArrayList I set out to implement a similar type in Rust.

To understand what a multi-array list even is I'll cite the Zig documentation:

A MultiArrayList stores a list of a struct or tagged union type.<br>Instead of storing a single list of items, MultiArrayList stores separate lists for each field of the struct or lists of tags and bare unions.<br>This allows for memory savings if the struct or union has padding,<br>and also improves cache usage if only some fields or just tags are needed for a computation.

To translate that into Rust code, imagine we have a struct like this:

struct Point {<br>x: i32,<br>y: i32,

And we create a list of points:

let mut list = Vec::new();<br>list.push(Point { x: 47, y: 23 });<br>list.push(Point { x: 0, y: 5 });

In memory this will be laid out roughly like:

┌─ list ───────────────────────┐<br>│ 2 │ 4 │ 0x5c2c3ef8cae0 │<br>└───────────────│──────────────┘<br>└─┌─ 0x5c2c3ef8cae0 ──────────┐<br>│ 47 │ 23 │ 0 │ 5 │<br>└───────────────────────────┘

The vector holds the length (2), the capacity (42) and a pointer to the actual data allocated on the heap.<br>On the heap all values are laid out flat one after the other.<br>To Rust it's known that the Point struct consists of 2 integers, of which it knows the size (32 bit = 4 bytes), and thus a Point is 8 bytes.<br>Thus we can expect a new Point every 8 bytes3.

For a multi-array list we turn it into this construct instead:

┌─ list ────────────────────────┐<br>│ 0x6000028bc010 │ 2 │ 2 │<br>└──│────────────────────────────┘<br>└─┌─ 0x6000028bc010 ────────────────┐<br>│ 0x6000028bc020 │ 0x6000028bc030 │<br>└──│───────────────│──────────────┘<br>│ └───────┐<br>└─┌─ 0x6000028bc020 ─┐ └─┌─ 0x6000028bc030 ─┐<br>│ 47 │ 0 │ │ 23 │ 5 │<br>└──────────────────┘ └──────────────────┘

Our list has a pointer to a list of pointers (0x6000028bc010), a length (2) and a capacity (also 24).<br>The pointers in that list of pointers point to more lists.<br>Each of these lists contain the values of just one of the fields of Point.<br>Or in Rust code5:

struct MultiArrayList {<br>elems: *mut *mut u8,<br>cap: usize,<br>len: usize,

This ends up being usable in Rust thanks to reflection6:

let mut points = MultiArrayList::::new();

let point = Point { x: 47, y: 23 };<br>points.push(point);

let point: Box = points.pop().unrwap();

It allows to efficiently iterate over just one of the fields:

for x in points.items::"x", i32>() {<br>dbg!(x);

Or iterate over the whole list and grab the pieces as we need them:

for point in points.iter() {<br>let x = point.get::"x", i32>();<br>let y = point.get::y", i32>();<br>dbg!(x, y);

Now this example doesn't actually show any of the advantages a multi-array list might have.<br>There's no padding we could save.

But I can prove that it does save reduce memory allocation that with the right toppings types:

; cargo run -q --example comparison<br>Allocating 500 pizzas.<br>Vec allocated: 16000 bytes<br>List allocated: 14016 bytes (-12.40%)

The code is available online: https://git.fnordig.de/jer/multi-array-list.

You can also grab it from crates.io:

cargo add multi-array-list

Note though that it's nightly-only, uses several experimental features7.<br>It is tested and Miri doesn't complain (yet), but I give absolutely no guarantees about it.<br>I think it might be easy to misuse this to transmute data without resorting to unsafe and there be dragons.<br>I do not plan to actively maintain it, but maybe I use this as a playground to explore reflection a bit more.

Footnotes:

I wrote the code shortly after the pull request landed and started the blog post the same day, but only finished it last night.

Rust allocates a bit more up front to avoid many...