How does `smallvec::SmallVec::insert_many` optimize bulk insertion for inline storage?

smallvec::SmallVec::insert_many optimizes bulk insertion by efficiently handling the insertion of multiple elements at a specific position, leveraging SmallVec's inline storage to avoid heap allocations when the total capacity fits within the inline buffer. Unlike inserting elements one at a time, which may require multiple reallocations, insert_many calculates the final size upfront and performs a single capacity adjustment, then shifts existing elements and inserts the new elements in one operation. This approach minimizes memory operations and preserves the performance benefits of SmallVec's small-vector optimization.

SmallVec Basics and Inline Storage

use smallvec::SmallVec;
 
fn main() {
    // SmallVec stores elements inline until capacity is exceeded
    type SmallVec3 = SmallVec<[i32; 3]>;
    
    let mut v: SmallVec3 = SmallVec::new();
    
    // These fit inline (no heap allocation)
    v.push(1);
    v.push(2);
    v.push(3);
    
    println!("Inline: {:?}", v);
    println!("On heap: {}", v.spilled());
    
    // This spills to heap
    v.push(4);
    println!("After push 4: {:?}", v);
    println!("On heap: {}", v.spilled());
}

SmallVec uses inline storage for small arrays, spilling to the heap only when necessary.

Basic insert_many Usage

use smallvec::SmallVec;
 
fn main() {
    type SmallVec8 = SmallVec<[i32; 8]>;
    
    let mut v: SmallVec8 = SmallVec::from_slice(&[1, 2, 3, 7, 8, 9]);
    
    // Insert multiple elements at position 3
    v.insert_many(3, [4, 5, 6]);
    
    println!("After insert_many: {:?}", v);
    // [1, 2, 3, 4, 5, 6, 7, 8, 9]
}

insert_many inserts all elements from an iterator at the specified position.

Comparison with Sequential Insertion

use smallvec::SmallVec;
 
fn main() {
    type SmallVec8 = SmallVec<[i32; 8]>;
    
    // Method 1: Sequential insert (multiple operations)
    let mut v1: SmallVec8 = SmallVec::from_slice(&[1, 2, 3, 7, 8, 9]);
    for (i, val) in [4, 5, 6].into_iter().enumerate() {
        v1.insert(3 + i, val);
    }
    println!("Sequential: {:?}", v1);
    
    // Method 2: insert_many (single operation)
    let mut v2: SmallVec8 = SmallVec::from_slice(&[1, 2, 3, 7, 8, 9]);
    v2.insert_many(3, [4, 5, 6]);
    println!("insert_many: {:?}", v2);
    
    // insert_many is more efficient:
    // 1. Single capacity check/adjustment
    // 2. Single shift of existing elements
    // 3. Bulk copy of new elements
}

Sequential insertion requires multiple shifts and potential reallocations.

Capacity Optimization

use smallvec::SmallVec;
 
fn main() {
    type SmallVec8 = SmallVec<[i32; 8]>;
    
    // When elements fit inline
    let mut v1: SmallVec8 = SmallVec::from_slice(&[1, 2, 3]);
    println!("Before: len={}, capacity inline={}", v1.len(), !v1.spilled());
    
    // Insert within inline capacity
    v1.insert_many(1, [10, 20]);
    println!("After insert (still inline): len={}, spilled={}", v1.len(), v1.spilled());
    
    // When insertion exceeds inline capacity
    let mut v2: SmallVec8 = SmallVec::from_slice(&[1, 2, 3, 4, 5, 6]);
    v2.insert_many(3, [100, 200, 300]);
    println!("After exceeding capacity: spilled={}", v2.spilled());
}

insert_many allocates heap space only when the total size exceeds inline capacity.

Memory Layout During Insertion

use smallvec::SmallVec;
 
fn main() {
    type SmallVec4 = SmallVec<[i32; 4]>;
    
    let mut v: SmallVec4 = SmallVec::from_slice(&[1, 5]);
    println!("Initial: {:?}", v.as_slice());
    
    // Insert many at position 1
    // Steps:
    // 1. Calculate new length: 2 + 3 = 5 (exceeds inline capacity of 4)
    // 2. Allocate heap space if needed
    // 3. Shift elements after position 1: [5] -> [_, _, _, _, 5]
    // 4. Copy new elements: [2, 3, 4] at position 1
    
    v.insert_many(1, [2, 3, 4]);
    println!("After insert_many: {:?}", v.as_slice());
    
    // Single efficient operation instead of:
    // - shift, insert 2
    // - shift, insert 3  
    // - shift, insert 4
}

A single insertion operation avoids repeated element shifting.

Using Iterators with insert_many

use smallvec::SmallVec;
 
fn main() {
    type SmallVec8 = SmallVec<[i32; 8]>;
    
    let mut v: SmallVec8 = SmallVec::from_slice(&[10, 20, 30]);
    
    // From array
    v.insert_many(1, [15, 17]);
    println!("Array: {:?}", v);
    
    // From iterator
    v.insert_many(4, (25..=27));
    println!("Iterator: {:?}", v);
    
    // From Vec
    let extra = vec
![35, 36, 37];
    v.insert_many(7, extra);
    println!("From Vec: {:?}", v);
    
    // From filter
    v.insert_many(0, (100..110).filter(|x| x % 3 == 0));
    println!("From filter: {:?}", v);
}

Any IntoIterator source can be used with insert_many.

Performance Comparison

use smallvec::SmallVec;
use std::time::Instant;
 
fn main() {
    type SmallVec16 = SmallVec<[u64; 16]>;
    
    const SIZE: usize = 1000;
    const INSERT_SIZE: usize = 500;
    
    // Benchmark: sequential insert
    let start = Instant::now();
    let mut v1: SmallVec16 = SmallVec::with_capacity(SIZE);
    for i in 0..SIZE - INSERT_SIZE {
        v1.push(i as u64);
    }
    
    // Insert at middle, one by one
    for (offset, val) in (INSERT_SIZE..INSERT_SIZE + INSERT_SIZE).enumerate() {
        v1.insert(500 + offset, val as u64);
    }
    let sequential_time = start.elapsed();
    
    // Benchmark: insert_many
    let start = Instant::now();
    let mut v2: SmallVec16 = SmallVec::with_capacity(SIZE);
    for i in 0..SIZE - INSERT_SIZE {
        v2.push(i as u64);
    }
    
    // Insert all at once
    v2.insert_many(500, INSERT_SIZE..INSERT_SIZE + INSERT_SIZE);
    let insert_many_time = start.elapsed();
    
    println!("Sequential insert: {:?}", sequential_time);
    println!("insert_many: {:?}", insert_many_time);
}

insert_many is significantly faster for bulk insertions.

Element Shifting Optimization

use smallvec::SmallVec;
 
fn main() {
    type SmallVec8 = SmallVec<[i32; 8]>;
    
    // When inserting many elements, elements after the insert position
    // are shifted exactly once, not once per element
    
    let mut v: SmallVec8 = SmallVec::from_slice(&[1, 2, 3, 8, 9]);
    
    // Insert [4, 5, 6, 7] at position 3
    // Elements [8, 9] shift once, then [4, 5, 6, 7] are copied
    v.insert_many(3, [4, 5, 6, 7]);
    
    println!("Result: {:?}", v);
    
    // Contrast with individual inserts:
    // Each insert would shift [8, 9], then [8, 9, 7], then [8, 9, 7, 6]...
}

Single-shift optimization reduces memory operations significantly.

Spill Behavior Analysis

use smallvec::SmallVec;
 
fn main() {
    type SmallVec4 = SmallVec<[String; 4]>;
    
    let mut v: SmallVec4 = SmallVec::new();
    v.push("a".to_string());
    v.push("b".to_string());
    v.push("c".to_string());
    
    println!("Before insert: spilled={}", v.spilled());
    
    // Insert within inline capacity
    v.insert_many(1, ["x".to_string()]);
    println!("Within capacity: spilled={}", v.spilled());
    
    // Insert that causes spill
    v.insert_many(0, ["y".to_string(), "z".to_string()]);
    println!("After spill: spilled={}", v.spilled());
    println!("Contents: {:?}", v);
}

Spilling to heap happens automatically when inline capacity is exceeded.

Working with Different Types

use smallvec::SmallVec;
 
fn main() {
    // Strings
    type SmallStringVec = SmallVec<[String; 4]>;
    let mut strings: SmallStringVec = SmallVec::from_slice(&[
        "a".to_string(),
        "d".to_string(),
    ]);
    strings.insert_many(1, ["b".to_string(), "c".to_string()]);
    println!("Strings: {:?}", strings);
    
    // Structs
    #[derive(Debug, Clone)]
    struct Point { x: i32, y: i32 }
    
    type SmallPointVec = SmallVec<[Point; 8]>;
    let mut points: SmallPointVec = SmallVec::new();
    points.push(Point { x: 0, y: 0 });
    points.insert_many(1, [
        Point { x: 1, y: 1 },
        Point { x: 2, y: 2 },
    ]);
    println!("Points: {:?}", points);
    
    // Options
    type SmallOptVec = SmallVec<[Option<i32>; 8]>;
    let mut opts: SmallOptVec = SmallVec::from_slice(&[Some(1), None, Some(5)]);
    opts.insert_many(1, [Some(2), Some(3), Some(4)]);
    println!("Options: {:?}", opts);
}

insert_many works with any Clone type stored in SmallVec.

Avoiding Reallocation

use smallvec::SmallVec;
 
fn main() {
    type SmallVec8 = SmallVec<[i32; 8]>;
    
    // Without insert_many: potential multiple reallocations
    let mut v1: SmallVec8 = SmallVec::with_capacity(100);
    v1.extend(0..50);
    
    for (i, val) in (50..60).enumerate() {
        // Each insert may require shifting and possibly reallocation
        v1.insert(25 + i, val);
    }
    
    // With insert_many: single allocation and shift
    let mut v2: SmallVec8 = SmallVec::with_capacity(100);
    v2.extend(0..50);
    
    v2.insert_many(25, 50..60);
    
    println!("Results match: {:?}", v1 == v2);
}

Pre-allocating with with_capacity combined with insert_many is optimal.

Insert at Beginning

use smallvec::SmallVec;
 
fn main() {
    type SmallVec8 = SmallVec<[i32; 8]>;
    
    let mut v: SmallVec8 = SmallVec::from_slice(&[4, 5, 6]);
    
    // Insert at beginning (position 0)
    v.insert_many(0, [1, 2, 3]);
    
    println!("After prepend: {:?}", v);
    
    // Efficient prepend without multiple shifts
    // All original elements shift once, then new elements copy
}

Prepending with insert_many at position 0 is efficient for small collections.

Insert at End

use smallvec::SmallVec;
 
fn main() {
    type SmallVec8 = SmallVec<[i32; 8]>;
    
    let mut v: SmallVec8 = SmallVec::from_slice(&[1, 2, 3]);
    
    // Insert at end is equivalent to extend
    v.insert_many(3, [4, 5, 6]);
    
    println!("After append: {:?}", v);
    
    // insert_many at len() == extend behavior
    // No shifting required, just appending
}

Inserting at len() is equivalent to extend, with no element shifting.

Comparison with extend

use smallvec::SmallVec;
 
fn main() {
    type SmallVec8 = SmallVec<[i32; 8]>;
    
    let mut v1: SmallVec8 = SmallVec::from_slice(&[1, 2, 6, 7]);
    let mut v2: SmallVec8 = SmallVec::from_slice(&[1, 2, 6, 7]);
    
    // extend only appends at end
    v1.extend([3, 4, 5]);
    println!("extend (at end): {:?}", v1);
    
    // insert_many can insert anywhere
    v2.insert_many(2, [3, 4, 5]);
    println!("insert_many (at position): {:?}", v2);
    
    // For appending at end, both are efficient
    // extend is slightly more idiomatic for appending
}

Use extend for appending at the end; insert_many for inserting at any position.

Custom Inline Capacity

use smallvec::SmallVec;
 
fn main() {
    // Different inline capacities for different use cases
    
    // Small inline capacity (minimal stack usage)
    type Tiny = SmallVec<[u8; 2]>;
    let mut tiny: Tiny = SmallVec::new();
    tiny.insert_many(0, [1, 2]);  // Still inline
    println!("Tiny inline: {}", !tiny.spilled());
    tiny.insert_many(0, [3, 4]);  // Now spilled
    println!("Tiny spilled: {}", tiny.spilled());
    
    // Large inline capacity (more stack usage, fewer heap allocations)
    type Large = SmallVec<[u8; 64]>;
    let mut large: Large = SmallVec::new();
    for i in 0..60 {
        large.push(i);
    }
    large.insert_many(30, 100..120);  // Still inline
    println!("Large still inline: {}", !large.spilled());
}

Choose inline capacity based on typical data size to optimize heap allocation.

Drain and Insert Pattern

use smallvec::SmallVec;
 
fn main() {
    type SmallVec8 = SmallVec<[i32; 8]>;
    
    let mut v: SmallVec8 = SmallVec::from_slice(&[1, 2, 3, 100, 200, 300, 4, 5, 6]);
    
    // Remove elements and insert replacements
    let drained: SmallVec8 = v.drain(3..6).collect();
    println!("Drained: {:?}", drained);
    println!("After drain: {:?}", v);
    
    // Insert replacements
    v.insert_many(3, [10, 20, 30]);
    println!("After insert: {:?}", v);
    
    // This pattern allows in-place replacement of ranges
}

Combine drain and insert_many for in-place range replacement.

Empty Insertion

use smallvec::SmallVec;
 
fn main() {
    type SmallVec8 = SmallVec<[i32; 8]>;
    
    let mut v: SmallVec8 = SmallVec::from_slice(&[1, 2, 3]);
    
    // Inserting empty iterator is a no-op
    v.insert_many(1, std::iter::empty::<i32>());
    
    println!("After empty insert: {:?}", v);
    
    // This is safe and efficient - no allocation or shifting
}

Inserting an empty iterator is a no-op with no side effects.

Safety and Bounds Checking

use smallvec::SmallVec;
 
fn main() {
    type SmallVec8 = SmallVec<[i32; 8]>;
    
    let mut v: SmallVec8 = SmallVec::from_slice(&[1, 2, 3]);
    
    // Valid positions: 0, 1, 2, 3 (len is 3)
    v.insert_many(0, [10]);  // Beginning
    v.insert_many(4, [20]);  // End (position == len)
    
    println!("Valid inserts: {:?}", v);
    
    // Invalid position would panic
    // v.insert_many(100, [30]);  // panics: index out of bounds
    
    // insert_many panics if index > len
}

Insert position must be within 0..=len() or the method panics.

Synthesis

insert_many optimization benefits:

Benefit	Description
Single allocation	Capacity calculated once, not per-element
Single shift	Elements after insert position shift once
Bulk copy	New elements copied in one operation
Inline preservation	Uses inline storage when possible

Capacity handling:

Scenario	Behavior
Fits inline	No heap allocation
Exceeds inline	Single heap allocation
Already spilled	May reallocate if needed

Comparison with alternatives:

Method	Shifts	Allocations	Use Case
`insert` (loop)	Multiple	Multiple	Single element
`insert_many`	One	Zero/One	Multiple elements
`extend`	None	As needed	Append at end

Memory efficiency:

Inline Capacity	Stack Usage	Heap Usage	Best For
Small (e.g., 4)	Minimal	Earlier spill	Very small collections
Medium (e.g., 16)	Moderate	Later spill	Typical use cases
Large (e.g., 64)	Higher	Rare spill	Large collections

Key insight: SmallVec::insert_many optimizes bulk insertion by treating the operation as a single atomic action: it calculates the final size upfront, allocates heap space only if the total exceeds inline capacity, shifts existing elements exactly once (rather than once per inserted element), and copies all new elements in a single batch. For SmallVec specifically, this preserves the inline storage optimization when possible—inserting elements that keep the total within inline capacity avoids heap allocation entirely. The method accepts any IntoIterator, making it flexible for various input sources. Compared to sequential insert calls, insert_many can reduce O(n*m) shift operations to O(n), where n is the final length and m is the number of inserted elements. The optimal inline capacity choice depends on typical data sizes: capacity should match or exceed common collection sizes to maximize the benefit of inline storage while minimizing stack overhead.

How does smallvec::SmallVec::insert_many optimize bulk insertion for inline storage?