CODEWITHSUNDEEP
rust
Ted Vu
Ted Vu

Reputation: 149

Capacity of vectors created with macro

let vec_macro = vec![0, 1, 2, 3, 4];
let mut vec = Vec::new();

for i in 0..5 {
    vec.push(i)
}

println!("Capacity of vec with macro: {}", vec_macro.capacity());
println!("Capacity of vec push: {}", vec.capacity());

// Result: 
// Capacity of vec with macro: 5
// Capacity of vec push: 8

I created 2 vectors, first one with macro vec! and the second one with Vec::new(), then I push item from 0 to 4 into them. The expected result is the capacity of these two vectors are the same, but it's not. Is this the bug in the implementation of vec!?

Upvotes: 1

Views: 730

Answers (2)

prog-fh
prog-fh

Reputation: 16910

The macro knows the number of elements, so it creates the vector with the optimal capacity (see also with_capacity()).

Your loop invokes push() several times, but this operation does not know by itself when we will stop pushing elements. So the strategy behind this is to amortize the cost of dynamic memory reallocation with an exponential capacity (0, 4, 8, 16, 32... for example on my computer). When you push very few elements, the capacity stays low (we do not waste too much unused allocated memory), but if you push many elements, the reallocations will grow by bigger and bigger steps in order to happen not too often.

At the moment, we see that it simply doubles the capacity (whatever it is) when it is exhausted. If we start from zero then just push, it seems to choose 4 as initial capacity then doubles it as needed, but if we start with 5 it will still continue to double the capacity (10, 20...). However, what we see now is not guaranteed and might change at any time in future releases.

Upvotes: 6

PitaJ
PitaJ

Reputation: 15084

vec![a, b, ...] is not the same as a repeated push. If you look at the source code for the macro, it looks like this:

    ($($x:expr),+ $(,)?) => (
        $crate::__rust_force_expr!(<[_]>::into_vec(box [$($x),+]))
    );

The important part is the <[_]>::into_vec(box [$($x),+]):

  • box [$($x),+] is special syntax to create a "boxed slice" directly on the heap, as opposed to creating it on the stack and then moving it to the heap
  • <[_]>::into_vec calls slice::into_vec

If we look at the source code of into_vec:

    pub fn into_vec<T, A: Allocator>(b: Box<[T], A>) -> Vec<T, A> {
        unsafe {
            let len = b.len();
            let (b, alloc) = Box::into_raw_with_allocator(b);
            Vec::from_raw_parts_in(b as *mut T, len, len, alloc)
        }
    }

And the signature of Vec::from_raw_parts_in:

pub unsafe fn from_raw_parts_in(
    ptr: *mut T,
    length: usize,
    capacity: usize,
    alloc: A
) -> Self;

You can see that the slice length is passed as both the Vec length and capacity.

The Vec documentation specifies this behavior of the macro:

vec![x; n], vec![a, b, c, d], and [Vec::with_capacity(n)][Vec::with_capacity], will all produce a Vec with exactly the requested capacity. If [len] == [capacity], (as is the case for the [vec!] macro), then a Vec<T> can be converted to and from a [Box<[T]>][owned slice] without reallocating or moving the elements.

As prog-fh said, Vec::push will exponentially reallocate when necessary, and will not end on a capacity of 5 unless you otherwise set the capacity manually via with_capacity or otherwise. It should be noted that this exponential growth is an implementation detail, not guaranteed by the Vec documentation.

Upvotes: 2

Related Questions