Course contentsShow
← Computer Science
Lesson 1188 of 2,87227. Pipelining and PerformanceFree lesson

Speedup and Amdahl's Law

Calculating speedup from optimizations and understanding the limits imposed by Amdahl's Law.

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.