Algebraic Data Types: Structs, Enums & Memory Dynamics

Rust leverages Algebraic Data Types (ADTs) to model domain concepts with mathematical precision. Instead of relying on class inheritance or untyped unions, Rust programs represent state through two core primitives: Product Types (Structs) and Sum Types (Enums).

1. Product Types vs Sum Types#

In type theory, types can be combined using two primary algebraic operations:

Product Types (Structs)#

A struct combines multiple field types into a single unit. For a struct $S$ containing fields $F_1, F_2, \dots, F_k$, the total number of possible states (cardinality $|S|$) is the Cartesian product of the field domains:

For example, a struct with a bool (2 states) and a u8 (256 states) has $|S| = 2 \times 256 = 512$ distinct states.

Sum Types (Enums)#

An enum expresses an exclusive choice between a closed set of variants. For an enum $E$ with variants $V_1, V_2, \dots, V_m$, the cardinality $|E|$ is the sum of the variant cardinalities:

This eliminates illegal states at compile time: a value can never be in two variants at once.

2. Memory Layout of Enums#

An enum is stored in hardware as a tagged union. It consists of two components:

1. Discriminant (Tag): An integer identifying which variant is currently active.
2. Payload: A memory union sized to hold the largest variant payload.

1
2
3
4
5
6
7
8
9
10
11
12
use std::mem::size_of;

enum Message {
    Quit,                       // 0 bytes payload
    Move { x: i32, y: i32 },    // 8 bytes payload (two i32)
    Write(String),              // 24 bytes payload (ptr + len + cap)
}

fn main() {
    println!("String size: {} bytes", size_of::<String>());   // 24 bytes
    println!("Message size: {} bytes", size_of::<Message>()); // 32 bytes (24B payload + 1B tag + 7B padding)
}

3. Niche Filling & Null Pointer Optimization#

One of Rust's most elegant compile-time optimizations is Null Pointer Optimization (NPO), also known as niche filling.

Certain types have invalid bit patterns (niches). For example, a Rust reference &T or standard NonNull<T> can never be null (address 0x00000000). The compiler detects this invariant and uses the zero address to represent the None variant of Option<&T>:

4. Struct Field Reordering#

In C, structs are laid out strictly in declaration order, which can introduce massive padding bloat if small fields alternate with large fields.

By default, the Rust compiler reorders fields in decreasing order of alignment size:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
use std::mem::size_of;

// Rust layout (default): rustc reorders to minimize padding
struct Optimized {
    a: u8,   // 1 byte
    b: u64,  // 8 bytes
    c: u16,  // 2 bytes
}

// C-compatible layout: fields preserved in exact order
#[repr(C)]
struct Unoptimized {
    a: u8,   // 1 byte (+ 7 bytes padding!)
    b: u64,  // 8 bytes
    c: u16,  // 2 bytes (+ 6 bytes tail padding!)
}

fn main() {
    println!("Optimized size: {} bytes", size_of::<Optimized>());     // 16 bytes
    println!("Unoptimized size: {} bytes", size_of::<Unoptimized>()); // 24 bytes
}

5. Concept Verification#

Test your understanding of Algebraic Data Types and compiler layout optimizations: