Profiled optimization
- Rust course
- Expert
- Lesson 46/46
- 7 min
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 callsNo 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.
Practice 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.
Starter code
fn main() {
// buraya yaz
}Sample 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());
}Expected output
6765 2880067194370816120
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Which step comes after fixing the algorithm?
- Nothing
- Verify the result is the same and measure again Correct answer
- Add unsafe right away
- Delete the profile file
Explanation: A correctness test catches a fast but wrong version; a new profile shows the next bottleneck.
2 Catch the overflow
let c = a.____(b)?;
a = b;
b = c;let c = a.checked_add(b)?;
a = b;
b = c;Explanation: checked_add returns None on overflow; ? propagates it upward.
3 Step and tool
| Term | Meaning |
|---|---|
Measure |
flamegraph / criterion |
Bottleneck |
The widest plateau |
Fix |
A better algorithm |
Verify |
Compare with the reference |