Amortized analysis

Four million times in a row a Go program appends a number to the end of a slice and times each append separately. On average it comes to about a hundred nanoseconds. But some thirty appends out of the four million take milliseconds, and the longest 57 ms, six hundred thousand times longer than the average: at such moments the slice moves to a bigger piece of memory and copies everything it held. Below is the same measurement on the site's server for four structures.

A Go slice and a Python dictionary behave alike: almost all operations fit in a thin strip at the bottom, and the tallest pillars are moments when the structure was rebuilt whole: 57 ms for the slice when it moved to 3.2 million elements, 75 ms for the dictionary. A Python list grows just as often, but its rebuilds cost almost nothing: its memory is allocated with realloc, which often simply extends the block in place, without copying. And a Go map since version 1.24 is split into small tables and rebuilds them one at a time. Even so, all four have pillars of milliseconds: the Go map has ten, and not one coincides with a rebuild. These are pauses of the machine, not of the structure: the server shares its processor with other programs, and the sandbox in which the code runs hands a program new memory more slowly than an ordinary system. Such pauses do not depend on how the structure is built. And with all that, it is correct to say of all four structures that adding costs O(1) amortized. What that means and what it does not is the subject of this article.

The idea

The amortized cost of an operation is neither the time of one operation nor an average over random inputs. It is a promise about a sequence: any m operations in a row, in whatever order they are called, together cost at most m·c. Expensive operations happen, but they are rare and paid for by the cheap ones before them.

The difference from an average matters. An average bound, like that of quicksort, says: on random data it is usually fast, but a malicious input can spoil everything. An amortized bound guarantees the sum always, on any inputs; there is no randomness in it. But it promises nothing about a single operation: a single append to a slice can cost O(n), and the measurement above shows it.

The word comes from accounting: a large purchase is written off in parts over many years ahead. Where the growth factors of arrays come from, and why twofold rather than by one, is in the article on the dynamic array. Here are three ways to prove such bounds and what they say about real structures.

The first way: add it all up

The most direct way is to count the cost of the whole sequence and divide by the number of operations. A binary counter: we add one to it n times, starting from zero. One increment flips the tail of ones and one more bit: from 0111 to 1000 all four flip. In the worst case that is all the bits of the number. But look at each bit separately.

The sum ⌊n/2⌋ + ⌊n/4⌋ + … can be computed exactly too: it equals n minus the number of ones in the binary notation of n. So a million increments flip exactly 2,000,000 − 7 = 1,999,993 bits, which is what the program below prints. With an array it is the same: if the capacity doubles every time, then by the moment the array holds n elements the copies have cost 1 + 2 + 4 + … + n/2 < n, and together with the writes themselves it comes to less than 2n.

The second way: coins

Adding it all up does not always work: operations differ, and their sequence is not known in advance. Then each operation is assigned a charge, as in a shop: not its real cost but a fixed sum. If an operation costs less than it paid, the difference goes into a piggy bank; if more, the shortfall is taken from the piggy bank. If the piggy bank never goes negative, the sum of the charges is an upper bound on the sum of the real costs. This is the accounting method.

For the counter the charge is two coins. An increment sets exactly one one: it spends one coin on that flip and puts the second on the new one. Erasing the tail of ones is paid for by the coins lying on them. There are always as many coins on the counter as there are ones in it, never fewer than zero, and 2n coins suffice for n increments.

For an array that grows twofold, three coins per append suffice: one pays for the write, two go into the piggy bank. After growing from capacity k to 2k the piggy bank is empty, and before the next growth there will be k appends; they will put in 2k coins, exactly what copying 2k elements costs. Under the chart in the first scene the same count is done on the real growth sequence of a Go slice: you can see which charge suffices and how the piggy bank empties at each growth.

The third way: a potential

The coins can be put not on the elements but on the whole structure: let Φ be a number that depends only on the state of the structure, its “stored energy”. The amortized cost of an operation is its real cost plus the change in Φ. If Φ is zero at the start and never negative, the sum of amortized costs is at least the sum of real ones: all the changes of Φ add up to Φ_end − Φ_start ≥ 0.

With doubling this is 3, with growth by half again 4, and with growth by a factor of 1.25 already 6. This is the choice every language makes: the smaller the factor, the less empty memory the array holds, but the more times each element moves. Go slices grow twofold while they are small, and from a few hundred elements on the factor smoothly decreases towards 1.25. In CPython a list grows by about an eighth: s + s/8 + 6, which the problem on list growth takes apart.

Code

Three factors on a million appends, the smallest sufficient charge, and a check of the formula for the counter:

The charge for growth by 1.25 came out at 6.14, slightly above the theory. The cause is small arrays: a capacity of 1 times 1.25 rounded down is 1 again, and such an array grows by one, copying everything at every append. The theorem about the factor g works when the factor is real, so real implementations start with a larger capacity or grow twofold at first.

The second classic is a queue on two stacks. Push into the “in” stack, take from the “out” stack, and when “out” is empty, move all of “in” into it. A single dequeue may move hundreds of thousands of elements, but each element is moved at most once in its whole life, so there are no more moves than enqueues.

When amortization is not enough

An amortized bound is good when the total time matters: processing a file, computing a report. But sometimes every operation matters. A game has to fit a frame into 16 milliseconds, a server has to answer every client fast, not all of them on average. A five-millisecond pause on one write in a million is a failure for such a system, however little the rest cost. Then the expensive work is split into parts, and this is called deamortization:

• Rebuilding in parts. When its hash table grows, Redis keeps two tables at once, the old and the new, and at every access moves one bucket into the new one, and in idle time as much as it can in a millisecond. No operation pays for the whole rebuild.
• Many small tables. A Go map since version 1.24 consists of tables of at most 1024 slots; when a table fills up, only that one splits in two. The price of one growth is bounded by the size of a table, not of the whole map, and the measurement shows it.
• Garbage collection. The garbage collectors in Go and Java work mostly concurrently with the program and in parts, so as not to stop it for long, for the same reason.

There is also a case where amortization breaks down completely: when you can return to an old state and repeat the expensive operation. The expensive increment of the counter 0111…1 is paid for by coins that piled up for a long time, but if you immediately subtract one and add it again, the coins are gone, and the operation is expensive again. The problem on a back-and-forth counter is built on exactly this. For the same reason amortized bounds carry over badly to persistent structures, where any old version remains available.

What it costs

The analysis itself costs the program nothing; it is a way of reasoning. But the choice between an amortized structure and a structure with a guarantee for every operation is an engineering one: the first is usually simpler and faster in total, the second is needed where the tail of latencies matters, not the average.

Both ways, the accounting one and the potential one, were described in detail by Robert Tarjan in the 1985 paper “Amortized computational complexity”. In the same year Tarjan and Daniel Sleator published splay trees, for which the amortized bound is the main one: a single operation there can be linear, while any m operations cost O(m log n).

Problems

In the first a counter goes back and forth, and the bound “fewer than two flips per operation” stops working. In the second, the exact rule by which a list grows in CPython: how many times it allocates memory and how many elements it copies.