Magic Memory Optimization in Rust and C

If you like to optimize everything in life (like a psychopath… or like me 😳), you will enjoy this short one. It is surprising how much memory we waste purely from not knowing how our data is laid out. I recently watched a talk by Andrew Kelley, the creator of the Zig language, and was struck by how much a few basic Data-Oriented Design (DoD) tricks can cut a program's memory footprint.

Primitive type sizes

Let's review the size in bytes of a few primitive types, Rust in this case:

• bool: 1
• u8: 1
• u16: 2
• u32: 4
• u64: 8
• char: 4

Struct alignment: Foo

Now that you are a Rust expert and know the byte size of every primitive type, a question. What is the size in bytes of the following struct?

struct Foo {
    elem:  u32,
    other: u16,
}

You have got it — if it were 6, I would not have asked. 6 is not entirely wrong, since the struct holds 4 bytes for a u32 and 2 bytes for a u16, but the size of a struct is computed by aligning to its largest field and rounding the total up to the nearest multiple of that alignment. If that is not obvious yet, here is a simple representation.

Struct padding: Bar

Now let's guess the size in bytes of this one:

struct Bar {
    num:     u16,
    bigger:  u32,
    another: u16,
}

Trickier than it looks. Following the mental model above, Bar would be 12 bytes: the largest alignment among the fields is 4, round every field up to 4, and you get 4 + 4 + 4 = 12.

A smarter approach reclaims the padding sitting between num and another, which gives (2 + 2) + 4 = 8. It looks like we optimized the free space by rearranging the fields — and in fact the Rust compiler is smart enough to do exactly that on its own. That is not the case in every strongly typed language.

Let's print the size of the Rust struct, then of its C equivalent.

The size of Rust structs in memory

std::mem::size_of::<Bar>() // output: 8

The size of C structs in memory

struct Bar {
    uint16_t num;
    uint32_t bigger;
    uint16_t another;
};

sizeof(struct Bar) // output: 12

The Rust compiler reorders the struct, the C compiler (clang here) does not. This is because C programmers really need to understand how computers work at a low level — the ABI — unlike Rustaceans (just kidding 😳). More seriously: the Rust compiler is heavily optimized and handles this for you, but a manual rearrangement in C reaches the same result.

Here is a visual representation of both layouts:

Fixing the C layout by reordering fields

Let's reorder the fields of the C struct and print its size again:

struct Bar {
    uint32_t bigger;
    uint16_t num;
    uint16_t another;
};

sizeof(struct Bar) // output: 8

It works. That does not mean you can ignore data layout in Rust and let the compiler do all the work: a compiler heavily optimizes what you ask it to optimize. Understanding layout still matters.

Enums and padding

Let's continue with enums. Do you know the size of an enum in Rust?

enum HtmlTag {
    H1,
    H2,
    UnorderedList,
    OrderedList,
    ...
}

std::mem::size_of::<HtmlTag>() // output: 1

Note that we are covering enums carrying no data beyond the discriminant of each variant. Those are 1 byte.

Now imagine we are building an HTML tokenizer — a program that walks an HTML source file and extracts every tag with its position. The simplified token struct:

struct HtmlToken {
    start_position: u32,
    token_tag:      HtmlTag,
}

std::mem::size_of::<HtmlToken>() // output: 8

If you followed along, the answer comes easily: 8 bytes. 4 for the u32, 1 for the enum, and 3 bytes of padding.

Now tokenize a large HTML page and generate 10,000 tokens. The token list weighs 10,000 * 8 = 80,000 bytes, of which 30,000 bytes are padding 🥵. That is a lot of wasted memory, and it happens more often than you would think. Booleans are 1 byte too: a struct mixing integers and a boolean will likely generate 3 bytes of padding per instance.

Solution: store 1-byte fields out-of-band

The fix here is to store the enum out-of-band, in a structure made of multiple arrays accessed in parallel by index. With that layout, no padding is generated per instance:

struct HtmlTokens {
    start_positions: [u32; 1],
    token_tags:      [HtmlTag; 1],
}

std::mem::size_of::<HtmlTokens>() // output: 5

With the multi-array technique, an 8-byte instance per HTML token becomes two arrays holding 5 bytes per entry. For our tokenizer, that cuts the token list in memory by 40% — impressive for such a small change.

Recap

Two techniques to shrink struct memory:

• The order of fields in a struct can significantly change the layout and what the compiler can optimize.
• Store booleans and 1-byte enums out-of-band to avoid padding on every instance.

Thanks for reading, and happy coding.

Want to keep reading? Here is an article on dynamic binary visualization.