Extreme Software Optimization

Extreme Software Optimization

The One Rule: Profile first. Prove behavior unchanged. One change at a time.

The Loop (Mandatory)

1. BASELINE    → hyperfine --warmup 3 --runs 10 'command'
2. PROFILE     → cargo flamegraph / py-spy / clinic flame
3. PROVE       → Golden outputs + isomorphism proof per change
4. IMPLEMENT   → Score ≥ 2.0 only, one lever per commit
5. VERIFY      → sha256sum -c golden_checksums.txt
6. REPEAT      → Re-profile (bottlenecks shift)

Opportunity Matrix

Rule: Only implement Score ≥ 2.0

Isomorphism Proof Template

For EVERY change, document:

## Change: [description]
- Ordering preserved:     [yes/no + why]
- Tie-breaking unchanged: [yes/no + why]
- Floating-point:         [identical/N/A]
- RNG seeds:              [unchanged/N/A]
- Golden outputs:         sha256sum -c golden_checksums.txt ✓

---

Pattern Tiers (Quick Reference)

Tier 1: Low-Hanging Fruit

Tier 2: Algorithmic

Tier 3: Data Structures

Full catalog: TECHNIQUES.md

---

Language Cheatsheet

Full language guides: LANGUAGE-SPECIFIC.md

---

Anti-Patterns (Never Do)

---

Checklist (Before Any Optimization)

• [ ] Baseline captured (p50/p95/p99, throughput, memory)
• [ ] Profiled: hotspot in top 5 by % time
• [ ] Opportunity score ≥ 2.0
• [ ] Golden outputs saved
• [ ] Isomorphism proof written
• [ ] Single lever only
• [ ] Rollback plan: git revert <sha>

---

Tool Commands

# Benchmark
hyperfine --warmup 3 --runs 10 'command'

# Profile
cargo flamegraph                           # Rust CPU
heaptrack ./binary                         # Allocation
strace -c ./binary                         # Syscalls

# Verify
sha256sum golden_outputs/* > golden_checksums.txt
sha256sum -c golden_checksums.txt          # After changes

---

References

Iteration Rounds

• Round 1: Standard (N+1, indexes, batching, memoization)
• Round 2: Algorithmic (DP, convex, semirings) → ADVANCED.md
• Round 3: Exotic (suffix automata, link-cut trees)

Each round: fresh profile → new hotspots → new matrix.

Advanced Optimization Techniques

Round 2+ patterns for when standard techniques are exhausted.

Contents

1. Mathematical Recastings 2. Advanced DP 3. Exotic Data Structures 4. Streaming/Sublinear 5. Algebraic Techniques 6. Graph Optimizations 7. Cache-Oblivious Design 8. Randomized Algorithms 9. Quick Reference

---

Mathematical Recastings

Convex Optimization

When: Brute-forcing allocation/scheduling/fitting

use minilp::{Problem, OptimizationDirection, ComparisonOp};

let mut problem = Problem::new(OptimizationDirection::Minimize);
let vars: Vec<_> = costs.iter().map(|&c| problem.add_var(c, (0.0, f64::INFINITY))).collect();
for (row, &limit) in constraints.iter().zip(limits.iter()) {
    problem.add_constraint(row.iter().zip(&vars).map(|(&a, &v)| (v, a)), ComparisonOp::Le, limit);
}
let solution = problem.solve().unwrap();

Libraries: minilp, good_lp, osqp

Submodular Greedy

When: Diminishing returns set function (f(A∪{x})-f(A) ≥ f(B∪{x})-f(B) when A⊆B)

fn greedy_submodular<F>(n: usize, k: usize, f: F) -> Vec<usize>
where F: Fn(&[usize]) -> f64 {
    let mut selected = Vec::with_capacity(k);
    let mut remaining: Vec<_> = (0..n).collect();
    for _ in 0..k {
        let (best_idx, _) = remaining.iter().enumerate()
            .map(|(i, &e)| { let mut c = selected.clone(); c.push(e); (i, f(&c) - f(&selected)) })
            .max_by(|a, b| a.1.partial_cmp(&b.1).unwrap()).unwrap();
        selected.push(remaining.remove(best_idx));
    }
    selected
}

Guarantee: 63% of optimal for monotone submodular

Semiring Generalization

When: Path computations (shortest path, transitive closure, dataflow)

trait Semiring {
    fn zero() -> Self;
    fn one() -> Self;
    fn add(&self, other: &Self) -> Self;  // ⊕
    fn mul(&self, other: &Self) -> Self;  // ⊗
}

// Tropical (shortest paths)
impl Semiring for MinPlus {
    fn zero() -> Self { MinPlus(f64::INFINITY) }
    fn one() -> Self { MinPlus(0.0) }
    fn add(&self, other: &Self) -> Self { MinPlus(self.0.min(other.0)) }
    fn mul(&self, other: &Self) -> Self { MinPlus(self.0 + other.0) }
}

// Boolean (transitive closure)
impl Semiring for bool {
    fn zero() -> Self { false }
    fn one() -> Self { true }
    fn add(&self, other: &Self) -> Self { *self || *other }
    fn mul(&self, other: &Self) -> Self { *self && *other }
}

Matroid Recognition

When: Greedy is provably optimal

Recognition: Independent sets satisfy hereditary property + exchange property

Examples:

• Graphic matroids (spanning trees)
• Partition matroids (select k from each category)
• Linear matroids (linearly independent vectors)

fn greedy_matroid<I: Matroid>(elements: &[Element], matroid: &I) -> Vec<Element> {
    let mut result = Vec::new();
    let mut sorted: Vec<_> = elements.iter().collect();
    sorted.sort_by(|a, b| b.weight.cmp(&a.weight));  // Descending
    for elem in sorted {
        if matroid.is_independent(&result, elem) {
            result.push(elem.clone());
        }
    }
    result
}

Min-Cost Max-Flow

When: Assignment, scheduling, resource allocation

// Model as graph:
// Source → workers (cap 1, cost 0)
// Workers → tasks (cap 1, cost = -preference)
// Tasks → sink (cap 1, cost 0)
use pathfinding::prelude::*;
let (flow, cost, paths) = edmonds_karp(&graph, source, sink);

Libraries: pathfinding, petgraph

2-SAT Reduction

When: Configuration validity, implication graphs, pairwise boolean constraints

// (x ∨ y) becomes (¬x → y) ∧ (¬y → x)
fn solve_2sat(clauses: &[(Lit, Lit)]) -> Option<Vec<bool>> {
    let n = /* number of variables */;
    let mut graph = ImplicationGraph::new(n);

    for &(a, b) in clauses {
        graph.add_implication(!a, b);
        graph.add_implication(!b, a);
    }

    let sccs = kosaraju(&graph);

    // Check: x and ¬x in same SCC = UNSAT
    for var in 0..n {
        if sccs[var] == sccs[var + n] { return None; }
    }

    // Assign: choose literal whose SCC comes later in reverse topo order
    Some((0..n).map(|var| sccs[var] > sccs[var + n]).collect())
}

---

Advanced DP

DP as Shortest Path in Implicit DAG

When: DP with DAG structure, non-uniform transition costs

fn dp_dijkstra(start: State, goal: State) -> Cost {
    let mut dist = HashMap::new();
    let mut heap = BinaryHeap::new();
    dist.insert(start, 0);
    heap.push(Reverse((0, start)));

    while let Some(Reverse((d, state))) = heap.pop() {
        if state == goal { return d; }
        if d > *dist.get(&state).unwrap_or(&Cost::MAX) { continue; }

        for (next_state, cost) in transitions(&state) {
            let new_dist = d + cost;
            if new_dist < *dist.get(&next_state).unwrap_or(&Cost::MAX) {
                dist.insert(next_state, new_dist);
                heap.push(Reverse((new_dist, next_state)));
            }
        }
    }
    Cost::MAX
}

Convex Hull Trick

When: DP recurrence dp[i] = min(m[j]·x[i] + c[j]) — O(n²) → O(n log n)

struct CHT { lines: VecDeque<(i64, i64)> }
impl CHT {
    fn add_line(&mut self, m: i64, c: i64) {
        while self.lines.len() >= 2 {
            let (m1, c1) = self.lines[self.lines.len() - 2];
            let (m2, c2) = self.lines[self.lines.len() - 1];
            if (c - c2) * (m1 - m2) <= (c2 - c1) * (m - m2) { self.lines.pop_back(); }
            else { break; }
        }
        self.lines.push_back((m, c));
    }
    fn query(&mut self, x: i64) -> i64 {
        while self.lines.len() >= 2 {
            let (m1, c1) = self.lines[0];
            let (m2, c2) = self.lines[1];
            if m1 * x + c1 >= m2 * x + c2 { self.lines.pop_front(); }
            else { break; }
        }
        let (m, c) = self.lines[0];
        m * x + c
    }
}

Knuth's Optimization

When: dp[i][j] = min(dp[i][k] + dp[k][j] + cost[i][j]), optimal split monotonic — O(n³) → O(n²)

Condition: cost satisfies quadrangle inequality, opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]

fn knuth_optimization(n: usize, cost: &[Vec<i64>]) -> Vec<Vec<i64>> {
    let mut dp = vec![vec![0; n]; n];
    let mut opt = vec![vec![0; n]; n];

    for i in 0..n { opt[i][i] = i; }

    for len in 2..=n {
        for i in 0..=n-len {
            let j = i + len - 1;
            dp[i][j] = i64::MAX;
            let lo = opt[i][j-1];
            let hi = if j + 1 < n { opt[i+1][j] } else { j };

            for k in lo..=hi.min(j) {
                let candidate = dp[i][k] + dp[k+1][j] + cost[i][j];
                if candidate < dp[i][j] {
                    dp[i][j] = candidate;
                    opt[i][j] = k;
                }
            }
        }
    }
    dp
}

Divide & Conquer DP

When: Similar conditions, 1D DP — O(n²) → O(n log n)

fn dc_dp(dp: &mut [i64], prev: &[i64], cost: impl Fn(usize, usize) -> i64,
         lo: usize, hi: usize, opt_lo: usize, opt_hi: usize) {
    if lo > hi { return; }
    let mid = (lo + hi) / 2;
    let mut best = (i64::MAX, opt_lo);

    for k in opt_lo..=opt_hi.min(mid) {
        let candidate = prev[k] + cost(k, mid);
        if candidate < best.0 { best = (candidate, k); }
    }

    dp[mid] = best.0;
    dc_dp(dp, prev, &cost, lo, mid.saturating_sub(1), opt_lo, best.1);
    dc_dp(dp, prev, &cost, mid + 1, hi, best.1, opt_hi);
}

---

Exotic Data Structures

Suffix Array + LCP

When: Substring queries, longest common substring, pattern matching

use suffix_array::SuffixArray;
let sa = SuffixArray::new(text);
let lcp = sa.lcp_array();
let range = sa.search(pattern);  // O(m log n)

Libraries: suffix_array, cdivsufsort

Wavelet Trees

When: Rank, select, quantile queries on sequences — O(log σ)

// Operations:
// rank(c, i): count of c in prefix [0, i)
// select(c, k): position of k-th occurrence of c
// quantile(l, r, k): k-th smallest in range [l, r)

Libraries: wavelet-matrix

Link-Cut Trees

When: Dynamic tree connectivity, path queries on changing trees — O(log n)

// Operations:
// link(u, v): Add edge
// cut(u, v): Remove edge
// path_query(u, v): Aggregate on u-v path
// find_root(u): Find tree root

Libraries: link_cut_tree crate or implement from scratch

Heavy-Light Decomposition

When: Path queries on static trees — O(log² n) per query

struct HLD {
    parent: Vec<usize>,
    depth: Vec<usize>,
    heavy: Vec<Option<usize>>,
    head: Vec<usize>,
    pos: Vec<usize>,
}
// Decompose tree into heavy chains
// Path query = O(log n) chains × O(log n) segment tree

Monotone Deque

When: Sliding window min/max — O(1) amortized

struct MonotoneDeque { deque: VecDeque<(i64, usize)> }
impl MonotoneDeque {
    fn push(&mut self, val: i64, idx: usize) {
        while self.deque.back().map_or(false, |&(v, _)| v >= val) { self.deque.pop_back(); }
        self.deque.push_back((val, idx));
    }
    fn pop_expired(&mut self, min_idx: usize) {
        while self.deque.front().map_or(false, |&(_, i)| i < min_idx) { self.deque.pop_front(); }
    }
    fn min(&self) -> Option<i64> { self.deque.front().map(|&(v, _)| v) }
}

Segment Tree + Lazy Propagation

When: Range updates + range queries

struct LazySegTree<T, L> {
    tree: Vec<T>,
    lazy: Vec<L>,
}

impl<T, L> LazySegTree<T, L> {
    fn push_down(&mut self, node: usize) {
        // Propagate lazy value to children
    }

    fn update_range(&mut self, node: usize, l: usize, r: usize, ql: usize, qr: usize, val: L) {
        if qr < l || r < ql { return; }
        if ql <= l && r <= qr {
            self.apply_lazy(node, val);
            return;
        }
        self.push_down(node);
        let mid = (l + r) / 2;
        self.update_range(2*node, l, mid, ql, qr, val.clone());
        self.update_range(2*node+1, mid+1, r, ql, qr, val);
        self.pull_up(node);
    }
}

---

Streaming/Sublinear

Bloom Filters

When: Probabilistic membership, no false negatives

use bloom::BloomFilter;
let mut filter = BloomFilter::new(expected_items, false_positive_rate);
filter.insert(&item);
if filter.may_contain(&item) { /* check authoritative source */ }

Count-Min Sketch

When: Frequency estimation — O(1) query, O(k) space

struct CountMinSketch { counters: Vec<Vec<u64>>, hash_fns: Vec<Box<dyn Fn(&[u8]) -> usize>> }
impl CountMinSketch {
    fn insert(&mut self, item: &[u8]) {
        for (i, hf) in self.hash_fns.iter().enumerate() {
            self.counters[i][hf(item) % self.counters[i].len()] += 1;
        }
    }
    fn estimate(&self, item: &[u8]) -> u64 {
        self.hash_fns.iter().enumerate()
            .map(|(i, hf)| self.counters[i][hf(item) % self.counters[i].len()])
            .min().unwrap()
    }
}

HyperLogLog

When: Count distinct — O(log log n) space

use hyperloglogplus::HyperLogLog;
let mut hll: HyperLogLog<str> = HyperLogLog::new(14).unwrap();  // 2^14 registers
for item in stream { hll.insert(&item); }
let cardinality = hll.count();

Libraries: hyperloglogplus

Locality-Sensitive Hashing (LSH)

When: Approximate nearest neighbor search

// For cosine similarity: random hyperplane LSH
// For Jaccard similarity: MinHash

use minhash::MinHash;
let mh1 = MinHash::new(128);  // 128 hash functions
let sig1 = mh1.signature(&set1);
let sig2 = mh1.signature(&set2);
let approx_jaccard = mh1.similarity(&sig1, &sig2);

Cuckoo Filter

When: Membership with deletion (Bloom alternative), better space at low FP rates

struct CuckooFilter {
    buckets: Vec<[Fingerprint; 4]>,  // 4 slots per bucket
    num_items: usize,
}

impl CuckooFilter {
    fn fingerprint(item: &[u8]) -> Fingerprint { hash(item) as Fingerprint }

    fn bucket_indices(&self, item: &[u8]) -> (usize, usize) {
        let fp = Self::fingerprint(item);
        let i1 = hash(item) % self.buckets.len();
        let i2 = (i1 ^ hash(&fp.to_le_bytes())) % self.buckets.len();
        (i1, i2)
    }

    fn insert(&mut self, item: &[u8]) -> bool {
        let fp = Self::fingerprint(item);
        let (i1, i2) = self.bucket_indices(item);
        // Try both buckets, then cuckoo displacement
    }

    fn contains(&self, item: &[u8]) -> bool {
        let fp = Self::fingerprint(item);
        let (i1, i2) = self.bucket_indices(item);
        self.buckets[i1].contains(&fp) || self.buckets[i2].contains(&fp)
    }

    fn delete(&mut self, item: &[u8]) -> bool {
        // Find and remove fingerprint from either bucket
    }
}

Libraries: cuckoofilter, xorf

Minimal Perfect Hashing

When: Static key set, guaranteed O(1), ~2-3 bits/key

// CHD algorithm: n keys → [0, n) with no collisions
struct MinimalPerfectHash {
    pilots: Vec<u32>,      // Pilot values per bucket
    values: Vec<Value>,    // Direct-indexed values
}

impl MinimalPerfectHash {
    fn build(keys: &[Key]) -> Self {
        // Group keys by initial hash
        // Sort buckets by size (largest first)
        // Find pilot for each bucket that avoids collisions
    }

    fn get(&self, key: &Key) -> Option<&Value> {
        let bucket = hash1(key) % self.pilots.len();
        let pilot = self.pilots[bucket];
        let pos = (hash1(key) ^ hash2(key).wrapping_mul(pilot as u64)) as usize % self.values.len();
        Some(&self.values[pos])
    }
}

Libraries: phf (compile-time), boomphf, ph

Fractional Cascading

When: Searching same value across multiple sorted lists — O(k log n) → O(log n + k)

struct FractionalCascade {
    augmented: Vec<Vec<(i64, usize)>>,  // (value, pointer to next list)
}

impl FractionalCascade {
    fn build(lists: Vec<Vec<i64>>) -> Self {
        // Start from last list
        // Build backwards, interleaving every other element from next list
        // Each element has pointer to corresponding position in next list
    }

    fn search(&self, x: i64) -> Vec<usize> {
        // Binary search in first list
        // Follow pointers for remaining lists (adjust by at most 2)
    }
}

Use cases: Computational geometry, database range queries

---

Algebraic Techniques

FFT/NTT Convolution

When: Polynomial multiplication — O(n²) → O(n log n)

use rustfft::{FftPlanner, num_complex::Complex};

fn convolve(a: &[f64], b: &[f64]) -> Vec<f64> {
    let n = (a.len() + b.len() - 1).next_power_of_two();
    let mut planner = FftPlanner::new();
    let fft = planner.plan_fft_forward(n);
    let ifft = planner.plan_fft_inverse(n);

    let mut a_fft: Vec<_> = a.iter().map(|&x| Complex::new(x, 0.0)).collect();
    let mut b_fft: Vec<_> = b.iter().map(|&x| Complex::new(x, 0.0)).collect();
    a_fft.resize(n, Complex::new(0.0, 0.0));
    b_fft.resize(n, Complex::new(0.0, 0.0));

    fft.process(&mut a_fft);
    fft.process(&mut b_fft);

    let mut result: Vec<_> = a_fft.iter().zip(&b_fft).map(|(a, b)| a * b).collect();
    ifft.process(&mut result);

    result.iter().map(|c| c.re / n as f64).take(a.len() + b.len() - 1).collect()
}

Matrix Exponentiation

When: Linear recurrence — O(n) → O(log n)

type Matrix = [[i64; 2]; 2];

fn mat_mul(a: &Matrix, b: &Matrix, m: i64) -> Matrix {
    let mut c = [[0; 2]; 2];
    for i in 0..2 {
        for j in 0..2 {
            for k in 0..2 {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % m;
            }
        }
    }
    c
}

fn mat_pow(mut base: Matrix, mut exp: u64, m: i64) -> Matrix {
    let mut result = [[1, 0], [0, 1]];  // Identity
    while exp > 0 {
        if exp & 1 == 1 { result = mat_mul(&result, &base, m); }
        base = mat_mul(&base, &base, m);
        exp >>= 1;
    }
    result
}

fn fibonacci(n: u64, m: i64) -> i64 {
    if n == 0 { return 0; }
    mat_pow([[1, 1], [1, 0]], n, m)[0][1]
}

Möbius Transform / Subset Convolution

When: Sum over subsets, subset DP

// Zeta transform: f'[S] = Σ_{T⊆S} f[T]
fn zeta_transform(f: &mut [i64]) {
    let n = f.len().trailing_zeros() as usize;
    for i in 0..n {
        for mask in 0..f.len() {
            if mask & (1 << i) != 0 {
                f[mask] += f[mask ^ (1 << i)];
            }
        }
    }
}

// Möbius transform (inverse): f[S] = Σ_{T⊆S} (-1)^{|S|-|T|} f'[T]
fn mobius_transform(f: &mut [i64]) {
    let n = f.len().trailing_zeros() as usize;
    for i in 0..n {
        for mask in 0..f.len() {
            if mask & (1 << i) != 0 {
                f[mask] -= f[mask ^ (1 << i)];
            }
        }
    }
}

Linear Algebra over GF(2)

When: XOR systems, toggle problems, error correction

// Solve Ax = b over GF(2) using Gaussian elimination
fn solve_gf2(mut a: Vec<Vec<bool>>, mut b: Vec<bool>) -> Option<Vec<bool>> {
    let n = a.len();
    let m = a[0].len();
    let mut pivot_col = 0;

    for row in 0..n {
        if pivot_col >= m { break; }

        // Find pivot
        let pivot_row = (row..n).find(|&r| a[r][pivot_col])?;
        a.swap(row, pivot_row);
        b.swap(row, pivot_row);

        // Eliminate
        for r in 0..n {
            if r != row && a[r][pivot_col] {
                for c in 0..m { a[r][c] ^= a[row][c]; }
                b[r] ^= b[row];
            }
        }
        pivot_col += 1;
    }
    Some(b)
}

---

Graph Optimizations

Bidirectional Search / Meet-in-the-Middle

When: Exponential branching — O(b^d) → O(b^{d/2})

fn bidirectional_bfs(start: Node, goal: Node, graph: &Graph) -> Option<usize> {
    let mut forward = HashMap::from([(start, 0)]);
    let mut backward = HashMap::from([(goal, 0)]);
    let mut forward_frontier = vec![start];
    let mut backward_frontier = vec![goal];

    while !forward_frontier.is_empty() && !backward_frontier.is_empty() {
        // Expand smaller frontier
        if forward_frontier.len() <= backward_frontier.len() {
            let mut next = Vec::new();
            for node in forward_frontier {
                let dist = forward[&node];
                for neighbor in graph.neighbors(node) {
                    if let Some(&bd) = backward.get(&neighbor) {
                        return Some(dist + 1 + bd);  // Found!
                    }
                    if !forward.contains_key(&neighbor) {
                        forward.insert(neighbor, dist + 1);
                        next.push(neighbor);
                    }
                }
            }
            forward_frontier = next;
        } else {
            // Similar for backward
        }
    }
    None
}

Mo's Algorithm

When: Offline range queries — O(qn) → O((n+q)√n)

fn mo_algorithm(arr: &[i64], queries: &[(usize, usize)]) -> Vec<i64> {
    let n = arr.len();
    let block = (n as f64).sqrt() as usize + 1;

    // Sort queries by (l/block, r)
    let mut indexed: Vec<_> = queries.iter().enumerate()
        .map(|(i, &(l, r))| (l / block, r, l, i))
        .collect();
    indexed.sort();

    let mut results = vec![0; queries.len()];
    let mut current = 0i64;
    let mut cur_l = 0;
    let mut cur_r = 0;

    for (_, r, l, idx) in indexed {
        while cur_r < r { current += add(arr[cur_r]); cur_r += 1; }
        while cur_l > l { cur_l -= 1; current += add(arr[cur_l]); }
        while cur_r > r { cur_r -= 1; current -= remove(arr[cur_r]); }
        while cur_l < l { current -= remove(arr[cur_l]); cur_l += 1; }
        results[idx] = current;
    }
    results
}

Centroid Decomposition

When: Path queries on trees, divide & conquer

fn centroid_decomposition(tree: &Tree) -> CentroidTree {
    fn find_centroid(tree: &Tree, root: usize, removed: &[bool]) -> usize {
        let size = subtree_size(tree, root, removed);
        let mut cur = root;
        loop {
            let heavy_child = tree.children(cur)
                .filter(|&c| !removed[c])
                .find(|&c| subtree_size(tree, c, removed) > size / 2);
            match heavy_child {
                Some(c) => cur = c,
                None => return cur,
            }
        }
    }

    fn decompose(tree: &Tree, root: usize, removed: &mut [bool]) -> CentroidNode {
        let centroid = find_centroid(tree, root, removed);
        removed[centroid] = true;
        let children: Vec<_> = tree.children(centroid)
            .filter(|&c| !removed[c])
            .map(|c| decompose(tree, c, removed))
            .collect();
        CentroidNode { id: centroid, children }
    }

    decompose(tree, 0, &mut vec![false; tree.len()])
}

Union-Find with Rollback

When: Undo connectivity (no path compression for rollback)

struct UFRollback {
    parent: Vec<usize>,
    rank: Vec<usize>,
    history: Vec<(usize, usize, usize)>,  // (node, old_parent, old_rank)
}

impl UFRollback {
    fn new(n: usize) -> Self {
        Self { parent: (0..n).collect(), rank: vec![0; n], history: Vec::new() }
    }

    fn find(&self, mut x: usize) -> usize {
        while self.parent[x] != x { x = self.parent[x]; }
        x
    }

    fn union(&mut self, x: usize, y: usize) -> bool {
        let (rx, ry) = (self.find(x), self.find(y));
        if rx == ry { return false; }

        let (small, large) = if self.rank[rx] < self.rank[ry] { (rx, ry) } else { (ry, rx) };
        self.history.push((small, self.parent[small], self.rank[large]));

        self.parent[small] = large;
        if self.rank[rx] == self.rank[ry] { self.rank[large] += 1; }
        true
    }

    fn checkpoint(&self) -> usize { self.history.len() }

    fn rollback(&mut self, checkpoint: usize) {
        while self.history.len() > checkpoint {
            let (node, old_parent, old_rank) = self.history.pop().unwrap();
            let large = self.parent[node];
            self.parent[node] = old_parent;
            self.rank[large] = old_rank;
        }
    }
}

---

Cache-Oblivious Design

Principles

1. Recursive decomposition: Problems splitting into n/2 subproblems naturally fit cache 2. Van Emde Boas layout: Recursive memory layout for trees 3. Blocking without block size: Algorithms that work for any cache size

Cache-Oblivious Matrix Transpose

fn transpose_recursive(
    src: &[f64], dst: &mut [f64],
    n: usize, m: usize,
    src_stride: usize, dst_stride: usize,
    si: usize, sj: usize, di: usize, dj: usize,
) {
    if n <= 32 && m <= 32 {
        // Base case: fits in cache
        for i in 0..n {
            for j in 0..m {
                dst[(di + j) * dst_stride + dj + i] = src[(si + i) * src_stride + sj + j];
            }
        }
    } else if n >= m {
        // Split rows
        let mid = n / 2;
        transpose_recursive(src, dst, mid, m, src_stride, dst_stride, si, sj, di, dj);
        transpose_recursive(src, dst, n - mid, m, src_stride, dst_stride, si + mid, sj, di, dj + mid);
    } else {
        // Split columns
        let mid = m / 2;
        transpose_recursive(src, dst, n, mid, src_stride, dst_stride, si, sj, di, dj);
        transpose_recursive(src, dst, n, m - mid, src_stride, dst_stride, si, sj + mid, di + mid, dj);
    }
}

---

Randomized Algorithms

Reservoir Sampling

When: Uniform random sample from stream of unknown size

fn reservoir_sample<T: Clone>(stream: impl Iterator<Item = T>, k: usize) -> Vec<T> {
    let mut reservoir = Vec::with_capacity(k);
    let mut rng = rand::thread_rng();

    for (i, item) in stream.enumerate() {
        if i < k {
            reservoir.push(item);
        } else {
            let j = rng.gen_range(0..=i);
            if j < k { reservoir[j] = item; }
        }
    }
    reservoir
}

Randomized Quickselect

When: Finding kth smallest element — O(n) expected

fn quickselect<T: Ord + Clone>(arr: &mut [T], k: usize) -> T {
    let mut rng = rand::thread_rng();

    fn partition<T: Ord>(arr: &mut [T], pivot_idx: usize) -> usize {
        arr.swap(pivot_idx, arr.len() - 1);
        let mut i = 0;
        for j in 0..arr.len() - 1 {
            if arr[j] < arr[arr.len() - 1] {
                arr.swap(i, j);
                i += 1;
            }
        }
        arr.swap(i, arr.len() - 1);
        i
    }

    let pivot_idx = rng.gen_range(0..arr.len());
    let pivot_pos = partition(arr, pivot_idx);

    match pivot_pos.cmp(&k) {
        Ordering::Equal => arr[k].clone(),
        Ordering::Greater => quickselect(&mut arr[..pivot_pos], k),
        Ordering::Less => quickselect(&mut arr[pivot_pos + 1..], k - pivot_pos - 1),
    }
}

Amortized Analysis Patterns

Key insight: Don't optimize operations that are already amortized O(1)

Examples:

• Dynamic array resize: O(1) amortized push despite O(n) occasional resize
• Union-Find path compression: O(α(n)) amortized despite O(log n) worst case
• Splay tree: O(log n) amortized despite O(n) worst case

Potential method: Expensive operations are rare and "pay" for future cheap operations

Hirschberg's Algorithm

When: Sequence alignment when O(n²) space is prohibitive — O(nm) space → O(min(n,m))

fn hirschberg(a: &[u8], b: &[u8]) -> Vec<Edit> {
    if a.is_empty() { return b.iter().map(|&c| Edit::Insert(c)).collect(); }
    if b.is_empty() { return a.iter().map(|_| Edit::Delete).collect(); }
    if a.len() == 1 { return base_case(a, b); }

    let mid = a.len() / 2;
    let (a1, a2) = a.split_at(mid);

    let score_l = nw_score_linear_space(a1, b);
    let score_r = nw_score_linear_space_rev(a2, b);

    // Find optimal split point in b
    let split = (0..=b.len())
        .max_by_key(|&j| score_l[j] + score_r[b.len() - j])
        .unwrap();

    let (b1, b2) = b.split_at(split);
    let mut result = hirschberg(a1, b1);
    result.extend(hirschberg(a2, b2));
    result
}

fn nw_score_linear_space(a: &[u8], b: &[u8]) -> Vec<i32> {
    let mut prev = (0..=b.len() as i32).map(|i| -i).collect::<Vec<_>>();
    let mut curr = vec![0; b.len() + 1];

    for (i, &ca) in a.iter().enumerate() {
        curr[0] = -(i as i32 + 1);
        for (j, &cb) in b.iter().enumerate() {
            let match_score = if ca == cb { 1 } else { -1 };
            curr[j + 1] = (prev[j] + match_score)
                .max(prev[j + 1] - 1)
                .max(curr[j] - 1);
        }
        std::mem::swap(&mut prev, &mut curr);
    }
    prev
}

Use cases: Bioinformatics, diff algorithms, sequences >10K elements

---

Quick Reference

Libraries

Language-Specific Profiling & Trouble Spots

Contents

1. Rust 2. Go 3. TypeScript 4. Python 5. Universal Patterns

---

Rust

Profiling

# CPU flamegraph (best first tool)
cargo flamegraph --root -- ./target/release/binary <args>

# Allocation
heaptrack ./binary <args> && heaptrack_gui heaptrack.binary.*.zst
# Or DHAT (add dhat to Cargo.toml with optional feature)
DHAT_LOG_FILE=dhat.out cargo run --release --features dhat-heap -- <args>

# perf (Linux)
perf record -g --call-graph dwarf ./binary <args> && perf report

# macOS
cargo instruments -t "Time Profiler" --release -- <args>

# Cache misses
valgrind --tool=cachegrind ./binary <args>

Trouble Spots

Grep for Issues

rg '\.clone\(\)' --type rust -c | sort -t: -k2 -rn | head -20
rg '\.unwrap\(\)' src/ --type rust
rg 'String::from|\.to_string\(\)|format!' --type rust -c
rg 'Box<dyn|&dyn|Arc<dyn' --type rust
rg 'Mutex::new|RwLock::new' --type rust
rg 'Vec::new\(\)' --type rust  # Check if followed by push loop

Optimizations

// Fast hasher
use rustc_hash::FxHashMap;
let map: FxHashMap<K, V> = FxHashMap::default();

// Stack for small collections
use smallvec::SmallVec;
let items: SmallVec<[Item; 8]> = SmallVec::new();

// Conditional ownership
fn process(input: &str) -> Cow<str> {
    if needs_change { Cow::Owned(modify(input)) }
    else { Cow::Borrowed(input) }
}

// Pre-size
let mut results = Vec::with_capacity(items.len());
let mut map = HashMap::with_capacity(expected_size);

// Avoid format! in hot path
let mut buf = String::with_capacity(100);
write!(buf, "{}: {}", key, value)?;

// Inline hot functions
#[inline]
fn hot_function() { /* ... */ }

Profile-Guided Optimization (PGO)

# Step 1: Build instrumented binary
RUSTFLAGS="-Cprofile-generate=/tmp/pgo-data" cargo build --release

# Step 2: Run with representative workload
./target/release/binary <typical-args>
./target/release/binary <another-workload>

# Step 3: Merge profile data
llvm-profdata merge -o /tmp/pgo-data/merged.profdata /tmp/pgo-data

# Step 4: Build optimized binary
RUSTFLAGS="-Cprofile-use=/tmp/pgo-data/merged.profdata" cargo build --release

Typical gains: 10-20% for hot paths When to use: Production binaries, after other optimizations exhausted

---

Go

Profiling

# Add to main.go
import _ "net/http/pprof"
go func() { http.ListenAndServe("localhost:6060", nil) }()

# CPU
go tool pprof http://localhost:6060/debug/pprof/profile?seconds=30

# Memory
go tool pprof http://localhost:6060/debug/pprof/heap

# Goroutine/blocking
go tool pprof http://localhost:6060/debug/pprof/goroutine
go tool pprof http://localhost:6060/debug/pprof/block

# Tracer
curl -o trace.out http://localhost:6060/debug/pprof/trace?seconds=5
go tool trace trace.out

# Escape analysis
go build -gcflags='-m -m' 2>&1 | grep "escapes to heap"

Trouble Spots

Grep for Issues

rg 'interface\{\}|any\b' --type go
rg '\+.*string|string.*\+' --type go
rg 'for.*\{' -A5 --type go | rg 'defer'
rg 'make\(chan.*,\s*[01]\)' --type go
rg 'var.*sync\.(Mutex|RWMutex)' --type go
rg 'fmt\.Sprintf' --type go
rg 'reflect\.' --type go

Optimizations

// Pre-allocate
items := make([]Item, 0, expectedSize)

// strings.Builder
var b strings.Builder
b.Grow(100)
b.WriteString(s1)
b.WriteString(s2)

// sync.Pool
var bufPool = sync.Pool{New: func() interface{} { return new(bytes.Buffer) }}
buf := bufPool.Get().(*bytes.Buffer)
defer bufPool.Put(buf)
buf.Reset()

// RWMutex for read-heavy
var mu sync.RWMutex
mu.RLock()
defer mu.RUnlock()

// Atomic counters
var counter atomic.Int64
counter.Add(1)

// strconv over fmt
s := strconv.Itoa(n)  // Not fmt.Sprintf("%d", n)

GC Debugging

# Trace GC activity
GODEBUG=gctrace=1 ./binary

# Output format:
# gc 1 @0.012s 2%: 0.026+0.44+0.003 ms clock, 0.10+0.32/0.40/0+0.012 ms cpu, 4->4->0 MB, 5 MB goal, 4 P
#    │   │   │    │                      │                             │           │        └── processors
#    │   │   │    │                      │                             │           └── target heap
#    │   │   │    │                      │                             └── heap before->after->live
#    │   │   │    │                      └── CPU times (assist/bg/idle mark)
#    │   │   │    └── wall-clock times (sweep/mark/term)
#    │   │   └── CPU % in GC
#    │   └── time since start
#    └── GC cycle number

# Memory allocation tracking
GODEBUG=allocfreetrace=1 ./binary  # Very verbose - every alloc/free

# Schedule tracing (goroutine scheduling)
GODEBUG=schedtrace=1000 ./binary   # Every 1000ms

Use when: High GC pause times, memory pressure, allocation debugging

Race Detection

# Build with race detector
go build -race ./...

# Test with race detector (recommended)
go test -race ./...

# Run with race detector
go run -race main.go

Note: 10-20x slowdown, 5-10x memory overhead; use in CI, not production Finds: Data races, concurrent map access, improper channel use

---

TypeScript

Profiling

# V8 profiler
node --prof app.js && node --prof-process isolate-*.log > profile.txt

# Chrome DevTools
node --inspect app.js
# Open chrome://inspect

# clinic.js (best)
npm install -g clinic
clinic doctor -- node app.js
clinic flame -- node app.js
clinic bubbleprof -- node app.js

# 0x flamegraphs
npm install -g 0x && 0x app.js

# Event loop
const { monitorEventLoopDelay } = require('perf_hooks');
const h = monitorEventLoopDelay({ resolution: 20 });
h.enable();
setInterval(() => console.log(h.percentile(99)), 1000);

Trouble Spots

Grep for Issues

rg 'fs\.(readFileSync|writeFileSync|existsSync)' --type ts
rg 'for.*await|while.*await' --type ts
rg 'JSON\.(parse|stringify)' --type ts
rg 'console\.(log|info|warn|error)' --type ts
rg 'new RegExp' --type ts
rg '\.(map|filter|reduce)\(.*\)\.(map|filter|reduce)' --type ts

Optimizations

// Set for membership
const seen = new Set<string>();
if (seen.has(item)) { /* O(1) vs includes O(n) */ }

// Parallel async
const results = await Promise.all(items.map(processAsync));

// Stream large JSON
import { createReadStream } from 'fs';
import { parser } from 'stream-json';
createReadStream('large.json').pipe(parser()).on('data', process);

// Pre-compile regex
const PATTERN = /\d+/g;  // Outside function

// Map over object
const cache = new Map<string, Result>();  // Faster for dynamic keys

// TypedArrays
const data = new Float64Array(1000);  // Faster than number[]

// Worker threads for CPU
import { Worker, isMainThread, parentPort } from 'worker_threads';

---

Python

Profiling

# cProfile
python -m cProfile -s cumtime script.py > profile.txt

# snakeviz (visual)
pip install snakeviz && python -m cProfile -o output.prof script.py && snakeviz output.prof

# line_profiler (decorate with @profile)
pip install line_profiler && kernprof -l -v script.py

# py-spy (no code changes, best)
pip install py-spy
py-spy record -o profile.svg -- python script.py
py-spy top --pid <PID>

# memory_profiler
pip install memory_profiler && python -m memory_profiler script.py

# scalene (CPU + memory + GPU)
pip install scalene && scalene script.py

Trouble Spots

Grep for Issues

rg 'for.*:' -A5 --type py | rg '\+='  # String concat
rg '\.append\(' --type py -c | sort -t: -k2 -rn
rg 'in \[|in list' --type py
rg '^\s+import |^\s+from .* import' --type py
rg 're\.(match|search|findall|sub)\(' --type py
rg '\.iterrows\(\)|\.itertuples\(\)' --type py

Optimizations

# String join
result = ''.join(items)  # Not += loop

# List comprehension
result = [x * 2 for x in items]  # Not append loop

# Set for membership
valid = set(valid_items)
if item in valid:  # O(1)

# Local caching
def process(items):
    local_func = expensive_module.func
    for item in items:
        local_func(item)

# Generator for large data
def process_large(items):
    for item in items:
        yield transform(item)

# Compile regex
PATTERN = re.compile(r'\d+')

# __slots__ for many instances
class Point:
    __slots__ = ['x', 'y']

# NumPy vectorize
np.arange(1000000) ** 2  # Not list comprehension

# lru_cache
from functools import lru_cache
@lru_cache(maxsize=128)
def expensive(n): return compute(n)

# Avoid pandas iteration
df['new'] = df['old'].apply(func)  # Not iterrows
df['new'] = np.where(df['old'] > 0, df['old'] * 2, 0)  # Better

GC Debugging

import gc

# Enable GC stats
gc.set_debug(gc.DEBUG_STATS)  # Print collection stats

# More verbose - show collectable objects
gc.set_debug(gc.DEBUG_COLLECTABLE)

# Show uncollectable objects (reference cycles that can't be freed)
gc.set_debug(gc.DEBUG_UNCOLLECTABLE)

# All debug flags
gc.set_debug(gc.DEBUG_STATS | gc.DEBUG_COLLECTABLE | gc.DEBUG_UNCOLLECTABLE)

# Manual GC control
gc.disable()           # Disable automatic GC
gc.collect()           # Force collection
gc.enable()            # Re-enable

# Get GC stats
print(gc.get_stats())  # Generation stats
print(gc.get_count())  # Objects in each generation

# Find reference cycles
gc.collect()           # Collect first
print(gc.garbage)      # Uncollectable objects (reference cycles with __del__)

Use when: Memory leaks, high GC pause times, debugging reference cycles

objgraph (Visual Memory Debugging)

import objgraph

# Find what's creating the most objects
objgraph.show_most_common_types(limit=20)

# Find growth between two points
objgraph.show_growth()  # Call multiple times to see delta

# Find references to specific objects
objgraph.show_backrefs([obj], filename='refs.png')

# Find reference chains (why isn't this GC'd?)
objgraph.find_backref_chain(obj, objgraph.is_proper_module)

Install: pip install objgraph

---

Universal Patterns

Find Hot Loops

rg 'for\s*\(|for\s+\w+\s+in|while\s*\(' --type-add 'code:*.{rs,go,ts,py}' -t code

Nested Loops (O(n²))

rg 'for.*\{' -A20 | rg 'for.*\{'

By Symptom

Red Flags

---

Profiling Cheatsheet

Detailed Optimization Methodology

Step-by-step process for rigorous, provably correct performance optimization.

Phase A: Baseline

A1. Test Suite

cargo test --release 2>&1 | tee baseline_tests.txt
grep -E "(FAILED|error)" baseline_tests.txt && echo "FIX TESTS FIRST" && exit 1

A2. Performance Metrics

# Latency (p50/p95/p99)
hyperfine --warmup 3 --runs 30 --export-json baseline.json './binary <args>'
cat baseline.json | jq '.results[0].times | sort |
  {p50: .[length/2], p95: .[length*0.95|floor], p99: .[length*0.99|floor]}'

# Peak memory
/usr/bin/time -v ./binary <args> 2>&1 | grep "Maximum resident"

A3. Document

## Baseline (DATE)
| Metric | Value |
|--------|-------|
| p50 | X ms |
| p95 | X ms |
| p99 | X ms |
| Peak memory | X MB |
| Tests | PASS |

---

Phase B: Profile

B1. CPU (Flamegraph)

cargo flamegraph --root --release -- <args>
# Alternative
perf record -g ./binary <args> && perf script | inferno-collapse-perf | inferno-flamegraph > flame.svg

Analysis: Widest bars = most time. Deep stacks = call overhead.

B2. Allocation

# DHAT
DHAT_LOG_FILE=dhat.out cargo +nightly run --release --features dhat-heap -- <args>
dhat-viewer dhat.out

# heaptrack
heaptrack ./binary <args>
heaptrack_gui heaptrack.binary.*.zst

B3. I/O

strace -c ./binary <args>
strace -T -e read,write,open,close ./binary <args> 2>&1 | head -1000

B4. Hotspot Table

| Rank | Location | % Time | Category |
|------|----------|--------|----------|
| 1 | `file.rs:123` | 35% | CPU |
| 2 | `file.rs:456` | 22% | Alloc |
| 3 | `file.rs:789` | 15% | I/O |

---

Phase C: Equivalence Oracle

C1. Golden Outputs

for input in test_inputs/*; do
  ./binary "$input" > "golden_outputs/$(basename $input).out"
done
sha256sum golden_outputs/* > golden_checksums.txt

C2. Invariants

Document: 1. Ordering: Results sorted by [field] 2. Tie-breaking: Equal items ordered by [secondary] 3. Floating-point: IEEE 754, no NaN 4. RNG seeds: Deterministic given seed X

C3. Property Tests

use proptest::prelude::*;

proptest! {
    #[test]
    fn deterministic(input in any::<Vec<u8>>()) {
        assert_eq!(process(&input), process(&input));
    }

    #[test]
    fn ordering_preserved(items in prop::collection::vec(any::<Item>(), 0..1000)) {
        let result = process(&items);
        assert!(result.windows(2).all(|w| w[0] <= w[1]));
    }
}

---

Phase D: Isomorphism Proof

Template

## Change: [description]

### What Changes
- Before: [code/behavior]
- After: [code/behavior]

### Proof
1. **I/O Equivalence:** Same inputs → same outputs because [reason]
2. **Ordering:** Preserved because [reason or N/A]
3. **Tie-breaking:** Unchanged because [reason or N/A]
4. **Floating-point:** [identical/N/A]
5. **RNG:** [unchanged/N/A]

### Verification
- [ ] `sha256sum -c golden_checksums.txt`
- [ ] `cargo test`
- [ ] `diff <(./old input) <(./new input)`

Common Proofs

---

Phase E: Opportunity Matrix

Scoring

Score = (Impact × Confidence) / Effort

Impact (1-5): 5=>50%+, 4=25-50%, 3=10-25%, 2=5-10%, 1=<5%
Confidence (1-5): 5=profiler confirms, 3=likely, 1=speculative
Effort (1-5): 5=>1 day, 3=hours, 1=minutes

Matrix

Rule: Only implement Score ≥ 2.0

---

Phase F: Implementation

One Lever Per Change

git checkout -b perf/add-hashmap-index
# Make ONLY the optimization change
# NO: refactoring, cleanup, style
git diff --stat  # Minimal files

Checklist

• [ ] Single technique applied
• [ ] No unrelated refactors
• [ ] Commit message explains perf rationale

Rollback Plan

## Rollback
- Command: `git revert <sha>`
- Risk: None / Low / Medium
- Post-rollback tests: [list]

---

Phase G: Regression Guardrails

Benchmarks

use criterion::{criterion_group, criterion_main, Criterion};

fn bench_critical(c: &mut Criterion) {
    let input = setup_input();
    c.bench_function("critical_function", |b| b.iter(|| critical_function(&input)));
}

criterion_group!(benches, bench_critical);
criterion_main!(benches);

CI Gate

- name: Check regression
  run: |
    cargo bench -- --baseline main --save-baseline current
    cargo benchcmp main current --threshold 10  # Fail if >10% regression

Monitoring

use metrics::{histogram, counter};

fn critical_function(input: &Input) -> Output {
    let start = Instant::now();
    let result = do_work(input);
    histogram!("critical_function_ms", start.elapsed().as_millis() as f64);
    result
}

---

Iteration Protocol

After each cycle: 1. Re-baseline → new metrics 2. Re-profile → new hotspots (bottlenecks shift) 3. Update matrix → recalculate scores 4. Repeat → until no Score ≥ 2.0

## History
| Round | Change | p95 Before | p95 After | Δ |
|-------|--------|------------|-----------|---|
| 1 | HashMap | 50ms | 35ms | -30% |
| 2 | Memoize | 35ms | 28ms | -20% |

---

Command Reference

# Profile
cargo flamegraph --root --release -- <args>
heaptrack ./binary <args>
strace -c ./binary <args>

# Benchmark
hyperfine --warmup 3 --runs 30 './binary <args>'
cargo bench

# Memory
/usr/bin/time -v ./binary <args>
valgrind --tool=massif ./binary <args>

# Verify
sha256sum -c golden_checksums.txt
cargo test
diff <(./old input) <(./new input)

# Git
git checkout -b perf/description
git revert <sha>

Optimization Techniques Catalog

Scan for applicable patterns after profiling identifies hotspots.

Contents

1. I/O & Network 2. Memory & Allocation 3. Concurrency 4. Algorithms 5. Data Structures 6. Caching 7. Serialization 8. Strings

---

I/O & Network

N+1 Elimination

// BAD: N round-trips
for id in ids { db.get(id).await; }

// GOOD: 1 round-trip
let items = db.get_many(&ids).await;

Isomorphism: Same results, order may change unless preserved.

Buffer Reuse

// BAD
loop { let buf = vec![0u8; 4096]; file.read(&mut buf)?; }

// GOOD
let mut buf = vec![0u8; 4096];
loop { file.read(&mut buf)?; }

Vectored I/O

// BAD: Multiple syscalls
socket.write(&header)?; socket.write(&body)?;

// GOOD: Single syscall
let iov = [IoSlice::new(&header), IoSlice::new(&body)];
socket.write_vectored(&iov)?;

Async Batching

// BAD: Sequential
for item in items { process(item).await; }

// GOOD: Parallel
futures::future::join_all(items.iter().map(process)).await;

// BETTER: Bounded concurrency
futures::stream::iter(items).map(process).buffer_unordered(10).collect().await;

Bounded Queues

// BAD: Unbounded (memory blowup)
let (tx, rx) = mpsc::unbounded_channel();

// GOOD: Backpressure
let (tx, rx) = mpsc::channel(1000);

---

Memory & Allocation

Pooling

let pool = Pool::new(|| expensive_create(), 10);
let obj = pool.get();  // Reuse, don't create

Libraries: deadpool, bb8, r2d2

Arena Allocation

let arena = bumpalo::Bump::new();
for _ in 0..1000 { arena.alloc_str("item"); }  // Fast bump
// All freed when arena drops

Libraries: bumpalo, typed-arena

SmallVec

use smallvec::SmallVec;
let items: SmallVec<[Item; 8]> = SmallVec::new();  // Stack up to 8

Cow<str>

fn process(input: &str) -> Cow<str> {
    if needs_change(input) { Cow::Owned(modify(input)) }
    else { Cow::Borrowed(input) }  // Zero-copy
}

SoA Layout

// AoS - poor cache locality
struct Point { x: f32, y: f32, z: f32 }
let points: Vec<Point>;

// SoA - excellent for field iteration
struct Points { xs: Vec<f32>, ys: Vec<f32>, zs: Vec<f32> }

---

Concurrency

Sharded Locks

// BAD: Single contention point
let map = Mutex::new(HashMap::new());

// GOOD: 16 shards
let shards: [Mutex<HashMap<K, V>>; 16];
fn shard(key: &K) -> usize { hash(key) % 16 }

Libraries: dashmap, flurry

Lock-Free

use crossbeam::queue::SegQueue;
let queue = SegQueue::new();  // Lock-free MPMC

Libraries: crossbeam, parking_lot

Work-Stealing

rayon::scope(|s| {
    s.spawn(|s| recursive_task(s));  // Automatic load balancing
});

---

Algorithms

Binary Search

// On data
let idx = data.binary_search(&target);

// On answer space (parametric)
let answer = (lo..hi).binary_search_by(|mid| {
    if predicate(mid) { Ordering::Less } else { Ordering::Greater }
});

O(n) → O(log n)

Two-Pointer

fn two_sum_sorted(arr: &[i32], target: i32) -> Option<(usize, usize)> {
    let (mut lo, mut hi) = (0, arr.len() - 1);
    while lo < hi {
        match (arr[lo] + arr[hi]).cmp(&target) {
            Ordering::Equal => return Some((lo, hi)),
            Ordering::Less => lo += 1,
            Ordering::Greater => hi -= 1,
        }
    }
    None
}

O(n²) → O(n)

Sliding Window

fn max_sum_k(arr: &[i32], k: usize) -> i32 {
    let mut sum: i32 = arr[..k].iter().sum();
    let mut max = sum;
    for i in k..arr.len() {
        sum += arr[i] - arr[i - k];
        max = max.max(sum);
    }
    max
}

Prefix Sums

// Build O(n), query O(1)
let prefix: Vec<i64> = arr.iter().scan(0, |acc, &x| { *acc += x; Some(*acc) }).collect();
fn range_sum(prefix: &[i64], l: usize, r: usize) -> i64 {
    prefix[r] - if l > 0 { prefix[l - 1] } else { 0 }
}

Union-Find

struct UnionFind { parent: Vec<usize>, rank: Vec<usize> }
impl UnionFind {
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x { self.parent[x] = self.find(self.parent[x]); }
        self.parent[x]
    }
    fn union(&mut self, x: usize, y: usize) {
        let (rx, ry) = (self.find(x), self.find(y));
        if rx != ry {
            match self.rank[rx].cmp(&self.rank[ry]) {
                Ordering::Less => self.parent[rx] = ry,
                Ordering::Greater => self.parent[ry] = rx,
                Ordering::Equal => { self.parent[ry] = rx; self.rank[rx] += 1; }
            }
        }
    }
}

O(α(n)) per operation

Dijkstra

fn dijkstra(graph: &Graph, start: Node) -> HashMap<Node, Cost> {
    let mut dist = HashMap::new();
    let mut heap = BinaryHeap::new();
    dist.insert(start, 0);
    heap.push(Reverse((0, start)));
    while let Some(Reverse((d, u))) = heap.pop() {
        if d > *dist.get(&u).unwrap_or(&Cost::MAX) { continue; }
        for (v, weight) in graph.edges(u) {
            let new_dist = d + weight;
            if new_dist < *dist.get(&v).unwrap_or(&Cost::MAX) {
                dist.insert(v, new_dist);
                heap.push(Reverse((new_dist, v)));
            }
        }
    }
    dist
}

Topological Sort (Kahn's Algorithm)

fn topological_sort(graph: &Graph) -> Option<Vec<Node>> {
    let mut in_degree: HashMap<Node, usize> = HashMap::new();
    for node in graph.nodes() {
        in_degree.entry(node).or_insert(0);
        for neighbor in graph.neighbors(node) {
            *in_degree.entry(neighbor).or_insert(0) += 1;
        }
    }

    let mut queue: VecDeque<Node> = in_degree.iter()
        .filter(|(_, &d)| d == 0)
        .map(|(&n, _)| n)
        .collect();

    let mut result = Vec::with_capacity(graph.node_count());
    while let Some(node) = queue.pop_front() {
        result.push(node);
        for neighbor in graph.neighbors(node) {
            let deg = in_degree.get_mut(&neighbor).unwrap();
            *deg -= 1;
            if *deg == 0 { queue.push_back(neighbor); }
        }
    }

    if result.len() == graph.node_count() { Some(result) } else { None }  // None = cycle
}

Use when: DAG processing, dependency resolution, build systems O(V + E)

Graph Traversal with Early Termination

// BFS with early exit - find first match
fn bfs_find<F>(graph: &Graph, start: Node, predicate: F) -> Option<Node>
where F: Fn(&Node) -> bool
{
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    queue.push_back(start);
    visited.insert(start);

    while let Some(node) = queue.pop_front() {
        if predicate(&node) { return Some(node); }  // Early exit
        for neighbor in graph.neighbors(node) {
            if visited.insert(neighbor) {
                queue.push_back(neighbor);
            }
        }
    }
    None
}

// DFS with early exit - find any path
fn dfs_path(graph: &Graph, start: Node, goal: Node) -> Option<Vec<Node>> {
    let mut visited = HashSet::new();
    let mut path = Vec::new();

    fn dfs(graph: &Graph, node: Node, goal: Node, visited: &mut HashSet<Node>, path: &mut Vec<Node>) -> bool {
        if node == goal { path.push(node); return true; }
        if !visited.insert(node) { return false; }
        path.push(node);
        for neighbor in graph.neighbors(node) {
            if dfs(graph, neighbor, goal, visited, path) { return true; }
        }
        path.pop();
        false
    }

    if dfs(graph, start, goal, &mut visited, &mut path) { Some(path) } else { None }
}

Pattern: Return early when condition met; avoid visiting entire graph Use when: Finding existence, first match, any valid path

---

Data Structures

Selection Matrix

Trie

use radix_trie::Trie;
let mut trie = Trie::new();
trie.insert("hello", 1);
for (k, v) in trie.iter_prefix("hel") { /* ... */ }

Libraries: radix_trie, fst

Bloom Filter

let mut filter = BloomFilter::new(1000, 0.01);  // 1% false positive
filter.insert(&"item");
if filter.contains(&"item") { /* maybe present */ }

Libraries: bloom, probabilistic-collections

---

Caching

LRU

use lru::LruCache;
let mut cache = LruCache::new(NonZeroUsize::new(100).unwrap());
cache.put("key", expensive_compute());

Libraries: lru, cached

Memoization

use cached::proc_macro::cached;
#[cached(size = 100, time = 60)]  // 100 entries, 60s TTL
fn expensive(x: u64) -> u64 { heavy_computation(x) }

Invalidation: TTL, LRU, write-through, cache-aside

---

Serialization

Format Comparison

Rule: bincode/rkyv internal, JSON external only.

Zero-Copy

use rkyv::{Archive, Deserialize, Serialize};
#[derive(Archive, Deserialize, Serialize)]
struct Data { values: Vec<u64> }

let archived = rkyv::check_archived_root::<Data>(&bytes).unwrap();
println!("{}", archived.values[0]);  // Direct memory access

Libraries: rkyv, zerocopy

---

Strings

Interning

use string_interner::{StringInterner, DefaultSymbol};
let mut interner = StringInterner::default();
let sym1 = interner.get_or_intern("hello");
let sym2 = interner.get_or_intern("hello");
assert_eq!(sym1, sym2);  // O(1) comparison

Regex

// BAD: Compile per iteration
for line in lines { Regex::new(r"\d+").unwrap().find(line); }

// GOOD: Compile once
lazy_static! { static ref RE: Regex = Regex::new(r"\d+").unwrap(); }
for line in lines { RE.find(line); }

// BETTER: RegexSet for multiple patterns
let set = RegexSet::new(&[r"\d+", r"\w+", r"[a-z]+"]).unwrap();

SIMD Search

use memchr::memmem;
let finder = memmem::Finder::new(b"pattern");
if let Some(pos) = finder.find(haystack) { /* ... */ }

Libraries: memchr, aho-corasick

---

Applicability Checks

DP

• [ ] Overlapping subproblems? → Memoize
• [ ] Optimal partitioning? → Interval DP
• [ ] DAG with repeated traversal? → Topological DP

Data Structure Selection

• [ ] Point lookups? → HashMap
• [ ] Range queries? → BTreeMap / Segment tree
• [ ] Prefix ops? → Trie
• [ ] Approximate membership? → Bloom filter

---

Library Quick Reference