Vec's Capacity Lives in a Niche: How Rust's RawVec Got One Word Smaller

TL;DR: Vec<T> is three machine words: pointer, length, capacity. It manages that by storing the capacity in a niche type — a usize whose top bit is guaranteed to be zero — so the “zero capacity” case is representable without an extra discriminant. And the growth policy is max(2 * cap, required), with a special minimum for tiny vectors.

The growth policy

rust
// library/alloc/src/raw_vec/mod.rs:539-555

// Nothing we can really do about these checks, sadly.
let required_cap = len.checked_add(additional).ok_or(CapacityOverflow)?;

// This guarantees exponential growth. The doubling cannot overflow
// because `cap <= isize::MAX` and the type of `cap` is `usize`.
let cap = cmp::max(self.cap.as_inner() * 2, required_cap);
let cap = cmp::max(min_non_zero_cap(elem_layout.size()), cap);

Three lines:

checked_add catches the length overflow and turns it into a CapacityOverflow error rather than a panic with a confusing message.
max(2*cap, required) is the amortized-doubling rule. If the caller asked for a specific capacity, that wins; otherwise double.
max(min_non_zero_cap(size), cap) imposes a floor.

The doubling cannot overflow because cap <= isize::MAX and the multiplication is done in usize. That invariant is why the code can use plain * instead of checked_mul.

The tiny-vector floor

rust
// library/alloc/src/raw_vec/mod.rs:163-176

// Tiny Vecs are dumb. Skip to:
// - 8 if the element size is 1, because any heap allocator is likely
// to round up a request of less than 8 bytes to at least 8 bytes.
// - 4 if elements are moderate-sized (<= 1 KiB).
// - 1 otherwise, to avoid wasting too much space for very short Vecs.
const fn min_non_zero_cap(size: usize) -> usize {
    if size == 1 {
        8
    } else if size <= 1024 {
        4
    } else {
        1
    }
}

The reasoning is allocator-aware: malloc rounds a 1-byte request up to a 16-byte chunk anyway, so allocating 1 byte and then reallocating to 8 is pure waste. For medium-sized elements, 4 gives a reasonable first allocation; for large elements, 1 avoids over-allocating.

The niche

rust
// library/alloc/src/raw_vec/mod.rs:40-51

type Cap = core::num::niche_types::UsizeNoHighBit;

// SAFETY: 0 *definitely* is less than isize::MAX.
const ZERO_CAP: Cap = unsafe { Cap::new_unchecked(0) };

/// `Cap(cap)`, except if `T` is a ZST then `Cap::ZERO`.
///
/// # Safety: cap must be <= `isize::MAX`.
const unsafe fn new_cap<T>(cap: usize) -> Cap {
    // SAFETY: Upheld by caller.
    if T::IS_ZST { ZERO_CAP } else { unsafe { Cap::new_unchecked(cap) } }
}

UsizeNoHighBit is a usize with an invariant: the top bit is always zero. That is a niche — a value the type cannot represent — and Rust’s niche optimization uses it to make Option<Cap> the same size as Cap.

Why does that matter? Because RawVec needs to represent “no allocation” (distinguished by a null pointer) and a capacity. With the invariant, the capacity’s top bit is free to be used as a flag… and, in fact, Cap::ZERO is the zero-capacity case, which is also the ZST case.

The payoff: Vec<T> is { ptr, cap, len } — three words — instead of four. For a Vec<u8> of 24 bytes on the stack, that is 8 bytes saved on every Vec in the program, including the ones on the stack of every function.

`into_raw_parts` and `from_raw_parts`

rust
// library/alloc/src/vec/mod.rs:795-801

#[must_use = "losing the pointer will leak memory"]
#[stable(feature = "vec_into_raw_parts", since = "1.93.0")]
#[rustc_const_unstable(feature = "const_heap", issue = "79507")]
pub const fn into_raw_parts(self) -> (*mut T, usize, usize) {
    let mut me = ManuallyDrop::new(self);
    (me.as_mut_ptr(), me.len(), me.capacity())
}

ManuallyDrop suppresses the destructor so the buffer is not freed, while the pointer/length/capacity are read out of the value. The reconstruction side is the mirror image:

rust
// library/alloc/src/vec/mod.rs:1127-1140

pub const unsafe fn from_raw_parts_in(
    ptr: *mut T,
    length: usize,
    capacity: usize,
    alloc: A,
) -> Self {
    ub_checks::assert_unsafe_precondition!(
        check_library_ub,
        "Vec::from_raw_parts_in requires that length <= capacity",
        (length: usize = length, capacity: usize = capacity) => length <= capacity
    );
    // SAFETY: Upheld by caller.
    unsafe { Vec { buf: RawVec::from_raw_parts_in(ptr, capacity, alloc), len: length } }
}

It is const, and the only validation is a debug-mode UB check. That makes it a zero-cost FFI boundary primitive: Vec::into_raw_parts and Vec::from_raw_parts round-trip through C without touching the allocator at all.

`drain` is destructive but reversible

rust
// library/alloc/src/vec/drain.rs:88-137

pub fn keep_rest(self) {
    // At this moment layout looks like this:
    //
    // [head] [yielded by next] [unyielded] [yielded by next_back] [tail]
    //        ^-- start         \_________/-- unyielded_len        \____/-- self.tail_len
    //                          ^-- unyielded_ptr                  ^-- tail
    ...
    let mut this = ManuallyDrop::new(self);
    unsafe {
        let source_vec = this.vec.as_mut();
        let start = source_vec.len();
        let tail = this.tail_start;
        let unyielded_len = this.iter.len();
        let unyielded_ptr = this.iter.as_slice().as_ptr();
        // ZSTs have no identity, so we don't need to move them around.
        if !T::IS_ZST {
            let start_ptr = source_vec.as_mut_ptr().add(start);
            // memmove back unyielded elements
            if unyielded_ptr != start_ptr {
                ptr::copy(src, dst, unyielded_len);
            }
            // memmove back untouched tail
            if tail != (start + unyielded_len) {
                ptr::copy(src, dst, this.tail_len);
            }
        }
        source_vec.set_len(start + unyielded_len + this.tail_len);
    }
}

The tail is restored with one memmove, not one move per element. And the Drop implementation uses a nested guard struct so the memmove happens even if the user’s Drop impl panics mid-drain:

rust
// library/alloc/src/vec/drain.rs:176-200

impl<T, A: Allocator> Drop for Drain<'a, T, A> {
    fn drop(&mut self) {
        /// Moves back the un-`Drain`ed elements to restore the original `Vec`.
        struct DropGuard<'r, 'a, T, A: Allocator>(&'r mut Drain<'a, T, A>);
        impl<'r, 'a, T, A: Allocator> Drop for DropGuard<'r, 'a, T, A> {
            fn drop(&mut self) {
                if self.0.tail_len > 0 {
                    unsafe {
                        let source_vec = self.0.vec.as_mut();
                        // memmove back untouched tail, update to new length
                        let start = source_vec.len();
                        let tail = self.0.tail_start;
                        if tail != start {
                            let src = source_vec.as_ptr().add(tail);
                            let dst = source_vec.as_mut_ptr().add(start);
                            ptr::copy(src, dst, self.0.tail_len);
                        }
                        source_vec.set_len(start + self.0.tail_len);
                    }
                }
            }
        }

The naive alternative — Vec::remove in a loop — is O(n²) in moves.

Where it lives

library/alloc/src/raw_vec/mod.rs — the growth policy, min_non_zero_cap, the Cap niche.
library/alloc/src/vec/mod.rs — into_raw_parts, from_raw_parts_in.
library/alloc/src/vec/drain.rs — the DropGuard trick.
library/core/src/num/niche_types.rs — UsizeNoHighBit.

Takeaway

The niche trick here is a nice illustration of a general Rust idiom: when a type has a value it can never hold, that value is free. usize can never be usize::MAX in a capacity, so the top bit is free, so Option<Cap> is free, so Vec is one word smaller. Across a program with thousands of live Vecs, that is megabytes of stack and heap.