Rust Performance Engineering

Avoiding Premature Optimization

Donald Knuth's famous principle summarizes the discipline of systems performance engineering:

"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."

Avoiding premature optimization means distinguishing between good foundational engineering habits (choosing sensible $O(n)$ algorithms, borrowing &str/&[T] instead of cloning, and using buffered I/O) and speculative micro-optimizations (sprinkling unsafe { get_unchecked }, manual SIMD intrinsics, or complex lock-free atomics across cold code paths before profiling).

The Optimization Value vs. Complexity Curve:

  High Impact / Low Complexity (Do Upfront!):
    - Compilation profile (`--release`, `lto = "thin"`)
    - Right asymptotic algorithm & data structure ($O(n)$ vs $O(n^2)$)
    - Buffered I/O (`BufReader`/`BufWriter`) & pre-allocation (`with_capacity`)
  -----------------------------------------------------------------------------
  Measure with a Profiler First! (Only apply to the proven hot 3% of code):
    - Custom SoA / cache-padded layouts & arena allocators
    - Explicit SIMD intrinsics (`core::arch`) & PGO
    - `unsafe` bounds-check bypasses (`get_unchecked`)

Good Mechanical Sympathy vs Premature Micro-Optimization

Practice Classification Why
Accepting &str / &[T] instead of &String / Vec<T> Idiomatic Habit (Do Always) Zero complexity cost; makes API more flexible for callers while avoiding clones.
Using BufWriter / BufReader around File or TcpStream Idiomatic Habit (Do Always) Prevents thousands of 1-byte OS syscalls with a 1-line wrapper.
Choosing HashMap / BTreeSet over $O(n)$ linear Vec::contains for large $N$ Algorithmic Design (Do Upfront) Asymptotic complexity ($O(1)$ vs $O(n)$) dominates micro-optimizations by orders of magnitude.
Replacing safe slice[i] with unsafe { slice.get_unchecked(i) } without profiling Premature Micro-Optimization (Avoid!) Introduces potential Undefined Behavior for a 0% gain if LLVM already eliminated the bounds check or the function is cold!
Writing custom lock-free AtomicPtr queues instead of Mutex<VecDeque<T>> on an uncontended path Premature Micro-Optimization (Avoid!) Uncontended std::sync::Mutex takes ~15ns; custom lock-free structures risk subtle ABA and memory-ordering bugs.

Algorithmic Complexity Always Beats Micro-Optimization

No amount of #[inline(always)], unsafe, or SIMD can rescue an $O(n^2)$ algorithm when $n = 50,000$. Replacing a repeated linear scan ($O(n^2)$) with a single-pass hash lookup ($O(n)$) speeds up execution by 1,000x+ while keeping the code 100% safe and readable:

use std::collections::HashSet;

/// O(N * M) naive intersection: scans `right` linearly for every element in `left`.
pub fn count_common_quadratic(left: &[u64], right: &[u64]) -> usize {
    left.iter().filter(|&x| right.contains(x)).count()
}

/// O(N + M) linear-time intersection using a pre-allocated `HashSet`.
pub fn count_common_linear(left: &[u64], right: &[u64]) -> usize {
    let right_set: HashSet<u64> = right.iter().copied().collect();
    left.iter().filter(|x| right_set.contains(x)).count()
}

fn main() {
    let left: Vec<u64> = (0..500).map(|x| x * 2).collect();
    let right: Vec<u64> = (0..500).map(|x| x * 3).collect();

    let c1 = count_common_quadratic(&left, &right);
    let c2 = count_common_linear(&left, &right);
    assert_eq!(c1, c2);

    println!("Common elements between multiples of 2 and 3: {c2}");
}

Common elements between multiples of 2 and 3: 167

Amdahl's Law: Why Optimizing Cold Code Yields Zero Speedup

By Amdahl's Law, if a function accounts for only 1% of your program's total execution time, even making that function infinitely fast ($1000\times$ speedup) improves total program runtime by at most 1%:

$$\text{Overall Speedup} = \frac{1}{(1 - p) + \frac{p}{s}}$$

where $p$ is the fraction of total runtime spent in the target component and $s$ is the speedup factor of that component. Always profile first to find the component where $p$ is large!