Rust
Profiled optimization
Improve performance with flamegraph.
Final task: profile-guided optimization
The last task applies the right order of optimization: measure → find the bottleneck → fix the algorithm → measure again. A sample hot function: recursive Fibonacci. The flamegraph shows almost all the time is spent in fib_yavas calling itself; the number of calls grows exponentially:
fn fib_yavas(n: u32) -> u64 {
if n < 2 { n as u64 } else { fib_yavas(n - 1) + fib_yavas(n - 2) }
}
// fib_yavas(40): ~330 million calls
No compiler setting (LTO, #[inline], target-cpu) can rescue an exponential algorithm. The gain comes from the algorithm first.
The linear version
The iterative version keeps only the last two values at each step: O(n) time, O(1) memory. Since u64 can hold at most fib(93), we report overflow safely with checked_add:
fn fib_hizli(n: u32) -> Option<u64> {
let (mut a, mut b) = (0u64, 1u64);
for _ in 0..n {
let c = a.checked_add(b)?;
a = b;
b = c;
}
Some(a)
}
Then settings like lto = "thin" and codegen-units = 1 in the release profile gain the last few percent, if measurement confirms it.
Exercise Fast Fibonacci
Write the fib_yavas and fib_hizli functions above. Verify with assert_eq! that the results of fib_yavas(20) and fib_hizli(20) are equal; then print the results of fib_yavas(20) and fib_hizli(90) separated by a space.
Show example solution
fn fib_yavas(n: u32) -> u64 {
if n < 2 {
n as u64
} else {
fib_yavas(n - 1) + fib_yavas(n - 2)
}
}
fn fib_hizli(n: u32) -> Option<u64> {
let (mut a, mut b) = (0u64, 1u64);
for _ in 0..n {
let c = a.checked_add(b)?;
a = b;
b = c;
}
Some(a)
}
fn main() {
assert_eq!(Some(fib_yavas(20)), fib_hizli(20));
println!("{} {}", fib_yavas(20), fib_hizli(90).unwrap());
}
Test yourself
-
Which step comes after fixing the algorithm?
- Nothing
- Verify the result is the same and measure again
- Add unsafe right away
- Delete the profile file
Show answer
Verify the result is the same and measure again — A correctness test catches a fast but wrong version; a new profile shows the next bottleneck.
-
Catch the overflow
let c = a.____(b)?;
a = b;
b = c;
Show answer
let c = a.checked_add(b)?;
a = b;
b = c;
-
Step and tool
- Measure
- flamegraph / criterion
- Bottleneck
- The widest plateau
- Fix
- A better algorithm
- Verify
- Compare with the reference
Next lesson: Expert section exam
