为何通过替换默认值填充Vec比预分配容量填充快得多？

Hey folks, let me start with a bit of context—normally, I don't sweat over micro-optimizations when solving programming puzzles with Rust. My standard move for vectors is firing up Vec::with_capacity to pre-allocate space, then calling push to add elements one by one. Most of the time, this gets the job done without any issues, so I never really questioned it.

But recently, I hit a puzzle where raw speed was non-negotiable, and that forced me to re-examine my implementation. Since I knew exactly how big my vector needed to be upfront, I decided to run a head-to-head between my go-to with_capacity + push flow versus creating a vector pre-filled with default values and then replacing those values. The result? The pre-filled approach was way faster—and I wanted to break down why that's the case.

Let's dig into the under-the-hood differences:

• Vec::with_capacity + push: Sure, pre-allocating with with_capacity reserves the right amount of memory upfront, but every single push still does a bounds check (even though we logically know there's space left). On top of that, each push has to increment the vector's length counter before writing the new element to the next slot. These small overheads add up when you're dealing with large vectors.
• Pre-filled Vec (e.g., vec![Default::default(); N] + index replacement): When you create a vector this way, Rust handles two things in a single bulk operation: allocating the memory and filling it with default values. Then, when you replace elements via indexing (like vec[i] = new_val), the compiler can often optimize away bounds checks entirely—especially if the loop's range is tied directly to the vector's length (which it usually is in these cases). Plus, writing via index skips the step of incrementing the length counter, since the vector's length is already set to its full capacity from the start.

Another big factor is cache locality. When you pre-fill the vector, all the memory is touched and initialized in one contiguous block. This lets the CPU's cache prefetchers do their job better, pulling in chunks of memory that will be used next. With push, even though the memory is allocated, you're writing to it one element at a time, which doesn't trigger the same efficient prefetching behavior.

Let's look at simplified code examples to make this tangible:

Approach 1: with_capacity + push #

let mut vec = Vec::with_capacity(10_000);
for i in 0..10_000 {
    vec.push(i);
}

Approach 2: Pre-filled Vec with replacement #

let mut vec = vec![0; 10_000];
for i in 0..10_000 {
    vec[i] = i;
}

In benchmarks, you'll consistently see the second approach outperform the first. The compiler can optimize the second loop much more aggressively—since it knows the vector's length is fixed at 10,000, it can unroll the loop more effectively, and the contiguous memory writes are far more efficient for the CPU's memory subsystem.

One last note: this is most impactful when your default value is cheap to create (like integers, booleans, or empty structs). The upfront cost of filling the vector with defaults is negligible compared to the gains from faster subsequent writes. If your default is expensive, you might need to weigh the tradeoffs, but for most puzzle-solving scenarios (where we're dealing with simple types), this is a no-brainer.

内容的提问来源于stack exchange，提问作者MutantOctopus