CODEWITHSUNDEEP
rustcachingcache-locality
Rahn
Rahn

Reputation: 5425

Do different ways of initializing a Vec<T> create different memory layout?

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.

Upvotes: 0

Views: 112

Answers (2)

Jmb
Jmb

Reputation: 23443

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

Upvotes: 2

Aleksander Krauze
Aleksander Krauze

Reputation: 6165

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.

Upvotes: 0

Related Questions