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
| Hotspot | Impact (1-5) | Confidence (1-5) | Effort (1-5) | Score |
|---|---|---|---|---|
| func:line | × | × | ÷ | Impact×Conf/Effort |
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
| Pattern | When | Isomorphism |
|---|---|---|
| N+1 → Batch | Sequential fetches | Same results, fewer round-trips |
| Linear → HashMap | Keyed lookups | O(n)→O(1), order may change |
| Lazy eval | Maybe-unused values | Same final values |
| Memoization | Repeated pure calls | Cached = recomputed |
| Buffer reuse | Alloc per iteration | Zero-copy in loop |
Tier 2: Algorithmic
| Pattern | Change | Check |
|---|---|---|
| Binary search | O(n)→O(log n) | Sorted input |
| Two-pointer | O(n²)→O(n) | Structured input |
| Prefix sums | O(n)→O(1) query | Static data |
| Priority queue | O(n)→O(log n) | Top-k/scheduling |
Tier 3: Data Structures
| Structure | Use Case |
|---|---|
| HashMap | Point lookups |
| BTreeMap | Range queries |
| SmallVec | Usually-small collections |
| Arena | Many allocations, bulk free |
| Bloom filter | Membership pre-filter |
Full catalog: TECHNIQUES.md
Language Cheatsheet
| Lang | CPU Profile | Trouble Spot Grep |
|---|---|---|
| Rust | cargo flamegraph | rg '\.clone\(\)' --type rust |
| Go | go tool pprof /debug/pprof/profile | rg 'interface\{\}' --type go |
| TS | clinic flame -- node app.js | rg 'JSON\.(parse|stringify)' --type ts |
| Python | py-spy record -o flame.svg -- python script.py | rg '\.iterrows\(\)' --type py |
Full language guides: LANGUAGE-SPECIFIC.md
Anti-Patterns (Never Do)
| ✗ | Why |
|---|---|
| Optimize without profiling | Wastes effort on non-hotspots |
| Multiple changes per commit | Can't isolate regressions |
| Assume improvement | Must measure before/after |
| Change behavior "while we're here" | Breaks isomorphism guarantee |
| Skip golden output capture | No regression detection |
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
| Need | Reference |
|---|---|
| Complete technique catalog | TECHNIQUES.md |
| Step-by-step methodology | METHODOLOGY.md |
| Language-specific guides | LANGUAGE-SPECIFIC.md |
| Advanced (Round 2+) | ADVANCED.md |
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.