Ranking Optimization Candidates by Expected Payoff

A profile produces a list of expensive things, not a plan. Between the list and the plan sits a judgement that is easy to make badly: which entries to act on. Acting on the largest entry is a defensible default, and it is also frequently wrong, because the largest entry is often the one whose cost cannot be reduced, or whose reduction has already been attempted, or whose apparent size is an artifact of the measurement.

What a plan needs is a single number per candidate that is comparable across candidates and that prices uncertainty explicitly enough to be argued with. Expected saved time is that number, and it decomposes into three quantities that can each be estimated separately.

Decomposing the payoff

For a candidate $i$, let $f_i$ be the fraction of elapsed time the candidate addresses, $s_i$ the factor by which that fraction can realistically be reduced, and $p_i$ the probability that the change reaches the measured workload at all — survives review, passes correctness tests, does not regress a different workload. The expected fraction of total time saved is

$$E[\Delta_i] = p_i \cdot f_i \cdot \left(1 - \frac{1}{s_i}\right)$$

The term $(1 - 1/s_i)$ is the share of the addressed fraction that disappears; at $s_i = 2$ it is one half, at $s_i = 10$ it is 0.9. Written this way, the ceiling from Amdahl’s law appears as the constraint $E[\Delta_i] \le p_i f_i$, and the score is always a fraction of total time rather than a speedup ratio, which makes scores additive across disjoint fractions.

Scores are only useful relative to cost. Dividing by an effort estimate — engineer-days, or the calendar time to reach the default branch — converts saved time into saved time per unit of work, which is the quantity that should be ordered. Dividing instead by risk-weighted effort is better still, since a change with a large chance of being abandoned consumes effort without returning time.

from dataclasses import dataclass

@dataclass
class Candidate:
    name: str
    fraction: float      # measured share of elapsed time
    factor: float        # realistic local speedup, not the ceiling
    probability: float   # chance the change lands and holds
    effort_days: float

    def expected_saving(self) -> float:
        """Fraction of total elapsed time saved, in expectation."""
        return self.probability * self.fraction * (1.0 - 1.0 / self.factor)

    def value(self) -> float:
        """Expected saving per engineer-day."""
        return self.expected_saving() / self.effort_days

ranked = sorted(candidates, key=Candidate.value, reverse=True)

The three inputs have different failure modes, and the score is only as trustworthy as the weakest one.

A small worked example shows why the ranking differs from the profile order. Suppose three candidates are extracted from the same profile: a serialization pass at 35 percent of time which can realistically be halved, a logging path at 20 percent that can be eliminated outright, and a query at 12 percent with a known equivalent that is five times cheaper. With all probabilities at one and efforts of ten, three, and six days respectively, the expected savings are $0.35 \times 0.5 = 0.175$, $0.20 \times 1.0 = 0.20$, and $0.12 \times 0.8 = 0.096$ of total time. Per day they are 0.0175, 0.067, and 0.016. The largest profile entry ranks last on value, and the middle entry ranks first by a wide margin, because elimination has no diminishing-returns term and the effort is small. This is the same asymmetry that removing work rather than accelerating it describes, made arithmetic.

Estimating the achievable factor without inventing it

The factor $s_i$ is where optimism enters. Every candidate, as stated, has a theoretical factor that is unachievable: “replace the sort” implies $O(n \log n) \to O(n)$, but the keys still have to be scanned, the output still has to be written, and the constant factors of a simpler algorithm are not zero. The realistic factor is bounded by the remaining irreducible work in the region, which is why a factor estimated from the shape of the code is more defensible than one estimated from the ambition.

Three anchors produce a defensible factor.

The first is an existing implementation elsewhere in the system. If the same operation is already fast in another path, the difference between the paths bounds what closing the gap would yield. This is a measurement, not a guess, and it is the strongest anchor available.

The second is the instruction and memory cost of the minimal version. If the region executes $N$ instructions per operation and the minimal version needs $M$, the factor is at most $N/M$ before accounting for memory stalls. Order-of-magnitude reasoning is enough here; the goal is to separate a factor of 1.2 from a factor of 5, not to predict 3.4.

The third is the ceiling that the surrounding structure imposes. A region that is 30 percent of time and is called from a loop whose iteration count is set by an external system cannot be made arbitrarily cheap, because the external system’s latency remains. Where the honest answer is “larger than the noise floor but not by much,” recording a range rather than a point estimate is more useful than recording a confident wrong number.

The probability term is not a fudge factor

Multiplying by $p_i$ looks like hedging. It is not: it encodes a real property of candidate sets. Candidates differ in how likely they are to survive, and the differences are systematic.

A candidate that has been attempted before and reverted has a low prior unless the previous attempt failed for a reason that no longer applies. A candidate that requires changing a public interface carries the cost of every caller and the probability that some caller cannot absorb the change. A candidate whose benefit depends on a workload property that is not guaranteed — request sizes, key distributions, hit rates — has a probability equal to the fraction of traffic exhibiting that property. A candidate that relies on a compiler transformation has a probability that the transformation fires on the actual code after inlining.

These are estimable, if roughly. The alternative to writing them down is to let them operate invisibly: the largest entry wins the argument, ships, and yields a small fraction of its predicted gain because the distribution it optimized was not the distribution in the trace. The workload-mix objective article treats the distribution question directly, since a candidate that helps the wrong part of the mix is a candidate whose $p_i$ is effectively zero for the metric that matters.

One probability deserves separate attention because it is routinely set to one and is routinely much lower: whether the addressed cost is even on the path that the metric measures. A candidate that optimizes a parallel branch with slack has $p_i$ near zero for latency and near one for capacity. The critical path analysis decides which of those two the candidate belongs to, and therefore which metric its fraction should be measured against.

Effort estimates and the cost of delay

Dividing by engineer-days is the standard conversion, but effort is not the only cost. A change that touches a shared data structure creates future cost for every change that follows; a change that special-cases a workload creates a branch that must be tested forever. For candidates of similar score, the one with the smaller surface is preferred, because the score measures the benefit and the surface measures the debt.

Calendar time matters separately when the benefit accrues over time. A 1.3x improvement that ships this quarter and a 1.4x improvement that ships next year are not ranked by ratio alone; the earlier one returns its saving for three extra months and, more importantly, changes the profile against which later candidates are evaluated. This favours short, independently shippable changes over large ones even when the large one scores higher in isolation, because each shipped change reorders the remaining list with real data.

When scores are close enough to be tied

The ranking is only meaningful to the precision of its inputs. A fraction measured from a profile with a few hundred samples carries a sampling error of roughly $1/\sqrt{n}$ on each bin; with 400 samples, a bin at 20 percent has an uncertainty of about two percentage points in absolute terms. An effort estimate of “two days” is uncertain by a factor of two on a good day.

The consequence is a rule: candidates whose scores differ by less than the propagated uncertainty should be treated as tied and ordered by a secondary criterion — smaller surface, fewer dependencies, ability to be measured in isolation. Sorting a list of noisy estimates and treating the top entry as the single correct answer is a way of amplifying noise, and it produces plans that are confidently wrong. The plateau discussion returns to this point, since once candidate scores cluster within noise, further ranking work has no expected value.

A related discipline is to record the estimate alongside the outcome. Expected saved time, predicted before the work starts, compared against measured saved time afterwards, is the only calibration signal available; without it, the estimate’s bias is learned slowly and by argument rather than by record.