How to efficiently create a large vector of items initialized to the same value?

Question

I'm looking to allocate a vector of small-sized structs.

This takes 30 milliseconds and increases linearly:

let v = vec![[0, 0, 0, 0]; 1024 * 1024];

This takes tens of microseconds:

let v = vec![0; 1024 * 1024];

Is there a more efficient solution to the first case? I'm okay with unsafe code.

Answer 1

Fang Zhang's answer is correct in the general case. The code you asked about is a little bit special: it could use alloc_zeroed, but it does not. As Stargateur also points out in the question comments, with future language and library improvements it is possible both cases could take advantage of this speedup.

This usually should not be a problem. Initializing a whole big vector at once probably isn't something you do extremely often. Big allocations are usually long-lived, so you won't be creating and freeing them in a tight loop -- the cost of initializing the vector will only be paid rarely. Sooner than resorting to unsafe, I would take a look at my algorithms and try to understand why a single memset is causing so much trouble.

However, if you happen to know that all-bits-zero is an acceptable initial value, and if you absolutely cannot tolerate the slowdown, you can do an end-run around the standard library by calling alloc_zeroed and creating the Vec using from_raw_parts. Vec::from_raw_parts is unsafe, so you have to be absolutely sure the size and alignment of the allocated memory is correct. Since Rust 1.44, you can use Layout::array to do this easily. Here's an example:

pub fn make_vec() -> Vec<[i8; 4]> {
    let layout = std::alloc::Layout::array::<[i8; 4]>(1_000_000).unwrap();
    // I copied the following unsafe code from Stack Overflow without understanding
    // it. I was advised not to do this, but I didn't listen. It's my fault.
    unsafe {
        Vec::from_raw_parts(
            std::alloc::alloc_zeroed(layout) as *mut _,
            1_000_000,
            1_000_000,
        )
    }
}

See also

• How to perform efficient vector initialization in Rust?

Answer 2

vec![0; 1024 * 1024] is a special case. If you change it to vec![1; 1024 * 1024], you will see performance degrades dramatically.

Typically, for non-zero element e, vec![e; n] will clone the element n times, which is the major cost. For element equal to 0, there is other system approach to init the memory, which is much faster.

So the answer to your question is no.