read0nly

Raw data, clear context.

[
[
[

]
]
]

Amdahl’s law in Python: why one fast function rarely fixes the whole programme

Optimising one function can feel like winning a race and discovering that the finish line is attached to a slower bicycle. The change may be excellent, yet the complete programme barely moves. Amdahl’s law gives that disappointment a number.

The law answers a practical question: how much can the whole job improve when only one part gets faster? It applies to a faster algorithm, a database query, a vectorised loop, extra CPU cores, or any other change that touches only part of the work. The limit comes from the time that remains unchanged.[1]

Start with the time, not the shiny function

Suppose a request spends 70 per cent of its time parsing input and 30 per cent calculating a result. You replace the calculation with an implementation that is effectively instant. The calculation disappears, but the parser still takes its 70 per cent. The best possible whole-request speedup is therefore about 1.43 times.

That is the part people often skip. They see a function become ten times faster and quietly assign that improvement to the application. Amdahl’s law asks a less flattering question: what share of the original wall-clock time did that function own?

The formula

Let p be the fraction of the original execution time spent in the part being improved. Let k be the speedup of that part. The overall speedup is:

S = 1 / ((1 - p) + p / k)

The unchanged work keeps the 1 - p term. The improved work takes only p / k of the old total time. If k becomes very large, the second term tends towards zero and the limit becomes 1 / (1 - p).[1]

For a concrete 30 per cent target, that limit is about 1.43 times. For a target that owns 90 per cent of the work, the ceiling is ten times. The second optimisation has a much better place to start, even before anyone writes code.

A small Python experiment

The programme below creates a workload with two pieces. fixed_work() is deliberately left alone. slow_target() calculates the sum of squares with a Python loop, while fast_target() uses the closed-form formula for the same sum. Both complete functions return the same checksum and mathematical result, so the comparison has a correctness check as well as a timer.

The benchmark uses timeit.Timer.repeat(), preserves all five timing samples for each timed function, and reports their median. Python’s documentation describes timeit as a way to measure small pieces of code while avoiding several common timing traps; its default timer is perf_counter(). The default garbage-collection behaviour is also recorded in the Output block.[2] The input sizes and repeat count are fixed in the file, and imports happen before timing starts.

amdahl_benchmark.py
Python
from __future__ import annotations
import platform
import timeit
from statistics import median
SIZES = (100_000, 250_000, 500_000)
REPEATS = 5
NUMBER = 1
def fixed_work(n: int) -> int:
    """A deliberately unchanged part of the workload."""
    state = 0x12345678
    for value in range(n):
        state = ((state ^ value) * 1_664_525 + 1_013_904_223) & 0xFFFFFFFF
    return state
def slow_target(n: int) -> int:
    """The part we can replace with a closed-form calculation."""
    total = 0
    for value in range(n):
        total += value * value
    return total
def fast_target(n: int) -> int:
    """The same result, calculated without the loop."""
    return (n - 1) * n * (2 * n - 1) // 6
def baseline(n: int) -> tuple[int, int]:
    return fixed_work(n), slow_target(n)
def optimised(n: int) -> tuple[int, int]:
    return fixed_work(n), fast_target(n)
def timed(function, n: int) -> list[float]:
    timer = timeit.Timer(lambda: function(n))
    return timer.repeat(repeat=REPEATS, number=NUMBER)
def median_time(samples: list[float]) -> float:
    return median(samples) / NUMBER
def format_samples(samples: list[float]) -> str:
    return "|".join(f"{sample / NUMBER:.6f}" for sample in samples)
def main() -> None:
    print(f"Python {platform.python_version()} on {platform.platform()}")
    print(f"sizes={SIZES}, repeats={REPEATS}, number={NUMBER}, timer=timeit.default_timer")
    print("sample_format=pipe_separated_seconds; summary=median_of_five; gc=timeit_default_disabled")
    print("correctness_check=baseline_result_equals_optimised_result")
    print("n,fixed_samples_s,slow_target_samples_s,baseline_samples_s,optimised_samples_s,baseline_median_s,optimised_median_s,speedup,slow_target_fraction,ideal_max_speedup,baseline_checksum")
    for n in SIZES:
        expected = baseline(n)
        actual = optimised(n)
        if expected != actual:
            raise AssertionError(f"result mismatch for n={n}: {expected} != {actual}")
        fixed_samples = timed(fixed_work, n)
        target_samples = timed(slow_target, n)
        baseline_samples = timed(baseline, n)
        optimised_samples = timed(optimised, n)
        fixed_s = median_time(fixed_samples)
        target_s = median_time(target_samples)
        baseline_s = median_time(baseline_samples)
        optimised_s = median_time(optimised_samples)
        fraction = target_s / (fixed_s + target_s)
        print(
            f"{n},{format_samples(fixed_samples)},{format_samples(target_samples)},"
            f"{format_samples(baseline_samples)},{format_samples(optimised_samples)},"
            f"{baseline_s:.6f},{optimised_s:.6f},{baseline_s / optimised_s:.2f},"
            f"{fraction:.3f},{1 / (1 - fraction):.2f},{expected[0]}"
        )
if __name__ == "__main__":
    main()

Run it with Python 3. The Output block below is the result from Python 3.13.5 on Linux 6.12.47, aarch64. The machine is a Raspberry Pi class system, so the absolute seconds are useful mainly as a record of this run. The ratios are easier to carry to another machine, although they are still workload and interpreter dependent.

Output
Plain text
Python 3.13.5 on Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41
sizes=(100000, 250000, 500000), repeats=5, number=1, timer=timeit.default_timer
sample_format=pipe_separated_seconds; summary=median_of_five; gc=timeit_default_disabled
correctness_check=baseline_result_equals_optimised_result
n,fixed_samples_s,slow_target_samples_s,baseline_samples_s,optimised_samples_s,baseline_median_s,optimised_median_s,speedup,slow_target_fraction,ideal_max_speedup,baseline_checksum
100000,0.041932|0.041942|0.045236|0.041538|0.041813,0.020925|0.019545|0.019729|0.019690|0.019540,0.061383|0.061686|0.063074|0.061262|0.061299,0.041941|0.041451|0.041541|0.042538|0.096661,0.061383,0.041941,1.46,0.320,1.47,3826213016
250000,0.113384|0.110826|0.113306|0.110100|0.110266,0.052029|0.050874|0.050816|0.059074|0.053049,0.173188|0.163945|0.167082|0.164697|0.163430,0.115135|0.114893|0.112126|0.118710|0.112670,0.164697,0.114893,1.43,0.319,1.47,2424878152
500000,0.220862|0.210516|0.210336|0.209203|0.208462,0.101373|0.098846|0.098771|0.098593|0.098648,0.318932|0.309307|0.308969|0.305955|0.306727,0.220137|0.208704|0.207681|0.208579|0.208503,0.308969,0.208579,1.48,0.320,1.47,3050012696

Every input size passed the equality check. At 500,000 items, replacing the loop changed the median from 0.308969 seconds to 0.208579 seconds, a 1.48 times speedup. The isolated target measurement accounted for 32.0 per cent of the fixed-work-plus-target time, which gives a best-case estimate of 1.47 times if that target cost vanished completely. The observed result is consistent with the unchanged loop accounting for most of the measured work.

The 250,000-item row is a useful reminder not to treat the formula as a stopwatch. It reports a 1.43 times measured speedup against a 1.47 times estimate from separately timed components. Timer noise and function-call overhead can move the rows around; cache effects are another possible, unmeasured factor. Amdahl’s law describes the limit implied by the time split; it does not remove the need to measure the complete programme.

What the law changes in an optimisation review

First, profile the complete path. A hot function is a good suspect, not a verdict. Measure representative requests or jobs, include waiting and data movement where they belong, and write down the time share before changing the implementation.

Second, calculate a ceiling before estimating a payback. If the target owns 12 per cent of the runtime, even an impossible infinite speedup leaves an 88 per cent remainder. A cleaner algorithm can still be worthwhile for memory use, latency variance, maintainability or future scale, but its effect on total runtime has a hard bound.

Third, revisit the time split after each large change. Once a parser is improved, the database call may become the dominant cost. Optimisation changes the shape of the programme, so yesterday’s profile is not a permanent map.

Where it does not settle the question

Amdahl’s law is a fixed-work model. It is useful when the job stays the same and you are asking how much faster it can finish. It says less about systems where extra processors let you process a larger dataset, reduce a queue, or change the algorithm entirely.[4]

It also does not choose the right Python execution model for you. The standard library provides a common interface for asynchronous callables, including thread and process executors.[3] Whether that helps depends on the work, data transfer, scheduling, memory and the rest of the programme. Adding workers to a task with a large serial section may produce more coordination than useful computation.

The practical rule is plain: optimise the part that owns enough time to matter, then measure the whole path again. A spectacular local improvement is still a small change when the rest of the programme is waiting beside it.

Sources

Leave a comment