Do different ways of initializing a Vec create different memory layout?

Question

fn main() {
    let vec0 = vec![0; 10];

    let mut vec1 = vec![];
    for _ in 0..10 {
        vec1.push(0);
    }

    assert_eq!(vec0.len(), vec1.len());
}

In this example, vec0 and vec1 are identical when accessing their items with index. But do these 2 approaches of initializing make different memory layout?

More background: I'm building a (hopefully) cache friendly container (Vec<T> so far) to exploit cache locality. Usually in C++ you can just allocate a new array with dynamic length (auto array = new DataType[length];) to enforce compact memory layout, yet variant length array is simply impossible in Rust. So I'm looking for a way to build Vec<T> that could improve cache hit/miss ratio during execution.

I put both methods into _compiler explorer_ and to my surprise there does seem to be a difference. Here is the [`vec!` macro variant](https://godbolt.org/z/G8jco738Y) and there is the [loop variant](https://godbolt.org/z/avnKdWb9b). — frankenapps, Aug 02 '23 at 04:32
@frankenapps that's probably because of reallocations needed in the "loop variant". If you create vector with the `with_capacity(10)` the compile will produce _very_ similar output. — Aleksander Krauze, Aug 02 '23 at 04:46

score 2 · Answer 1 · answered Aug 02 '23 at 06:44

2

As answered by @AleksanderKrauze, the only difference between the two is the final capacity and the initialization time due to the potential multiple reallocations in the for loop. However you can do an equivalent of your C++ dynamic array in Rust:

let a = Box::from_iter (std::iter::repeat (0).take (length));

Playground

answered Aug 02 '23 at 06:44

Jmb

18,893
2
28
55

Is accessing contiguous items from this `Box<[T]>` faster than aceessing items from `Vec` – Rahn Aug 02 '23 at 06:57
1

You would need to benchmark to be sure, but I would expect them to be the same speed. However the `Box<[T]>` takes 64 bits less memory because it doesn't need to store the `capacity`, and it ensures that you never accidentally reallocate. – Jmb Aug 02 '23 at 07:00
@Jmb I didn't know about `Box::from_iter`, thanks. For those that are curious it uses [Vec::into_boxed_slice](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.into_boxed_slice) under the hood. – Aleksander Krauze Aug 02 '23 at 07:50

score 0 · Answer 2 · answered Aug 02 '23 at 04:42

From the documentation

A contiguous growable array type with heap-allocated contents, written Vec<T>

std::vec::Vec<T> in Rust is pretty much the same as std::vector<T> in C++. They both will store their data in a contiguous array of elements. In Rust this is even more obvious, because Vec<T> implements Deref<Target = [T]>. And all slices represent a "view into a contiguous sequence".

There is no difference in how data is layed out in memory between different methods of creating a Vec. The only difference could be the amount of capacity, since macro vec! will create vector using it's with_capacity method, while when you push to a vector you will have to reallocate and due to amortization you could end up with different capacity at the end (using macro will also be faster, since you don't have to do all those reallocations).

Usually in C++ you can just allocate a new array with dynamic length (auto array = new DataType[length];) to enforce compact memory layout, yet variant length array is simply impossible in Rust.

This is not exactly true. There are no stable and safe methods in the standard library to do this. However if you want to use allocator yourself, or use some unstable features (for example Box::new_uninit_slice) you can crate exactly the same heap-stored array. Although Vec will probably work fine enough. Just remember to create it using with_capacity.

Do different ways of initializing a Vec create different memory layout?

2 Answers2