CODEWITHSUNDEEP
rustmemory-layout
mwlon
mwlon

Reputation: 1006

How and why does Rust's Option<Vec<T>> get optimized to 24 bytes?

I was surprised that Option<Vec<T>> has the same size as Vec<T>:

fn main() {
  println!(
    "u128: {} -> {}",
    size_of::<u128>(),
    size_of::<Option<u128>>()
  );
  println!(
    "vec: {} -> {}",
    size_of::<Vec<u16>>(),
    size_of::<Option<Vec<u16>>>()
  );
}

evaluating to

u128: 16 -> 32
vec: 24 -> 24

So

  1. How does Rust represent the None case for Option<Vec>? It looks like a normal Vec's 24 bytes come from 3 8-byte fields: a pointer, a byte capacity, and a length. My guess is that it's using a null pointer for None, but I'm not certain. Would Rust still be able to maintain the same memory layout if Vec held 2 pointers?

  2. Why does Rust do this? For Option<u128> we clearly have the choice of using N bytes as long as N > 16, and Rust chooses N = 32. This of course has nice properties, e.g. we can access the ith element of a Vec<Option<u128>> with only bit shifts (no multiplications). But if that's ideal, shouldn't Rust make Option<Vec<T>> 32 bytes as well?

Rust version: rustc 1.83.0-nightly (1bc403daa 2024-10-11)

Upvotes: 2

Views: 142

Answers (1)

Finn Bear
Finn Bear

Reputation: 1970

1. Option<Vec<_>>

You have discovered a niche value optimization guaranteed by Vec. More specifically:

  • Vec<T> contains...
  • RawVec<T>, which contains...
  • RawVecInner, which contains both...
    • Cap, an usize that can never exceed isize::MAX (known to rustc via rustc_layout_scalar_valid_range_end)
    • Unique<u8>, which contains...
    • NonNull<u8>. The documentation of NonNull specifically notes that the lack of NULL enables a memory layout optimization.

As a result, Option::<Vec<_>>::None is represented by 0 where the pointer would go (which is different than a valid instance of a NULL *const u8 pointer). Alternatively, it could be represented by a value exceeding isize::MAX where Cap would go. The other fields could be arbitrary for such a value. The compiler gets to choose which representation to use arbitrarily, but all zero bytes is be optimal for performance (easier to allocate).

I'm not sure what you mean by a Vec that held two pointers. Adding an additional pointer to Vec would increase the size of both Vec and Option<Vec<_>> by the size of a pointer.

2. Option<u128>

First, let's assume pointers are 8 bytes and the alignment of u128 is 16:

println!("{}", std::mem::size_of::<*const u8>()); // 8
println!("{}", std::mem::align_of::<u128>()); // 16

Consider the value vec![Some(0u128), Some(0u128)]. For soundness, both u128 values must be aligned. By your logic, the first item in the Vec must occupy at least 17 bytes (16 for the u128, 1 for the enum discriminant). The next aligned memory location (multiple of the alignment) would be 32 bytes from the beginning of the Vec. Because Vec doesn't have a way to add padding between items, the padding must fall within Option<u128>, making it 32 bytes. In fact, size is a multiple of alignment for all types.

In case you're interested, the closest thing to a 16-byte Option<u128> is an Option<NonZeroU128>.

But if that's ideal, shouldn't Rust make Option<Vec> 32 bytes as well

As I mentioned, it's an alignment concern not an indexing performance concern. Vec has an alignment of 8, so the size only needs to be a multiple of 8. If you were concerned with indexing performance, it's always possible to increase alignment:

/// Disclaimer: actual performance may vary;
/// consult your benchmark before making any optimization decision!
///
/// A 33% increase in memory usage will reduce cache locality!
#[repr(align(32))]
struct FastVec<T>(Vec<T>);

Upvotes: 2

Related Questions