CPU optimization
A hot path gets faster in a strict order: do less work, do it with better
memory access, then shave constant factors. Reaching for micro-optimization
first is how people spend a day on SIMD to beat an O(n^2) loop that a hash set
would have fixed in five minutes. Earn each layer by proving the one above it is
exhausted.
Method
- Profile to the line, not the function. Use a sampling profiler with call
attribution:
perf record, py-spy, pprof, or a flame graph. Confirm the
suspect owns a real share of wall time, and find the exact inner loop, before
changing anything.
- Exhaust the algorithm first. Replace the quadratic scan, the sort inside
the loop, the recomputation of an unchanged value. A better complexity class
or a fitter data structure dwarfs any constant-factor trick; that swap is
algorithmic-optimization's job and it comes before everything below.
- Make memory access sequential and cache-friendly. A linear walk over a
contiguous array beats pointer-chasing a linked structure at equal Big-O,
because it hits cache and the hardware prefetcher. Lay data out to be scanned
in order, and batch work over arrays rather than one scattered object at a
time.
- Hoist invariants and kill redundant work in the loop. Move constant
computations, allocations, and bounds lookups out of the body. Cache a
repeated property access in a local. Avoid per-iteration allocation that
quietly invokes the allocator and collector on the hot path.
- Only now micro-optimize, guided by the profile. Make the common case
straight-line to cut branch misprediction, replace a division by a shift or
multiply, let the compiler vectorize a tight numeric loop or drop to explicit
SIMD where it pays. Each such change earns its place against a benchmark.
- Benchmark on production-shaped input after each step. Measure with a
stable harness (
hyperfine, perf stat, a language microbench) at realistic
size and distribution. Keep the change only if the number moved past noise.
Litmus tests
- Did a profiler name this line, or are you optimizing on suspicion?
- Is the algorithm settled before any constant-factor work started?
- Does the data get walked in order rather than chased through pointers?
- Did each micro-optimization show a measurable win on real input, not just in
theory?
Boundaries
This is single-thread, CPU-bound work. Swapping the algorithm outright is
algorithmic-optimization; spreading work across cores or processes is
concurrency-tuning. Memory footprint, even when it drives the cache misses, is
memory-optimization's concern.
1---2name: cpu-optimization3description: Speed up a CPU-bound hot path by fixing its algorithm and memory access first, then applying micro-optimization only where the profiler still points. Use when a function dominates CPU time and you need it faster without changing what it computes.4---56# CPU optimization78A hot path gets faster in a strict order: do less work, do it with better9memory access, then shave constant factors. Reaching for micro-optimization10first is how people spend a day on SIMD to beat an O(n^2) loop that a hash set11would have fixed in five minutes. Earn each layer by proving the one above it is12exhausted.1314## Method15161. **Profile to the line, not the function.** Use a sampling profiler with call17 attribution: `perf record`, `py-spy`, `pprof`, or a flame graph. Confirm the18 suspect owns a real share of wall time, and find the exact inner loop, before19 changing anything.202. **Exhaust the algorithm first.** Replace the quadratic scan, the sort inside21 the loop, the recomputation of an unchanged value. A better complexity class22 or a fitter data structure dwarfs any constant-factor trick; that swap is23 algorithmic-optimization's job and it comes before everything below.243. **Make memory access sequential and cache-friendly.** A linear walk over a25 contiguous array beats pointer-chasing a linked structure at equal Big-O,26 because it hits cache and the hardware prefetcher. Lay data out to be scanned27 in order, and batch work over arrays rather than one scattered object at a28 time.294. **Hoist invariants and kill redundant work in the loop.** Move constant30 computations, allocations, and bounds lookups out of the body. Cache a31 repeated property access in a local. Avoid per-iteration allocation that32 quietly invokes the allocator and collector on the hot path.335. **Only now micro-optimize, guided by the profile.** Make the common case34 straight-line to cut branch misprediction, replace a division by a shift or35 multiply, let the compiler vectorize a tight numeric loop or drop to explicit36 SIMD where it pays. Each such change earns its place against a benchmark.376. **Benchmark on production-shaped input after each step.** Measure with a38 stable harness (`hyperfine`, `perf stat`, a language microbench) at realistic39 size and distribution. Keep the change only if the number moved past noise.4041## Litmus tests4243- Did a profiler name this line, or are you optimizing on suspicion?44- Is the algorithm settled before any constant-factor work started?45- Does the data get walked in order rather than chased through pointers?46- Did each micro-optimization show a measurable win on real input, not just in47 theory?4849## Boundaries5051This is single-thread, CPU-bound work. Swapping the algorithm outright is52algorithmic-optimization; spreading work across cores or processes is53concurrency-tuning. Memory footprint, even when it drives the cache misses, is54memory-optimization's concern.
Amey-Thakur