You can find the Chinese version at 為什麼你應該幫 Rust Vector 加上初始容量
Introduction
High-level programming languages usually offer growable arrays, like C++ and Rust's Vectors, Go's Slices, or JavaScript's Arrays. These can change in size and offer push and pop functions to add or remove elements. They're essentially enhanced arrays.
Since growable arrays in different languages work similarly, this discussion isn't limited to Rust Vectors. However, I'll use Rust Vectors as an example because I've been working with Rust recently. If you're not familiar with Rust, don't worry—just look at the example to see how Rust Vectors work.
fn main() {
let mut vec = vec![1, 2, 3]; // [1, 2, 3]
vec.push(4); // [1, 2, 3, 4]
vec.push(5); // [1, 2, 3, 4, 5]
vec.pop(); // [1, 2, 3, 4]
}
Why Vectors Can Grow
In lower-level languages like C, you must specify a length when allocating memory. Growable arrays like Vectors need to allocate extra space initially to allow for pushing new elements.
For example, if you have a Vector [1, 2, 3], it might allocate space for 6 integers. The first three slots hold [1, 2, 3].
When you run vec.push(4), it places 4 in the next slot without reallocating memory.
But if you keep pushing elements and exceed the initial capacity, Rust will allocate a new memory block twice the size and copy the existing elements over.
So, after vec.push(7), the Vector's capacity becomes 12, giving you 5 more empty slots. If you fill these up, Rust will double the capacity again and copy the numbers over.
Small Example: Double function
Now, consider this double function, which creates a new Vector where each value is double the original. For instance, [1, 2, 3] becomes [2, 4, 6].
fn main() {
let vec = vec![1, 2, 3];
let vec2 = double(&vec);
println!("{:?}", vec); // [1, 2, 3]
println!("{:?}", vec2); // [2, 4, 6]
}
The current implementation declares a new vec2 using Vec::new() and pushes each doubled value into vec2.
fn double(vec: &Vec<i32>) -> Vec<i32> {
let mut vec2 = Vec::new();
for x in vec.iter() {
vec2.push(x * 2);
}
return vec2;
}
What's the Problem?
As mentioned earlier, Vectors allocate extra space, but if it’s insufficient, they reallocate double the previous capacity and copy the data over.
If you double a Vector of 10,000 elements, you'll perform 10,000 pushes. If these pushes frequently exceed the capacity, the Vector will keep reallocating and copying, making the process time-consuming.
Improved double function
To avoid constant memory allocation and copying, Rust provides Vec::with_capacity(cap), allowing you to set an initial capacity. By reserving enough space at the start, you avoid moving contents around, improving efficiency.
fn double2(vec: &Vec<i32>) -> Vec<i32> {
let mut vec2 = Vec::with_capacity(vec.len());
for x in vec.iter() {
vec2.push(x * 2);
}
return vec2;
}
The second version is almost the same, except it replaces Vec::new() with Vec::with_capacity(vec.len()), setting the initial capacity to the original Vector's length. This ensures enough space, so you can push without worrying about exceeding capacity.
Performance Comparison
Theoretically, reserving capacity should make it faster, but how much faster? I ran both versions of "double" with a 100,000-element array 1,000 times to get an average.
The first version took about 273 ms, while the improved version took only 107 ms—about 2.5 times faster. This was compiled in release mode, so it’s close to real-world performance.
Conclusion
Now you know why setting an initial capacity for Rust Vectors is important. If you know the final number of elements, like in this example, using an initial capacity speeds up the push operations. If you can't know the exact number but have an estimate, setting an initial capacity can also reduce the number of reallocations.
Even if you don't use Rust, many languages have similar initialization methods, like Go's make([]T, len, cap) and Java's new ArrayList<T>(cap). The key is understanding how Vectors expand and knowing when to set an initial capacity.
Lastly, while setting an initial capacity speeds up push operations, the overall impact on your program might be small. For significant performance improvements, focus on the architecture, I/O model, algorithms, etc. Simply changing Vec::new() to Vec::with_capacity(cap) won’t suffice.