Rust and Data Structures

Performance and Memory Trade-Offs

Designing systems software regularly involves trading memory footprint for lookup speed (caching, precomputed lookup tables, hash indexes) or trading slight CPU compute for drastically smaller memory footprint (bit-packing, string interning, compact integer IDs)—which in turn often makes the program faster overall because the working set fits inside the CPU's L2/L3 cache!

The Memory-Compute Feedback Loop on Modern CPUs:

  Naive Uncompressed Representation (e.g., 64-byte structs + duplicated `String`s)
       |
       +--> Exceeds 16 MiB L3 Cache ---> Every random lookup stalls ~80ns on DRAM!

  Compact Representation (e.g., 8-byte interned `SymbolId(u32)` + bit-packed flags)
       |
       +--> Entire working set fits in L2/L3 Cache ---> Lookups finish in ~3-10ns!

Classic Space-Time Trade-Off Techniques in Rust

Technique What You Trade Benefit Gained
String Interning Small once-per-unique-string dictionary Replaces 24-byte heap Strings + $O(n)$ string comparisons with a 4-byte SymbolId(u32) that compares and hashes in $O(1)$ (1 CPU cycle)!
Precomputed Lookup Tables (const) 256B – 64 KiB of .rodata memory Replaces multi-branch loops (CRC32, hex/base64 decoding, character classes) with an $O(1)$ array index.
Box<[T]> / Arc<str> over Vec<T> / String Gives up in-place .push() capacity growth Saves 8 bytes per instance (16B instead of 24B) and eliminates up to 50% unused geometric spare capacity!
Probabilistic Filters (Bloom Filter) Small fixed bit-array (~10 bits per key) + ~1% false-positive rate Eliminates 99% of expensive disk reads or network queries for non-existent keys in $O(1)$ time!

Implementing a Zero-Allocation-per-Duplicate String Interner

In compilers, log analyzers, and JSON/CSV processors, millions of records repeat the same few hundred field names or status strings ("USD", "ACTIVE", "GET"). A String Interner stores each unique string once and hands out a 4-byte Copy Symbol(u32):

use std::collections::HashMap;

/// A 4-byte `Copy` handle representing an interned string.
/// Comparing two `Symbol`s (`a == b`) is a single 32-bit integer comparison!
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Symbol(u32);

#[derive(Default)]
pub struct StringInterner {
    map: HashMap<Box<str>, Symbol>,
    strings: Vec<Box<str>>,
}

impl StringInterner {
    pub fn new() -> Self {
        Self::default()
    }

    /// Returns the existing `Symbol` if `text` was already interned (with 0 allocations!),
    /// or allocates `text` once and assigns the next `Symbol`.
    pub fn intern(&mut self, text: &str) -> Symbol {
        if let Some(&sym) = self.map.get(text) {
            return sym;
        }

        let sym = Symbol(self.strings.len() as u32);
        let boxed: Box<str> = text.into();
        self.strings.push(boxed.clone());
        self.map.insert(boxed, sym);
        sym
    }

    pub fn resolve(&self, sym: Symbol) -> Option<&str> {
        self.strings.get(sym.0 as usize).map(Box::as_ref)
    }

    pub fn unique_count(&self) -> usize {
        self.strings.len()
    }
}

fn main() {
    let mut interner = StringInterner::new();

    let s1 = interner.intern("application/json");
    let s2 = interner.intern("text/plain");
    let s3 = interner.intern("application/json"); // Duplicate: 0 new strings added!

    // O(1) integer equality check instead of byte-by-byte string comparison:
    assert_eq!(s1, s3);
    assert_ne!(s1, s2);
    assert_eq!(interner.unique_count(), 2);

    println!(
        "Interned 3 strings into {} unique symbols; s1 == s3: {}, resolved s1: {:?}",
        interner.unique_count(),
        s1 == s3,
        interner.resolve(s1)
    );
}

Interned 3 strings into 2 unique symbols; s1 == s3: true, resolved s1: Some("application/json")

Shrinking Excess Capacity on Long-Lived Collections (shrink_to_fit)

While geometric capacity doubling ($2\times$) makes Vec::push and HashMap::insert fast during construction, a Vec that grew to 1,025 elements has an allocated capacity of 2,048 elements—leaving nearly 50% of its heap allocation unused forever if the vector is never mutated again.

For long-lived, read-only collections retained in memory for the lifetime of a server, call vec.shrink_to_fit() (or convert into vec.into_boxed_slice()) once construction finishes to return the unused tail capacity to the allocator.