How rustc Sorts Struct Fields by log2(Size) and Then Hides a Niche

TL;DR: rustc is allowed to reorder the fields of a repr(Rust) struct — and it does, sorting them by log2(max(align, size)) so that fields with similar alignment end up adjacent and the padding is minimised. For enums it goes further: it finds the largest “niche” — the invalid value range of the biggest variant — and reserves it as the discriminant, which is why Option<&T> is exactly one pointer wide.

Layout is one of the places where a compiler either earns its keep or wastes memory. rustc’s layout algorithm is a nice piece of engineering: the field reordering is a sort key rather than a bin-packing heuristic, and the enum algorithm is a search for a hole.

Field reordering as a sort key

The naive approach to minimising padding is a bin-packing problem: try to find an order of the fields that leaves the fewest holes. rustc does something much simpler and cheaper — it sorts the fields.

The key insight is that if you sort fields by decreasing alignment, the padding is at most max_align bytes at the end. Sorting by alignment alone is not optimal, though, because it wastes space for fields whose size is much larger than their alignment.

rustc’s sort key is log2(max(align, size)):

• the alignment matters, because a field’s alignment determines the padding it introduces;
• the size matters, because a large field with a small alignment is a poor neighbour for small-alignment fields.

Sorting by log2 of that combined value groups similar fields together: all the 1-byte fields, then the 2-byte fields, then 4, then 8, then 16… The result is that padding is concentrated at the ends rather than scattered, and the total is close to optimal for the common case of homogeneous structs.

There is one more twist: the niche position. When a struct has a field with a niche (a bool, a char, a NonZeroU32, an enum with unused discriminants), the struct itself has a niche, and where the niche ends up depends on where the field sits. rustc biases the ordering so that niche-bearing fields land in positions where the niche is most useful.

Enums: the niche hunt

The famous example is:

size_of::<Option<&T>>() == size_of::<&T>()  // 8

How is that possible? A &T has a niche: null is not a valid reference. So the pointer’s bit pattern has “invalid” values, and Option<&T> can use one of them to mean “None”.

For a general enum, rustc computes the layout of the biggest variant, finds the largest hole in it — the range of bit patterns that cannot occur — and reserves part of that hole for the discriminant.

The interesting engineering is in the corner cases:

• Multiple variants with different sizes. The enum’s size is the size of the biggest variant; smaller variants are padded. But rustc tries to place the discriminant in a niche so that the padding is not wasted.
• Nested enums. An enum variant’s payload may itself have a niche, and the search has to find the largest niche across all variants.
• Data-carrying enums. When there is no room for a niche, the enum gets a separate tag and the payload is placed next to it — and rustc then widens the tag to the alignment of the first field, specifically to stop LLVM from memcpy-ing the padding around.

That last detail is worth calling out because it is a pure-codegen concern leaking into the layout algorithm:

the tag is widened to the first field’s alignment specifically to stop LLVM memcpy-ing padding

If the tag were 1 byte and the payload 8-byte aligned, LLVM would emit a memcpy that includes 7 bytes of padding — which is both slow and a potential source of uninitialised-memory reads.

The niche is also how Option<Box<T>> stays small

The same machinery applies to any type with a niche. Option<Box<T>> is also one pointer, because Box has the null niche. Option<NonZeroU32> is four bytes. Option<bool> is one byte. These are not special cases in the standard library — they are consequences of the layout algorithm.

The SizeSkeleton escape hatch

Layout cannot always be computed: a generic function’s layout depends on its type parameters, and at monomorphization time the parameters may be opaque.

// compiler/rustc_abi/src/layout.rs

rustc handles this with a SizeSkeleton: a conservative fallback describing the size and pointer-fatness of a type without knowing its exact layout. It is not enough to compute field offsets, but it is enough to keep transmute checks and ABI computations working under generics.

The layout is a query, so it is cached

Layout computation is not free — it involves the whole algorithm above — so it is a memoized query:

// compiler/rustc_ty_utils/src/layout.rs

and the caching key is the type, so a type’s layout is computed once per compilation session. In an incremental build it is additionally cached on disk, because the layout of a type is stable across sessions as long as the type is unchanged.

Where it lives

• compiler/rustc_abi/src/layout.rs — the layout algorithm, field reordering, niche computation.
• compiler/rustc_ty_utils/src/layout.rs — the layout_of query provider.
• compiler/rustc_target/src/callconv/x86_64.rs — the ABI classification that follows from the layout.

Takeaway

The interesting idea here is that “minimise padding” and “find a hole to put the tag in” are not separate problems. Once you know the niche of the largest variant, the discriminant is free, and the whole enum shrinks. And the field ordering trick — sorting by log2(max(align, size)) — is a case where a sort beats a bin-packer: the search space is O(n log n) instead of O(n!), and for the shapes that real code has, the results are nearly identical.