use smallvec::SmallVec;
 
fn basic_usage() {
    // SmallVec with inline capacity for 4 elements
    let mut vec: SmallVec<[i32; 4]> = SmallVec::new();
    
    // Elements stored inline (no heap allocation)
    vec.push(1);
    vec.push(2);
    vec.push(3);
    vec.push(4);
    
    // Still inline - capacity exactly met
    assert!(!vec.spilled());  // Has NOT spilled to heap
    
    // Adding 5th element causes heap allocation
    vec.push(5);
    assert!(vec.spilled());  // NOW spilled to heap
}

use smallvec::SmallVec;
 
fn capacity_parameter() {
    // The [T; N] parameter defines inline capacity
    // N = maximum elements stored inline
    
    type SmallVec4 = SmallVec<[i32; 4]>;   // 4 i32s inline
    type SmallVec8 = SmallVec<[i32; 8]>;   // 8 i32s inline
    type SmallVec16 = SmallVec<[i32; 16]>; // 16 i32s inline
    
    // Size of SmallVec on stack:
    // - Inline buffer: N * size_of::<T>()
    // - Length field: size_of::<usize>()
    // - Capacity/discriminant: size_of::<usize>()
    
    // SmallVec<[i32; 4]> stack size ≈ 4*4 + 8 + 8 = 32 bytes
    // SmallVec<[i32; 8]> stack size ≈ 8*4 + 8 + 8 = 48 bytes
    
    println!("SmallVec<[i32; 4]> size: {}", std::mem::size_of::<SmallVec<[i32; 4]>>());
    println!("SmallVec<[i32; 8]> size: {}", std::mem::size_of::<SmallVec<[i32; 8]>>());
}

use smallvec::SmallVec;
 
fn memory_layout() {
    // Before spilling (inline storage):
    // SmallVec contains:
    // - Inline buffer: [T; N] stored on stack
    // - Length: how many elements are in the buffer
    // - No heap pointer needed
    
    // After spilling (heap storage):
    // SmallVec contains:
    // - Heap pointer: pointer to allocated memory
    // - Capacity: allocated heap capacity
    // - Length: how many elements
    // - Inline buffer: unused (wasted stack space)
    
    let mut vec: SmallVec<[u64; 4]> = SmallVec::new();
    
    // Inline: buffer is part of SmallVec's memory
    vec.push(1);
    vec.push(2);
    
    // Spilled: buffer lives on heap
    vec.push(5); // Spills if capacity exceeded
    vec.push(6);
    
    // When spilled:
    // - Original inline capacity still reserved on stack (unused)
    // - Heap allocation holds all elements
    // - Total memory = stack inline buffer + heap allocation
}

use smallvec::SmallVec;
 
fn allocation_threshold() {
    // The inline capacity IS the allocation threshold
    // Elements <= capacity: inline, no allocation
    // Elements > capacity: heap allocation
    
    let mut vec: SmallVec<[String; 2]> = SmallVec::new();
    
    // 1 element: inline
    vec.push("first".to_string());
    // No heap allocation for SmallVec
    // String contents are on heap (String always allocates)
    
    // 2 elements: still inline
    vec.push("second".to_string());
    assert!(!vec.spilled());
    
    // 3 elements: spills to heap
    vec.push("third".to_string());
    assert!(vec.spilled());
    
    // The threshold is exactly the inline capacity
    // No "hysteresis" - threshold equals capacity
}

use smallvec::SmallVec;
 
fn stack_size_tradeoff() {
    // Larger inline capacity = larger stack size
    
    struct Config {
        // Different inline capacities for different sizes
        small_numbers: SmallVec<[i32; 2]>,   // ~24 bytes on stack
        medium_numbers: SmallVec<[i32; 8]>,  // ~48 bytes on stack  
        large_numbers: SmallVec<[i32; 32]>,  // ~144 bytes on stack
    }
    
    // If you embed SmallVec in many structs or use deeply nested calls:
    // - Large inline capacity increases stack usage significantly
    // - Could cause stack overflow in recursive functions
    
    // Example: recursive function with SmallVec
    fn recursive(depth: usize) {
        // Each recursive call allocates this on stack
        let vec: SmallVec<[u8; 1024]> = SmallVec::new();
        // 1024 bytes on stack per call!
        
        if depth > 0 {
            recursive(depth - 1);  // Stack overflow risk
        }
    }
    
    // Better: smaller inline capacity for recursive contexts
    fn recursive_better(depth: usize) {
        let vec: SmallVec<[u8; 16]> = SmallVec::new();  // Smaller
        // Only 16 bytes on stack per call
        
        if depth > 0 {
            recursive_better(depth - 1);
        }
    }
}

use smallvec::SmallVec;
 
fn cache_locality() {
    // Inline storage: excellent cache locality
    // SmallVec and its elements are contiguous in memory
    
    let mut vec: SmallVec<[i32; 16]> = SmallVec::new();
    for i in 0..16 {
        vec.push(i);
    }
    
    // Iterating inline storage:
    // - All elements in same cache line(s) as SmallVec
    // - No pointer chasing
    // - Excellent for small, frequently accessed collections
    
    let sum: i32 = vec.iter().sum();  // Cache-friendly iteration
    
    // Heap storage (after spill):
    // - SmallVec on stack, elements on heap
    // - At least one cache miss to reach elements
    // - Still better than Vec<Vec<T>> because contiguous
    
    vec.push(17);  // Spills
    // Now elements on heap, but still contiguous
}

use smallvec::SmallVec;
use std::time::Instant;
 
fn allocation_overhead() {
    // Allocation cost comparison
    
    let iterations = 100_000;
    
    // Vec: always allocates
    let start = Instant::now();
    for _ in 0..iterations {
        let mut v: Vec<i32> = Vec::with_capacity(4);
        v.push(1);
        v.push(2);
        v.push(3);
        v.push(4);
        // Heap allocation happened
    }
    let vec_time = start.elapsed();
    
    // SmallVec: no allocation for small collections
    let start = Instant::now();
    for _ in 0..iterations {
        let mut v: SmallVec<[i32; 4]> = SmallVec::new();
        v.push(1);
        v.push(2);
        v.push(3);
        v.push(4);
        // No heap allocation!
    }
    let smallvec_time = start.elapsed();
    
    // SmallVec is significantly faster when staying inline
    // The difference is allocation overhead
    println!("Vec: {:?}", vec_time);
    println!("SmallVec: {:?}", smallvec_time);
}

use smallvec::SmallVec;
 
fn choosing_capacity() {
    // Guidelines for choosing capacity:
    
    // 1. Common case fits inline
    // If 90% of cases use <= N elements, capacity N is good
    
    // Example: function arguments typically 0-4
    type Args = SmallVec<[String; 4]>;
    
    // Example: RGB colors always 3 elements
    type Rgb = SmallVec<[u8; 3]>;
    // Capacity 3: always inline, never spills
    
    // Example: small buffers for parsing
    type Buffer = SmallVec<[u8; 64]>;
    // Common case fits, large inputs spill
    
    // 2. Consider element size
    // Small elements (u8, i32): larger capacity is cheap
    // Large elements (String, Vec): smaller capacity to save stack
    
    type SmallInts = SmallVec<[i32; 32]>;  // 128 bytes inline
    type LargeStrings = SmallVec<[String; 4]>;  // Smaller inline
    
    // 3. Avoid excessive inline capacity
    // Rule of thumb: inline buffer <= 1KB
    
    type Okay = SmallVec<[u8; 1024]>;  // ~1KB on stack, okay
    type Risky = SmallVec<[u8; 65536]>; // 64KB on stack, risky
}

use smallvec::SmallVec;
 
fn different_types() {
    // Zero-sized types: inline storage is free
    let mut zst: SmallVec<[(); 1000]> = SmallVec::new();
    // No actual stack space used for the buffer!
    // Size of SmallVec<[(); 1000]> == size of SmallVec<[(); 0]>
    
    // Small types: large inline capacity is fine
    let mut small: SmallVec<[u8; 128]> = SmallVec::new();
    // 128 bytes on stack, reasonable
    
    // Large types: smaller inline capacity
    let mut large: SmallVec<[Box<[u8; 1024]>; 4]> = SmallVec::new();
    // Each Box is pointer-sized, so 4 pointers inline
    // But Box contents are on heap
    
    // Strings: capacity in count, not bytes
    let mut strings: SmallVec<[String; 4]> = SmallVec::new();
    // 4 String structs inline, String contents on heap
    // SmallVec<[_; 4]> is about 4 * 24 + 16 = 112 bytes on stack
    
    // Nested SmallVecs
    let mut nested: SmallVec<[SmallVec<[i32; 4]>; 4]> = SmallVec::new();
    // Stack space: outer SmallVec + inline capacity of nested SmallVecs
}

use smallvec::{smallvec, SmallVec};
 
fn smallvec_macro() {
    // Create SmallVec with inline capacity inferred from count
    
    // Inline capacity = number of elements
    let v: SmallVec<[i32; 3]> = smallvec
![1, 2, 3];
    // Always inline (3 elements, capacity 3)
    
    // Create with extra capacity
    let v: SmallVec<[i32; 8]> = smallvec
![1, 2, 3];
    // 3 elements, inline capacity 8
    
    // Create empty
    let v: SmallVec<[i32; 4]> = smallvec
![];
    // Empty, inline capacity 4
    
    // Note: if count > inline capacity, it spills
    // smallvec
![1, 2, 3, 4, 5] as SmallVec<[i32; 4]> would spill
    
    // Use with_capacity for explicit allocation
    let mut v: SmallVec<[i32; 4]> = SmallVec::with_capacity(10);
    // Inline capacity is 4, but heap allocated for 10
    // This bypasses inline storage!
    assert!(v.spilled());  // Already spilled with capacity > 4
}

use smallvec::SmallVec;
 
fn growth_after_spill() {
    let mut vec: SmallVec<[i32; 4]> = SmallVec::new();
    
    // Inline: capacity exactly 4
    for i in 0..4 {
        vec.push(i);
    }
    println!("Capacity: {}", vec.capacity());  // 4
    
    // Spill: capacity grows like Vec
    vec.push(4);
    println!("Capacity: {}", vec.capacity());  // Likely 8 (doubled)
    
    // Further growth follows Vec's growth strategy
    for i in 5..20 {
        vec.push(i);
    }
    println!("Capacity: {}", vec.capacity());  // 32 or similar
    
    // Once spilled, behavior is similar to Vec
    // The inline buffer is unused
}

use smallvec::SmallVec;
 
fn reserving_capacity() {
    let mut vec: SmallVec<[i32; 4]> = SmallVec::new();
    
    // Reserve within inline capacity
    vec.reserve(3);
    assert!(!vec.spilled());  // Still inline
    
    // Reserve exceeding inline capacity
    vec.reserve(10);
    assert!(vec.spilled());  // Now spilled
    
    // Reserve forces spill if needed
    // Even if you haven't pushed that many elements
    
    // Alternative: push within capacity
    let mut vec2: SmallVec<[i32; 4]> = SmallVec::new();
    vec2.push(1);
    vec2.push(2);
    vec2.push(3);
    vec2.push(4);
    assert!(!vec2.spilled());  // Still inline
    
    // reserve_exact for precise allocation
    let mut vec3: SmallVec<[i32; 4]> = SmallVec::new();
    vec3.reserve_exact(10);
    assert!(vec3.spilled());
    println!("Capacity: {}", vec3.capacity());  // Exactly 10
}

use smallvec::SmallVec;
 
fn shrinking() {
    let mut vec: SmallVec<[i32; 4]> = SmallVec::new();
    
    // Fill and spill
    for i in 0..100 {
        vec.push(i);
    }
    assert!(vec.spilled());
    println!("Capacity: {}", vec.capacity());  // ~128
    
    // Shrink to fit
    vec.shrink_to_fit();
    println!("Capacity: {}", vec.capacity());  // 100 (exact)
    assert!(vec.spilled());  // Still spilled (100 > 4)
    
    // Shrink to inline capacity
    vec.truncate(4);
    vec.shrink_to_fit();
    // Cannot un-spill!
    // Once spilled, SmallVec stays on heap
    // Inline buffer is never used again
    
    // shrink_to_fit() doesn't move back to inline
    assert!(vec.spilled());
}

use smallvec::SmallVec;
 
fn compare_strategies() {
    // Vec: always heap, minimal stack footprint
    struct VecUser {
        data: Vec<i32>,  // 24 bytes on stack (ptr + len + cap)
    }
    
    // SmallVec inline: potential stack growth
    struct SmallVecUser {
        data: SmallVec<[i32; 16]>,  // ~80 bytes on stack
    }
    
    // Array: fixed size, no growth
    struct ArrayUser {
        data: [i32; 16],  // 64 bytes on stack
    }
    
    // Trade-offs:
    //
    // Vec:
    // + Smallest stack footprint
    // + Unlimited growth
    // - Always allocates (even for 1 element)
    // - Pointer chasing for access
    
    // SmallVec:
    // + No allocation for small collections
    // + Good cache locality when inline
    // + Can grow larger than array
    // - Larger stack footprint
    // - Wasted stack space after spill
    
    // Array:
    // + No allocation
    // + Best cache locality
    // - Cannot grow
    // - Fixed size always on stack
}

use smallvec::SmallVec;
 
// Common use: function arguments
// Most functions have <= 4 arguments, but some have more
 
fn process_arguments(args: SmallVec<[String; 4]>) {
    // Common case: 1-4 arguments, inline
    // Rare case: 5+ arguments, spilled to heap
    
    for arg in args.iter() {
        println!("Arg: {}", arg);
    }
}
 
fn example_usage() {
    // Common case - inline
    let args: SmallVec<[String; 4]> = smallvec
![
        "arg1".to_string(),
        "arg2".to_string(),
        "arg3".to_string(),
    ];
    process_arguments(args);  // No heap allocation
    
    // Rare case - spilled
    let args: SmallVec<[String; 4]> = smallvec
![
        "arg1".to_string(),
        "arg2".to_string(),
        "arg3".to_string(),
        "arg4".to_string(),
        "arg5".to_string(),
    ];
    process_arguments(args);  // Spills to heap
}

use smallvec::SmallVec;
 
fn read_line() -> SmallVec<[u8; 64]> {
    // Common case: short lines fit inline
    // Rare case: long lines spill to heap
    
    let mut buffer: SmallVec<[u8; 64]> = SmallVec::new();
    // 64-byte inline buffer for typical lines
    
    // Read data (simplified)
    for byte in b"hello world" {
        buffer.push(*byte);
    }
    
    // Most lines < 64 bytes, so usually no allocation
    buffer
}
 
fn parse_tokens(input: &str) -> SmallVec<[&str; 8]> {
    // Common case: <= 8 tokens, inline
    // Many inputs have only a few tokens
    
    let mut tokens: SmallVec<[&str; 8]> = SmallVec::new();
    for token in input.split_whitespace() {
        tokens.push(token);
    }
    tokens
}

use smallvec::SmallVec;
use std::mem::size_of;
 
fn memory_overhead() {
    // Before spill (inline):
    // Total = stack size of SmallVec
    // = inline_buffer + length_field + discriminant
    
    // SmallVec<[u8; 64]> inline:
    // = 64 bytes buffer + ~16 bytes overhead = ~80 bytes on stack
    // 0 bytes on heap
    
    // After spill (heap):
    // Total = stack size + heap size
    // = ~80 bytes stack + N * size_of::<T>() bytes heap
    
    // SmallVec<[u8; 64]> with 100 elements:
    // = ~80 bytes stack (wasted inline buffer!)
    // + 100 bytes heap
    // = 180 bytes total
    
    // Compare with Vec<u8>:
    // = 24 bytes stack + 100 bytes heap = 124 bytes
    
    // SmallVec has MORE memory overhead when spilled!
    // Because inline buffer is allocated but unused
    
    println!("SmallVec<[u8; 64]> size: {}", size_of::<SmallVec<[u8; 64]>>());
    println!("Vec<u8> size: {}", size_of::<Vec<u8>>());
}

use smallvec::SmallVec;
 
fn when_it_helps() {
    // SmallVec HELPS when:
    // 1. Most collections stay within inline capacity
    // 2. Allocation overhead is significant
    // 3. Frequent creation/destruction of small collections
    
    // Example: parsing tokens in a loop
    fn parse_many() {
        for _ in 0..1000000 {
            // Each iteration creates a small collection
            let tokens: SmallVec<[&str; 4]> = smallvec
!["a", "b", "c"];
            // No allocation per iteration!
        }
    }
    
    // SmallVec HURTS when:
    // 1. Collections frequently exceed inline capacity
    // 2. Stack space is limited (recursion)
    // 3. Inline capacity is too large
    
    // Example: large collections
    fn process_large() {
        let mut data: SmallVec<[u8; 64]> = SmallVec::new();
        for _ in 0..10000 {
            data.push(0);  // Spills early, wasted inline buffer
        }
        // Vec would be better here
    }
}

use smallvec::SmallVec;
 
fn dynamic_capacity() {
    // SmallVec's capacity is compile-time fixed
    
    // If you need runtime-determined inline capacity:
    // Use SmallVec with largest expected size, or
    // use a different crate
    
    // Alternative pattern: generic capacity
    fn with_capacity<const N: usize>(items: usize) -> SmallVec<[u8; N]> {
        let mut vec: SmallVec<[u8; N]> = SmallVec::new();
        for i in 0..items.min(N) {
            vec.push(i as u8);
        }
        vec
    }
    
    // The capacity N must be known at compile time
    // Cannot change N based on runtime input
}

use smallvec::SmallVec;
 
// Inline capacity determines:
// 1. Stack memory consumption (always)
// 2. Maximum elements before heap allocation
// 3. Cache locality benefits (when inline)
 
// Higher inline capacity:
// + More elements stored inline
// + Fewer heap allocations
// - More stack memory used
// - Wasted memory when spilled
 
// Lower inline capacity:
// + Less stack memory used
// + Less wasted memory after spill
// - More frequent heap allocations
// - Less cache locality benefit

// Before spill:
// Stack: inline_buffer + overhead
// Heap: 0
 
// After spill:
// Stack: inline_buffer + overhead (buffer unused!)
// Heap: element_capacity * element_size
 
// Vec for comparison:
// Stack: pointer + length + capacity = ~24 bytes
// Heap: element_capacity * element_size
 
// SmallVec has HIGHER memory when spilled
// But LOWER or ZERO memory when inline

// Inline (elements <= capacity):
// + Zero allocation overhead
// + Excellent cache locality
// + Contiguous memory access
// + Ideal for small, hot collections
 
// Spilled (elements > capacity):
// + Still contiguous on heap
// - Allocation overhead (once)
// - Wasted stack memory
// - Similar to Vec after spill
 
// Key: most common case should fit inline

use smallvec::SmallVec;
 
// 1. Analyze your data distribution
//    - What's the 90th percentile size?
//    - What's the maximum size?
 
// 2. Capacity = 90th percentile (or slightly higher)
//    - Covers most cases inline
//    - Rare cases spill to heap
 
// 3. Consider element size
//    - Small elements (u8, i32): capacity can be large
//    - Large elements (String, structs): keep capacity small
 
// 4. Consider stack constraints
//    - Recursive functions: small capacity
//    - Embedded in many structs: smaller capacity
 
// 5. Profile and measure
//    - Compare allocation counts with Vec
//    - Check if common case stays inline