Occasionally Expensive, Usually Free

Last timeSpace Is a Cost As Well

Some operations are almost always instant and occasionally enormous. Averaging the enormous step over the cheap ones around it is the honest accounting, and it is why a growing list stays cheap.

Adding an item to the end of a list is instant. Except once in a while, when

it copies every item it holds into a larger block of memory.

So what does adding an item cost? The worst single add is linear in the whole

list, and saying so would be true and would describe nothing anybody

experiences.

FIG 1Twelve additions to a list that doubles when it fills

step	item added	room before	items copied	running total of copies
1	1st	1	0	0
2	2nd	1	1	1
3	3rd	2	2	3
4	5th	4	4	7
5	9th	8	8	15
6	17th	16	16	31
7	after 17 additions	32		31 copies in total, under 2 per item

7 steps

The rows that are missing from this trace are the point of it: every addition not listed copied nothing at all, because there was already room. Copying happens only at the powers of two, and each copy is twice the size of the one before, which sounds alarming until the running total is read. After seventeen additions the machine has moved thirty one items, under two per addition, and that ratio does not grow. The expensive steps get rarer at exactly the rate they get more expensive, and the two cancel.

FIG 2Every copy ever made, added up

: the number of items in the list at the end
: the total items copied across the entire history of the list
: the copying work charged to each addition once the total is shared out

The geometric sum is doing all the work here. Each term is twice the one before, so the whole series up to n is less than twice its own last term, which means the entire copying history of a list costs less than two copies of the finished list. Shared out over the additions, that is under two moved items each, a constant that does not depend on how large the list grows. This is the argument behind the claim that adding to a list is constant time, and it is worth being able to reproduce, because the same geometric sum appears in hash table growth, in buffer growth and in retry backoff.

FIG 3Total copying work under the two growth strategies

doubling the room when fulladding 100 slots when full

The strategy that grows by a fixed amount looks reasonable and is quadratic: it fills and copies every hundred items, and each copy is larger than the last, so the totals add up like the squares. Doubling is the straight line along the bottom. At twenty thousand items the fixed growth strategy has moved a hundred times more data, and the ratio keeps growing. The choice between these two is a single constant in one line of code, and it moves a list from constant cost per item to linear cost per item, which is the largest consequence per character of code in this course.

What the averaged figure does not promise

It promises a total over a run. It does not promise anything about the one

addition that happened to be the one that copied.

For a service with a limit on every response, that distinction is the whole

problem: the rare quarter second copy is a breached limit no matter how good

the average is. The repairs are to spread the expensive work over the cheap

operations, a little at a time, or to do it in advance while nobody is

waiting. Both are common in systems that publish a worst case promise, and

both cost a little throughput to buy a steadier worst case.

The lesson stops here

1 more paragraph to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

Occasionally Expensive, Usually Free

What the averaged figure does not promise

1 more paragraph to go

This is the reading half

Read alongside