The Work That Disappears

On mathematical optimization, programming, and the pleasure of understanding what is necessary.

I find it difficult to leave a repeated calculation alone. Once I have noticed that its answer is already available somewhere, I start wondering why the program needs to ask again.

That instinct is good at finding puzzles. It is less reliable at finding bottlenecks. I can spend an hour removing work that costs almost nothing, or make a piece of code shorter and leave it harder to understand.

The improvements I enjoy most change what I can explain about a program. I can point to a set of possibilities it no longer explores and say why none of them can help. I can account for an intermediate result that no longer needs to exist. There is less uncertainty in the design, as well as less work in the execution.

A smaller running time matters. But so does understanding what made it possible.

What a better answer owes us

Before comparing two implementations, we have to decide what counts as an improvement. Average running time, the longest acceptable delay, and memory use are different objectives. The output may have to remain identical; the inputs we care about may be only part of the space the program accepts. A faster implementation that silently abandons a requirement has changed the question.

Mathematical optimization makes those commitments explicit: here are the choices, here is how we compare them, and here are the constraints a choice must satisfy. Once those are written down, better becomes a claim we can examine. [1]

Consider ten units to distribute between two destinations, with this cost model:

Minimize x² + 4y², subject to x + y = 10 and x, y ≥ 0.

Equal shares cost 125. We could try other allocations and see how far the number falls. The constraint gives us a more conclusive route: for every feasible allocation, we can rewrite the cost as

x² + 4y² = 80 + (x − 4y)² / 5.

The useful part of that square is its sign. It cannot be negative, so no feasible allocation can cost less than 80. Choosing x = 8 and y = 2 makes the square zero and reaches the bound.

We now have both an answer and a reason to stop. Finding an allocation that costs 80 would, on its own, leave open the possibility of something better. The lower bound closes that possibility. It rules out an entire region of the search without asking us to visit it.

Convex optimization develops this kind of reassurance further: when the objective and feasible set are convex, every local minimum is global. Duality gives us another way to certify an answer: a valid lower bound proves a feasible solution optimal when their values agree. Neither idea makes every optimization problem easy. Each tells us what structure would let us reach a definite conclusion. [1]

What the future needs to remember

Finding an optimal answer and optimizing the program that finds it are different tasks. A scheduling problem lets us watch them meet.

Each job has a fixed start, a fixed end, and an integer value. Only one job may run at a time, and we want the compatible selection with the greatest total value. A job ending at time five may be followed by one starting at time five: the intervals include their start and exclude their end.

Taking the most valuable job first is tempting. But a job running from zero to five and worth ten loses to two smaller jobs: zero to three for five, then three to five for six. We could settle the matter by checking every subset. With n jobs, that means 2ⁿ candidates.

The way out starts with an order. Sort the jobs by finishing time, and consider the last job in the list. If we take it, every earlier job that could precede it lies in a compatible prefix: all the jobs ending no later than it starts. We only need the best schedule within that prefix. If we leave it out, we need the best schedule among the remaining jobs.

Numbering the sorted jobs from one, let best[j] be the largest total value available among the first j jobs. Let p(j) be the number of earlier jobs ending no later than job j begins. The two choices become:

best[0] = 0
best[j] = max(best[j - 1], value[j] + best[p(j)])

This is the standard weighted interval scheduling recurrence. Its justification is exhaustive without being an exhaustive search: every solution either includes job j or excludes it, and both cases lead to smaller problems of the same form. [2] [3]

The interesting compression is in what we no longer ask about the past. For deciding whether to take job j, a compatible earlier schedule matters through the value it contributes. We do not need every history that could produce that value. We can recover a particular history afterward, when we reconstruct the chosen schedule. [3]

The implementation below returns both the optimal value and a schedule achieving it. Sorting and binary searches take O(n log n) time; the recurrence and reconstruction take O(n). Storage is O(n), under the usual model that treats integer comparisons and arithmetic as constant-cost operations. [2]

from bisect import bisect_right
from collections.abc import Iterable
from dataclasses import dataclass


@dataclass(frozen=True)
class Job:
    start: int
    end: int
    value: int

    def __post_init__(self) -> None:
        if any(type(x) is not int for x in (self.start, self.end, self.value)):
            raise TypeError("Job fields must be integers.")
        if self.start >= self.end:
            raise ValueError("A job must end after it starts.")


def optimal_schedule(jobs: Iterable[Job]) -> tuple[int, list[Job]]:
    ordered = sorted(jobs, key=lambda job: job.end)
    ends = [job.end for job in ordered]
    previous: list[int] = []
    best = [0]

    for i, job in enumerate(ordered):
        # This prefix length is also an index into best.
        prefix = bisect_right(ends, job.start, 0, i)
        previous.append(prefix)
        best.append(max(best[-1], job.value + best[prefix]))

    chosen: list[Job] = []
    i = len(ordered)
    while i:
        if best[i] == best[i - 1]:
            i -= 1
        else:
            chosen.append(ordered[i - 1])
            i = previous[i - 1]

    chosen.reverse()
    return best[-1], chosen


jobs = [Job(0, 3, 5), Job(3, 5, 6), Job(0, 5, 10), Job(5, 6, 2)]
score, schedule = optimal_schedule(jobs)
assert score == 13
assert schedule == [jobs[0], jobs[1], jobs[3]]

Forgetting is safe only after we have identified what the future can depend on. Add a rule that consecutive jobs require setup time depending on their identities, and a prefix’s best value no longer tells us enough. We would also need to know which job came last. The state would have to change.

An order worth keeping

The scheduler uses finishing-time order to make compatible prefixes easy to find. Sometimes an order is useful often enough that we choose to maintain it in advance.

Consider a SQLite query that asks for one owner’s events, ordered by start time:

CREATE TABLE events (
    id INTEGER PRIMARY KEY,
    owner_id INTEGER NOT NULL,
    starts_at INTEGER NOT NULL
);

CREATE INDEX events_by_owner_and_start
    ON events(owner_id, starts_at);

EXPLAIN QUERY PLAN
SELECT starts_at
FROM events
WHERE owner_id = 7
ORDER BY starts_at;

The ORDER BY is still there. The index makes it possible to satisfy it without a separate sort.

Index entries are ordered first by owner, then by start time. SQLite can locate one owner’s entries and walk through them chronologically. The requested column is already in the index, so this query need not consult the table either. It is a covering index: the representation contains everything the query needs. [5]

For this schema and query, a local check with SQLite 3.46.1 produces:

SEARCH events USING COVERING INDEX events_by_owner_and_start (owner_id=?)

There is no separate sorting step in that plan. This is the kind of change I want to see in EXPLAIN QUERY PLAN, rather than infer from how economical the SQL looks. [5]

Of course, maintaining the order is work too. The index takes space and must be updated as the data changes. Whether that exchange is worthwhile depends on the workload. The requested order has become part of the representation, and we pay to keep it there. [5]

The program does not need a cleverer answer to “how should I sort these rows?” It needs to notice when that question has already been answered.

Doing more arithmetic to finish sooner

The index earns its space by saving later work. That makes the next example awkward for my dislike of repeated calculations.

A conventional dense-attention implementation stores a large matrix of interactions between sequence positions. Keeping that result sounds sensible. Using it later, however, means moving data between the GPU’s larger memory and its smaller, faster on-chip memory. Those transfers have a cost. [6]

The original FlashAttention algorithm works in blocks and avoids materializing the full attention matrix in the larger memory. During training, it deliberately recomputes some intermediates instead of retrieving them. In the authors’ experiments, the extra arithmetic accompanied faster execution because it reduced expensive memory traffic. [6]

The repeated calculation has earned its place: fetching a saved value can cost more than producing it again. [6]

For a fixed head dimension, dense attention’s arithmetic remains quadratic in sequence length. FlashAttention has not made those interactions disappear. It has changed where data lives and when it is needed. [6]

Remembering helped the scheduler; recomputing helped this GPU algorithm. The apparent contradiction disappears once we name the resource each technique saves. Counting arithmetic alone would miss the reason to prefer the second design.

This is where a cost model has to resemble a machine. Some of the most expensive work may be work our equations barely mention.

The promise inside a transformation

Memory traffic is not the only place where a mathematical description can miss the machine. Even rearranging an addition can change the answer.

a, b, c = 1e16, -1e16, 1.0
print((a + b) + c)  # 1.0
print(a + (b + c))  # 0.0

Over the real numbers, those expressions are equal. In ordinary binary64 floating-point arithmetic, rounding makes the grouping observable. The first expression cancels the large values before adding one. In the second, adding one to the large negative value rounds back to that value, and the final addition produces zero. [7]

A transformation justified in real arithmetic therefore needs a second justification before being applied to floating-point code. LLVM makes the distinction explicit: its reassoc fast-math flag permits algebraically equivalent transformations that may substantially change floating-point results. [8]

The same distinction applies to FlashAttention. Computing exact attention is not, by itself, a promise of identical floating-point bits. Equivalence in real arithmetic does not guarantee identical floating-point results. [6] [7]

There is nothing inherently wrong with accepting a controlled numerical difference. But the tolerance must belong to the specification. It cannot be invented after a benchmark improves.

Before changing an implementation, I want to know what it owes its caller. Sometimes that is identical output. Sometimes it is an error bound. Sometimes the order of otherwise equal results matters. These details define which transformations are available to us.

Where attention belongs

A tenfold speedup is easy to like. Its importance becomes clearer when we ask how much of the program it affects.

Suppose the part we improve accounts for 10% of a fixed workload’s original running time. Make it ten times faster, leaving everything else unchanged and adding no overhead, and its contribution falls to 1% of the original total. The other 90% is still there. The whole program now takes 91% of its former time: an overall speedup of about 1.10.

Even making that part instantaneous would leave 90% of the time untouched. The best possible overall speedup would be 1 / 0.9, approximately 1.11. [9]

Amdahl’s argument about the limits of parallel execution gives the general form of this fixed-workload calculation. If a fraction p of the original running time belongs to the improved part, and that part becomes s times faster under the same assumptions, then:

overall speedup = 1 / ((1 − p) + p / s). [9]

I appreciate this limit because it puts a boundary around my own attention. The code that keeps attracting me is not necessarily the code that deserves another evening.

Knuth’s discussion of optimization makes room for both restraint and care. He warns against pursuing efficiencies in noncritical code while defending worthwhile improvements in the parts identified as important. Measurement is what lets us distinguish the two. [10]

What we count in that measurement matters. Python’s timeit excludes setup from the timed section and disables garbage collection by default. Those are useful conditions for some experiments, but they can leave out costs an application still has to pay. Repeated measurements help reveal timing interference; they do not make an unrepresentative workload representative. [11]

For the scheduler, I would vary both the number of jobs and their pattern of overlaps, and include sorting in an end-to-end comparison. I would also check the selected schedules against exhaustive search on small inputs before timing larger ones. For the indexed query, I would count the cost of maintaining the index if writes matter to the application.

“Faster” should tell a reader what was measured, what was preserved, and which costs were counted.

A stopping condition for the programmer

A program can meet its requirements and still leave me thinking about another improvement. There is no obvious end to that kind of attention.

Multiple objectives make the word optimal more modest. A Pareto-optimal choice is one for which no feasible alternative improves an objective without worsening another. There may be many such choices; the definition alone does not select the trade-off we should prefer. [1]

That leaves room for judgment. I might accept a little more memory to make a latency requirement dependable. I might keep a slower implementation because the faster one would be difficult to verify and the difference is irrelevant to its use. Those decisions need reasons, but they need not apologize for declining the smallest number on a chart.

I also want room to study an optimization simply because it interests me. An evening spent understanding why a recurrence works can be worthwhile even when no application needs the result. Curiosity and engineering have different stopping conditions. Confusing them makes a learning exercise look like a delivery failure, or makes a private fascination look like a product requirement.

The beauty I am looking for survives that distinction. It is there in the allocation whose lower bound meets its cost, in the scheduling state that remembers exactly enough, and in the data arrangement that makes a later operation unnecessary.

After a good optimization, I want to be able to explain both the answer and the absence of the work we removed. The program still owes its caller the same promise. We have understood enough to keep it with less.

Sources