Allocations

For a variable to be growable (so that it can occupy different amounts of space in the memory at different times), it needs to be allocated on the heap, and not on the stack. The stack works faster, since on the loading of the program, it gets assigned to it. But the heap is slower, since for each allocation you need to perform a system call to the kernel, which means you will need a context switch (to kernel mode) and back (to user mode). This makes things too slow.

Vectors (and other standard library structures) have an interesting way of allocating that memory so that they perform as efficiently as possible. Let's check the algorithm it uses to allocate new memory with this code:

    let mut my_vector = vec![73, 55];
    println!(
        "length: {}, capacity: {}",
        my_vector.len(),
        my_vector.capacity()
    );

    my_vector.push(25);
    println!(
        "length: {}, capacity: {}",
        my_vector.len(),
        my_vector.capacity()
    );

    my_vector.push(33);
    my_vector.push(24);
    println!(
        "length: {}, capacity: {}",
        my_vector.len(),
        my_vector.capacity()
    );

The output should be something along these lines:

This means that, at the beginning, the vector will have allocated only the space required by our first two elements. But as soon as we push a new one, it will allocate space for two new elements, so that with the fourth push it won't need to allocate more memory. When we finally insert a fifth element, it allocates space for another four, so that it does not need to allocate until it gets to the ninth.

If you follow the progression, the next time it will allocate space for 8 more elements, making the capacity grow to 16. This is dependent on the first allocation, and if we had started the vector with 3 elements, the numbers would be 3, 6, 12, 24,... We can, in any case, force the vector to pre-allocate a given number of elements with two functions, reserve() and reserve_exact(). The former will reserve space for at least the given number of elements, while the latter will reserve space exactly for the given number of elements. This is really useful when you know the size of the input, so that it doesn't need to allocate once and again. It will just allocate once.