Speedup and Amdahl's Law
You'll learn how to calculate the real-world performance gains from optimizations and why no single improvement can deliver infinite speedup.
What is Speedup?
Speedup measures how much faster a system becomes after an optimization. It's simply the ratio:
Speedup = Execution Time (before) / Execution Time (after)
For example, if a program took 100 seconds and now takes 25 seconds, the speedup is 4× (four times faster).
Amdahl's Law: The Reality Check
Here's the catch: most optimizations only speed up part of your program. Amdahl's Law tells us the maximum speedup possible when only a fraction of the program benefits from the improvement.
The Formula:
Speedup_overall = 1 / ((1 - f) + f/s)
Where:
- f = fraction of execution time that can be improved (0 to 1)
- s = speedup of that improved fraction
The Insight
Think of it like renovating a restaurant. If cooking takes 80% of meal preparation time (f = 0.8) and you make the kitchen infinitely fast (s = ∞), you still can't eliminate the 20% spent on serving and billing. Your maximum speedup is only 5×, not infinite!
Example: Your program spends 60% of its time on operations you can make 10× faster:
Speedup = 1 / ((1 - 0.6) + 0.6/10) = 1 / (0.4 + 0.06) = 1 / 0.46 ≈ 2.17×
Even though part runs 10× faster, the overall program only runs 2.17× faster because the unimproved 40% becomes the bottleneck.
Key Takeaway: Amdahl's Law shows that optimizing only part of a program yields diminishing returns—the unoptimized portion ultimately limits total speedup, making it critical to identify and improve the largest bottlenecks first.