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.

Breadstuff

1. no, magic doesn't exist 2. 1024*1024*4 != 1024*1024 3. your code don't even compile. – Hydrangea

I did my own test, unfortunatly you right it's way more slow and the explanation is simple, Rust doesn't look if array type is zero, github.com/rust-lang/rust/blob/…. I believe that with const fn this could change – Hydrangea

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?

Therapeutics

Anything that state that from_raw_parts() can be use with alloc ? Apart the fact that it's obvious. – Hydrangea

Hmm, good question. std::alloc says the standard library has one “global” memory allocator that is used for example by Box<T> and Vec<T>., and alloc_zeroed is documented to use the global allocator. – Therapeutics

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.

Saleh

Answer 3

A straightforward way to do this which doesn't double your memory usage by allocating a slice (array) of static pre-defined values is to use with_capacity in combination with resize.

This keeps all of your memory usage confined to the heap.

let mut v = Vec::with_capacity(1000000); // large !
v.resize(1000000, value);

Notes: It is possible the Rust Compiler does some optimization which doesn't result in extra memory usage when using a slice for initialization.

vec![value; 1000000]; // large ! and might (probably will?) cause a stack overflow

I don't think it does this, but I could be wrong.

This is the solution I went for when I found there is no Vec constructor function which takes a single "value" and the "count of the number of elements (copies) of that value".

Fasto