How to improve Vec initialization time?

Question

Initializing a Vec in Rust is incredibly slow if compared with other languages. For example, the following code

let xs: Vec<u32> = vec![0u32, 1000000];

will translate to

let xs: Vec<u32> = Vec::new();
xs.push(0);
xs.push(0);
xs.push(0);
// ...

one million times. If you compare this to the following code in C:

uint32_t* xs = calloc(1000000, sizeof(uint32_t));

the difference is striking.

I had a little bit more luck with

let xs: Vec<u32> = Vec::with_capacity(1000000);
xs.resize(1000000, 0);

bit it's still very slow.

Is there any way to initialize a Vec faster?

How did you compile your Rust program? Did you pass the `--release` flag? (Which will enable optimizations.) — BurntSushi5, Jul 21 '16 at 13:00
Correct me if I'm wrong, but isn't that `calloc` call allocating an array of one million zero-sized elements? The man page says doing this doesn't allocate *anything*, so *of course* the difference would be striking... — DK., Jul 21 '16 at 13:13
Check your source, `vec![0u32, 1000000]` does *not* compile into one million call to `push`. It compiles essentially to `Vec::with_capacity` + `Vec::resize`. — mcarton, Jul 21 '16 at 13:22
You need to show the *actual* code you're testing and the compiler switches you're using, because when I copy+paste your code as-given (fixing the C code so that `xs` is a pointer), *both* examples complete instantaneously. — DK., Jul 21 '16 at 13:40
@mcarton I was using the definition described in https://doc.rust-lang.org/book/macros.html, but now I saw a footnote that says that the actual implementation might differ. — André Wagner, Jul 21 '16 at 13:43

Alex Hansen · Accepted Answer · 2016-07-21T13:49:29.340

8

You are actually performing different operations. In Rust, you are allocating an array of one million zeroes. In C, you are allocating an array of one million zero-length elements (i.e. non-existent elements). I don't believe this actually does anything, as DK commented on your question and pointed out.

Also, Running the code you presented verbatim gave me very comparable times on my laptop when optimizing, however this is probably because the vector allocation in Rust is being optimized away, as the variable is never used.

cargo build --release
time ../target/release/test

real   0.024s 
usr    0.004s
sys    0.008s

and the C:

gcc -O3 test.c 
time ./a.out

real   0.023s
usr    0.004s
sys    0.004s`

Without --release, the Rust performance drops, presumably because the allocation actually happens. Note that calloc() also looks to see if the memory is zeroed out first, and doesn't reset the memory if it is already set to zero. This makes the execution time of calloc() somewhat reliant on the previous state of your memory.

edited Jul 21 '16 at 13:49

answered Jul 21 '16 at 13:40

Alex Hansen

301
2
9

1

I now see that the problem was that I wasn't using the `--release` flag. Using this flag made it fast. In my question I was also making the wrong assumption that the `vec!` macro would generate tons of `push()` calls, which is not true. So I'm accepting this answer. – André Wagner Jul 21 '16 at 13:46
Ah, ok. I will undo my edit to edit, then. Note that you can also configure exactly what gets optimized in the cargo.toml file. – Alex Hansen Jul 21 '16 at 13:49
This is a tangent, but do you have a reference for "calloc() also looks to see if the memory is zeroed out first"? How would it be able to check in less time than actually zeroing it? – Chris Emerson Jul 21 '16 at 14:38
Not the most reliable source, but I was going off of here http://stackoverflow.com/questions/1538420/difference-between-malloc-and-calloc#comment43152189_1585987 . The way I presented it does seem to imply a comparison to zero, but it is actually doing a slightly different check (according to this comment). – Alex Hansen Jul 21 '16 at 14:44

How to improve Vec initialization time?

1 Answers1