Rust Vec Under the Hood
A Vec handle is three numbers, a pointer, a length and a capacity. Growth doubles that block when it runs out.
vec! buys an exact-fit block
Three items arrive at once, so the first block fits exactly three:
let v = vec![10, 20, 30];
println!("len = {}, capacity = {}", v.len(), v.capacity());Watch the block double
Push one by one and print the capacity each time it changes:
let mut v: Vec<i32> = Vec::new();
let mut last = 0;
for i in 0..10 {
v.push(i);
if v.capacity() != last {
println!("len {} -> capacity {}", v.len(), v.capacity());
last = v.capacity();
}
}Spare room is room already paid for
Ten slots are reserved and three are filled. Seven pushes still cost no new block:
let mut v: Vec<i32> = Vec::with_capacity(10);
v.extend([1, 2, 3]);
println!("spare = {}", v.spare_capacity_mut().len());A borrow cannot cross a push
first points into the block. A push may move the whole block to a new address. The compiler refuses the programme before it can dangle:
let mut v = vec![1, 2, 3];
let first = &v[0];
v.push(4); // error E0502: v is borrowed by first
println!("{first}");shrink_to_fit hands the spare back
The block was bought for 100 items. Only 3 live there. shrink_to_fit asks the allocator for a block that fits:
let mut v: Vec<i32> = Vec::with_capacity(100);
v.extend([1, 2, 3]);
println!("before = {}", v.capacity());
v.shrink_to_fit();
println!("after = {}", v.capacity());Cut the spare off for good
into_boxed_slice freezes the Vec into a boxed slice. The capacity is gone. The handle is now a fat pointer: an address and a length:
let mut v: Vec<i32> = Vec::with_capacity(100);
v.extend([1, 2, 3]);
let boxed: Box<[i32]> = v.into_boxed_slice();
println!("len = {}, handle = {} bytes", boxed.len(), std::mem::size_of::<Box<[i32]>>());Example
fn main() {
let mut bytes: Vec<u8> = Vec::new();
for i in 0..20 { bytes.push(i); }
println!("u8 vec: len {}, capacity {}", bytes.len(), bytes.capacity());
let mut nums: Vec<i32> = Vec::new();
for i in 0..20 { nums.push(i); }
println!("i32 vec: len {}, capacity {}", nums.len(), nums.capacity());
let mut units: Vec<()> = Vec::new();
units.push(());
units.push(());
println!("unit vec: len {}, capacity {}", units.len(), units.capacity());
println!("every handle = {} bytes", std::mem::size_of::<Vec<i32>>());
}Key points
- The handle weighs 24 bytes on the stack, at 3 items or at 3 million items
- Growth doubles the block each time it runs out, so copying stays rare
- First blocks are small: 4 items for most types, 8 items for one-byte types
- capacity counts items, not bytes: a Vec<u64> with capacity 4 owns 32 bytes of heap room
- A borrow into a Vec cannot cross a push: growth may move every item to a new block
- The handle is just an address, a count of items, and a count of spare slots
- The pointer aims at the heap block that holds the items.
In this example, three Vec types keep a growth diary. The u8 Vec ends at length 20 and capacity 32: its blocks ran 8, 16, 32. The i32 Vec also ends at 32: its blocks ran 4, 8, 16, 32. Both handles still weigh 24 bytes, because a handle never grows with its block. The unit Vec is the surprise. Its items weigh nothing, so it never allocates at all. Rust reports its capacity as the biggest number a usize can hold. A Vec of nothing needs no room, ever.
Note
Vec::new allocates nothing
The first block is bought by the first push, not before
Try it Yourself
Edit the code, then press Run.
Running is simulated · Rust Playground
Exercise
A Vec<i32> shows length 6 and capacity 8. Two more pushes fit. What happens on the push after that?