7

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.

trent
  • 25,033
  • 7
  • 51
  • 90
danglingptr
  • 143
  • 2
  • 7
  • 1. no, magic doesn't exist 2. `1024*1024*4` != `1024*1024` 3. your code don't even compile. – Stargateur Dec 13 '19 at 01:37
  • 1
    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, https://github.com/rust-lang/rust/blob/ddca1e09c36a6ce21d95fec1619f23ba59b69c8a/src/liballoc/vec.rs#L1719. I believe that with const fn this could change – Stargateur Dec 13 '19 at 02:10

2 Answers2

4

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

trent
  • 25,033
  • 7
  • 51
  • 90
  • 1
    Anything that state that `from_raw_parts()` can be use with alloc ? Apart the fact that it's obvious. – Stargateur Dec 13 '19 at 15:30
  • 1
    Hmm, good question. `std::alloc` says [the standard library has one “global” memory allocator that is used for example by `Box` and `Vec`.](https://doc.rust-lang.org/std/alloc/index.html), and `alloc_zeroed` [is documented](https://doc.rust-lang.org/std/alloc/fn.alloc_zeroed.html) to use the global allocator. – trent Dec 13 '19 at 15:38
3

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.

Fang Zhang
  • 1,597
  • 18
  • 18