smallvec

The `smallvec` crate in Rust provides a `SmallVec<A: Array>` type, which is a vector optimized for cases where the collection is typically small. Its primary goal is to avoid heap allocations for small collections by storing elements directly on the stack (inline) up to a fixed capacity. Only if the collection grows beyond this inline capacity does it allocate memory on the heap, similar to a standard `Vec<T>`.

How it works:
1. Inline Storage: You define the maximum number of elements `N` that can be stored on the stack. The `SmallVec` internally holds an array of `N` elements (e.g., `[T; N]`) along with its current length and a discriminant (to track if it's currently using stack or heap storage).
2. Heap Spill: If you attempt to add an element that would exceed the inline capacity `N`, `SmallVec` automatically allocates a new `Vec<T>` on the heap, copies all existing elements from the stack to the heap, and then inserts the new element into the heap-allocated vector. All subsequent operations will then use the heap storage.
3. `Vec`-like API: `SmallVec` implements many of the same traits and methods as `Vec<T>`, such as `Deref` and `DerefMut` to `[T]`, `IntoIterator`, `Extend`, `Push`, `Pop`, `get`, `index`, etc., making it largely a drop-in replacement in many scenarios.

Benefits:
* Performance: For small collections, it completely bypasses the overhead of heap allocation, deallocation, and potential memory fragmentation. This leads to faster operations and better cache locality.
* Reduced Allocations: Minimizes calls to the system allocator, which can be a bottleneck in performance-critical code.
* Predictable Memory Use (for small sizes): For collections within the inline capacity, memory usage is purely stack-based, which is generally faster and more predictable.

When to use it:
Use `smallvec` when you have a collection that:
* Is *usually* small (e.g., 0-5 elements).
* *Occasionally* might grow larger.
* Is performance-critical, and you want to avoid heap allocations for the common small case.

Examples: Function argument lists, temporary buffers, short lists of items in an algorithm, processing pipeline stages where intermediate results are often small. It's particularly useful in hot loops or embedded systems where heap allocations are expensive or undesirable.

Example Code

```rust
// Cargo.toml
// [dependencies]
// smallvec = "1.11.0"

use smallvec::{smallvec, SmallVec};

fn process_numbers(numbers: SmallVec<[i32; 4]>) -> SmallVec<[i32; 4]> {
    println!("Processing {:?} (capacity on stack: 4)", numbers);
    let mut result = SmallVec::<[i32; 4]>::new();
    for &num in numbers.iter() {
        result.push(num * 2);
    }
    result
}

fn main() {
    // --- Case 1: Stays on the stack ---
    println!("\n--- Case 1: Small collection ---");
    let mut sv1: SmallVec<[i32; 4]> = smallvec![10, 20]; // Uses stack capacity
    println!("sv1 initial: {:?}, len: {}, cap: {}", sv1, sv1.len(), sv1.capacity());
    // Add more elements, still fits on stack
    sv1.push(30);
    println!("sv1 after push: {:?}, len: {}, cap: {}", sv1, sv1.len(), sv1.capacity());

    let processed1 = process_numbers(sv1);
    println!("Processed 1 result: {:?}, len: {}, cap: {}", processed1, processed1.len(), processed1.capacity());

    // --- Case 2: Spills to the heap ---
    println!("\n--- Case 2: Exceeds inline capacity ---");
    let mut sv2: SmallVec<[i32; 4]> = smallvec![1, 2, 3, 4]; // Fills stack capacity
    println!("sv2 initial: {:?}, len: {}, cap: {}", sv2, sv2.len(), sv2.capacity());
    // Pushing the 5th element will cause a heap allocation
    sv2.push(5);
    println!("sv2 after push (spill): {:?}, len: {}, cap: {}", sv2, sv2.len(), sv2.capacity());
    // Note: capacity might be larger now, as Vec usually over-allocates

    let processed2 = process_numbers(sv2);
    println!("Processed 2 result: {:?}, len: {}, cap: {}", processed2, processed2.len(), processed2.capacity());

    // --- Case 3: Empty SmallVec ---
    println!("\n--- Case 3: Empty SmallVec ---");
    let mut sv3: SmallVec<[u8; 8]> = SmallVec::new(); // Starts empty, on stack
    println!("sv3 initial: {:?}, len: {}, cap: {}", sv3, sv3.len(), sv3.capacity());
    sv3.extend_from_slice(&[100, 101, 102, 103, 104, 105, 106, 107]); // Still on stack
    println!("sv3 extended: {:?}, len: {}, cap: {}", sv3, sv3.len(), sv3.capacity());
    sv3.push(108); // Spills to heap
    println!("sv3 after push (spill): {:?}, len: {}, cap: {}", sv3, sv3.len(), sv3.capacity());

    // SmallVec can be used like a normal Vec in most contexts
    println!("\n--- Vec-like operations ---");
    let mut items: SmallVec<[String; 2]> = smallvec!["apple".to_string(), "banana".to_string()];
    items.push("cherry".to_string()); // Spills to heap
    for item in &items {
        println!("Item: {}", item);
    }
    items.remove(0);
    println!("After remove: {:?}", items);
}
```

Example Code

Related Topics