---
title: "Vec::push() dans une boucle vs. pré-allouer avec Vec::with_capacity() ?"
description: "Comparaison des performances de Vec::push() dans les boucles versus pré-allouer avec Vec::with_capacity(), analysant les coûts de réallocation mémoire et stratégies d'optimisation"
url: "https://mayorana.ch/fr/blog/vec-push-vs-with-capacity-performance"
language: "fr"
date: "2025-11-19"
author: "Mohamed Bennekrouf"
tags:
- "rust"
- "vec"
- "performance"
- "memory-allocation"
- "optimization"
- "collections"
en_version: "https://mayorana.ch/en/blog/vec-push-vs-with-capacity-performance.md"
---
# Vec::push() dans une boucle vs. pré-allouer avec Vec::with_capacity() ?
## Différences performance clés
| Vec::push() dans une Boucle | Vec::with_capacity() + push() |
|-----------------------------|---------------------------------|
| Réalloue la mémoire plusieurs fois (croissance exponentielle). | Alloue une fois en amont. |
| Complexité temporelle O(n log n) (amortie). | Complexité temporelle O(n). |
| Peut fragmenter la mémoire due aux allocations répétées. | Bloc mémoire contigu unique. |
## Pourquoi les réallocations Sont Coûteuses
### Stratégie de croissance
- Un Vec démarre avec une capacité 0 et double sa capacité quand plein (ex : 0 → 4 → 8 → 16...).
- Chaque réallocation implique :
- Allouer une nouvelle mémoire.
- Copier tous les éléments existants.
- Libérer l'ancienne mémoire.
### Exemple pour 10 éléments
- **push() avec Vec::new()** : 4 réallocations (capacité 0 → 4 → 8 → 16).
- **push() avec with_capacity(10)** : 0 réallocation.
## Comparaison Benchmark
```rust
use std::time::Instant;
fn main() {
// Test avec 1 million d'éléments
let n = 1_000_000;
// Méthode 1 : Pas de pré-allocation
let start = Instant::now();
let mut v1 = Vec::new();
for i in 0..n {
v1.push(i);
}
println!("Vec::new(): {:?}", start.elapsed());
// Méthode 2 : Pré-allouer
let start = Instant::now();
let mut v2 = Vec::with_capacity(n);
for i in 0..n {
v2.push(i);
}
println!("Vec::with_capacity(): {:?}", start.elapsed());
}
```
### Résultats typiques
```
Vec::new(): 1.8ms
Vec::with_capacity(): 0.4ms // 4.5x plus rapide
```
## Quand Pré-Allouer
- **Taille Connue** : Utilise with_capacity(n) si tu connais le nombre exact/maximum d'éléments.
- **Code Critique en Performance** : Évite les réallocations dans les boucles chaudes.
- **Grandes Données** : Prévient le stack overflow pour des collections énormes.
## Quand Vec::new() est Acceptable
- **Tailles Petites/Inconnues** : Pour usage ad-hoc ou vecteurs de courte durée.
- **Simplicité de Code** : Quand la performance n'est pas critique.
## Optimisations avancées et Patterns
### 1. Utilisation d'extend() pour les itérateurs
Si tu as un itérateur, `extend()` est souvent plus rapide qu'une boucle avec `push()` :
```rust
let mut v = Vec::with_capacity(n);
v.extend(0..n); // Optimisé pour les itérateurs (évite les vérifications de bounds)
// Comparaison performance
fn benchmark_extend_vs_push() {
let n = 1_000_000;
let data: Vec = (0..n).collect();
// Méthode push() en boucle
let start = std::time::Instant::now();
let mut v1 = Vec::with_capacity(n);
for item in &data {
v1.push(*item);
}
let push_time = start.elapsed();
// Méthode extend()
let start = std::time::Instant::now();
let mut v2 = Vec::with_capacity(n);
v2.extend(&data);
let extend_time = start.elapsed();
println!("Push loop: {:?}", push_time);
println!("Extend: {:?}", extend_time);
println!("Speedup: {:.2}x", push_time.as_nanos() as f64 / extend_time.as_nanos() as f64);
}
```
### 2. Techniques de Réservation dynamique
```rust
// Pattern pour croissance adaptative
struct AdaptiveVec {
inner: Vec,
growth_factor: f64,
}
impl AdaptiveVec {
fn new() -> Self {
Self {
inner: Vec::new(),
growth_factor: 1.5, // Croissance plus conservative que 2.0
}
}
fn with_initial_capacity(capacity: usize) -> Self {
Self {
inner: Vec::with_capacity(capacity),
growth_factor: 1.5,
}
}
fn smart_push(&mut self, item: T) {
if self.inner.len() == self.inner.capacity() {
let new_capacity = ((self.inner.capacity() as f64) * self.growth_factor) as usize;
self.inner.reserve(new_capacity.saturating_sub(self.inner.capacity()));
}
self.inner.push(item);
}
fn bulk_reserve(&mut self, additional: usize) {
// Réserve avec stratégie intelligente
let needed = self.inner.len() + additional;
if needed > self.inner.capacity() {
let optimal_size = needed.next_power_of_two();
self.inner.reserve(optimal_size - self.inner.len());
}
}
}
```
### 3. Optimisations spécialisées par domaine
```rust
// Pattern pour traitement par batches
fn process_data_batched(data: impl Iterator, batch_size: usize, mut processor: F) -> Vec
where
F: FnMut(T) -> T,
{
let mut result = Vec::new();
let mut batch = Vec::with_capacity(batch_size);
for item in data {
batch.push(processor(item));
if batch.len() == batch_size {
result.reserve(batch.len()); // Réserve exactement ce qui est nécessaire
result.extend(batch.drain(..));
}
}
// Traite le dernier batch
if !batch.is_empty() {
result.reserve(batch.len());
result.extend(batch);
}
result
}
// Optimisation pour construction conditionnelle
fn collect_conditionally(data: &[T], predicate: P) -> Vec
where
T: Clone,
P: Fn(&T) -> bool,
{
// Estimation heuristique de la capacité
let estimated_size = data.len() / 4; // Suppose 25% de sélection
let mut result = Vec::with_capacity(estimated_size);
for item in data {
if predicate(item) {
result.push(item.clone());
}
}
// Optimise la mémoire si surestimation importante
if result.capacity() > result.len() * 2 {
result.shrink_to_fit();
}
result
}
```
### 4. Benchmarking complet et Métriques
```rust
use criterion::{BenchmarkId, Criterion, Throughput, black_box};
fn comprehensive_vec_bench(c: &mut Criterion) {
let sizes = [100, 1_000, 10_000, 100_000, 1_000_000];
let mut group = c.benchmark_group("vec_allocation_strategies");
for size in sizes {
group.throughput(Throughput::Elements(size as u64));
// Benchmark Vec::new() + push
group.bench_with_input(
BenchmarkId::new("vec_new_push", size),
&size,
|b, &size| {
b.iter(|| {
let mut v = Vec::new();
for i in 0..size {
v.push(black_box(i));
}
black_box(v)
})
}
);
// Benchmark Vec::with_capacity + push
group.bench_with_input(
BenchmarkId::new("vec_with_capacity_push", size),
&size,
|b, &size| {
b.iter(|| {
let mut v = Vec::with_capacity(size);
for i in 0..size {
v.push(black_box(i));
}
black_box(v)
})
}
);
// Benchmark collect() depuis iterator
group.bench_with_input(
BenchmarkId::new("collect_from_iterator", size),
&size,
|b, &size| {
b.iter(|| {
let v: Vec = (0..size).map(|i| black_box(i)).collect();
black_box(v)
})
}
);
// Benchmark Vec::with_capacity + extend
group.bench_with_input(
BenchmarkId::new("vec_with_capacity_extend", size),
&size,
|b, &size| {
b.iter(|| {
let mut v = Vec::with_capacity(size);
v.extend((0..size).map(|i| black_box(i)));
black_box(v)
})
}
);
}
group.finish();
}
// Tests de validation
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_allocation_strategies_correctness() {
let n = 1000;
// Toutes les méthodes doivent produire le même résultat
let v1: Vec = {
let mut v = Vec::new();
for i in 0..n {
v.push(i);
}
v
};
let v2: Vec = {
let mut v = Vec::with_capacity(n);
for i in 0..n {
v.push(i);
}
v
};
let v3: Vec = (0..n).collect();
let v4: Vec = {
let mut v = Vec::with_capacity(n);
v.extend(0..n);
v
};
assert_eq!(v1, v2);
assert_eq!(v2, v3);
assert_eq!(v3, v4);
// Vérifications de capacité
assert!(v2.capacity() >= n);
assert!(v4.capacity() >= n);
}
#[test]
fn test_memory_efficiency() {
let n = 1000;
// Test avec pré-allocation exacte
let mut v_exact = Vec::with_capacity(n);
for i in 0..n {
v_exact.push(i);
}
assert_eq!(v_exact.capacity(), n);
// Test avec sur-allocation
let mut v_over = Vec::with_capacity(n * 2);
for i in 0..n {
v_over.push(i);
}
assert!(v_over.capacity() >= n * 2);
// Optimisation mémoire
v_over.shrink_to_fit();
assert!(v_over.capacity() >= n);
assert!(v_over.capacity() < n * 2);
}
}
```
### 5. Patterns d'Optimisation avancés
```rust
// Pool de Vec réutilisables pour éviter les allocations
pub struct VecPool {
pool: std::sync::Mutex>>,
default_capacity: usize,
}
impl VecPool {
pub fn new(default_capacity: usize) -> Self {
Self {
pool: std::sync::Mutex::new(Vec::new()),
default_capacity,
}
}
pub fn get(&self) -> PooledVec {
let mut pool = self.pool.lock().unwrap();
let mut vec = pool.pop().unwrap_or_else(|| Vec::with_capacity(self.default_capacity));
vec.clear(); // Assure que le Vec est vide
PooledVec {
vec: Some(vec),
pool: &self.pool,
}
}
}
pub struct PooledVec<'a, T> {
vec: Option>,
pool: &'a std::sync::Mutex>>,
}
impl std::ops::Deref for PooledVec<'_, T> {
type Target = Vec;
fn deref(&self) -> &Self::Target {
self.vec.as_ref().unwrap()
}
}
impl std::ops::DerefMut for PooledVec<'_, T> {
fn deref_mut(&mut self) -> &mut Self::Target {
self.vec.as_mut().unwrap()
}
}
impl Drop for PooledVec<'_, T> {
fn drop(&mut self) {
if let Some(vec) = self.vec.take() {
let mut pool = self.pool.lock().unwrap();
pool.push(vec);
}
}
}
// Utilisation du pool
fn use_vec_pool() {
let pool = VecPool::new(1000);
// Réutilise les Vec sans réallocation
for _ in 0..10 {
let mut pooled_vec = pool.get();
for i in 0..1000 {
pooled_vec.push(i);
}
// Vec automatiquement retourné au pool à la fin du scope
}
}
// Builder pattern pour construction efficace
pub struct VecBuilder {
vec: Vec,
sorted: bool,
deduplicated: bool,
}
impl VecBuilder {
pub fn new() -> Self {
Self {
vec: Vec::new(),
sorted: true,
deduplicated: true,
}
}
pub fn with_capacity(capacity: usize) -> Self {
Self {
vec: Vec::with_capacity(capacity),
sorted: true,
deduplicated: true,
}
}
pub fn push(mut self, item: T) -> Self {
self.vec.push(item);
self.sorted = false;
self.deduplicated = false;
self
}
pub fn extend_from_iter(mut self, iter: I) -> Self
where
I: IntoIterator,
{
self.vec.extend(iter);
self.sorted = false;
self.deduplicated = false;
self
}
pub fn sort(mut self) -> Self
where
T: Ord,
{
if !self.sorted {
self.vec.sort();
self.sorted = true;
}
self
}
pub fn dedup(mut self) -> Self
where
T: PartialEq,
{
if !self.deduplicated {
self.vec.dedup();
self.deduplicated = true;
}
self
}
pub fn build(self) -> Vec {
self.vec
}
}
```
## Analyse de performance détaillée
### Complexité Temporelle
```rust
// Analyse des coûts asymptotiques
fn analyze_complexity() {
println!("=== Analyse Complexité Temporelle ===");
// Vec::new() + push en boucle
// - Réallocations: log(n) fois
// - Copies totales: O(n) éléments copiés au total
// - Complexité: O(n) amortie, mais constante élevée
// Vec::with_capacity() + push en boucle
// - Réallocations: 0
// - Copies: 0
// - Complexité: O(n) strict
let sizes = [1000, 10000, 100000, 1000000];
for &size in &sizes {
// Mesure allocations
let start = std::time::Instant::now();
let mut v1 = Vec::new();
for i in 0..size {
v1.push(i);
}
let time_no_prealloc = start.elapsed();
let start = std::time::Instant::now();
let mut v2 = Vec::with_capacity(size);
for i in 0..size {
v2.push(i);
}
let time_prealloc = start.elapsed();
let speedup = time_no_prealloc.as_nanos() as f64 / time_prealloc.as_nanos() as f64;
println!("Size: {}, No prealloc: {:?}, Prealloc: {:?}, Speedup: {:.2}x",
size, time_no_prealloc, time_prealloc, speedup);
}
}
```
## Décider au point d'appel
### Matrice de décision
| Scénario | Recommandation | Justification |
|----------|----------------|---------------|
| **Taille connue à l'avance** | `Vec::with_capacity(n)` | Évite toutes les réallocations |
| **Taille approximativement connue** | `Vec::with_capacity(estimate)` | Réduit les réallocations |
| **Taille totalement inconnue** | `Vec::new()` puis `shrink_to_fit()` | Simplicité, optimise après |
| **Construction depuis itérateur** | `collect()` | Optimisé par le compilateur |
| **Ajouts par petits batches** | `reserve()` périodiquement | Équilibre performance/mémoire |
| **Très gros volumes** | Pool + réutilisation | Évite la fragmentation |
### Cas d'Usage spécialisés
```rust
// Parsing de fichiers - taille estimable
fn parse_file_lines(content: &str) -> Vec {
let estimated_lines = content.len() / 50; // 50 chars par ligne en moyenne
let mut lines = Vec::with_capacity(estimated_lines);
for line in content.lines() {
lines.push(line.to_string());
}
lines
}
// Stream processing - taille inconnue
fn process_stream(stream: impl Iterator) -> Vec {
let mut results = Vec::new();
let mut count = 0;
for item in stream {
results.push(item);
count += 1;
// Réserve proactivement pour éviter les réallocations fréquentes
if count > 0 && count.is_power_of_two() {
results.reserve(count);
}
}
results.shrink_to_fit(); // Optimise la mémoire finale
results
}
```
## Règles empiriques
**Utilise with_capacity() pour** :
- Nombres d'éléments prévisibles.
- Scénarios haute performance.
**Utilise Vec::new() pour** :
- Tailles petites/inconnues ou prototypage.
**Évite les réallocations inutiles**—elles dominent le runtime pour les gros Vecs.
**Techniques avancées** :
- `extend()` pour les itérateurs
- `reserve()` pour croissance par batches
- `shrink_to_fit()` pour optimiser la mémoire
- Pools pour réutilisation intensive
## Impact monde réel
Dans la crate regex, la [pré-allocation](https://mayorana.ch/fr/blog/vec-new-vs-with-capacity) est utilisée pour les groupes de capture pour éviter les réallocations pendant le pattern matching. Dans serde_json, les buffers de sérialisation sont pré-alloués basés sur la taille estimée du JSON de sortie.
Sur-réserver a un coût aussi. `with_capacity(1000)` pour dix éléments retient tout le bloc
jusqu'au drop du `Vec` ; `shrink_to_fit()` le rend, au prix d'une copie supplémentaire.