Dynamic array

A Python program calls lst.append(x) a million times and never says how many elements there will be in all. But the computer hands out memory in blocks of a length known in advance, and a block cannot simply be lengthened if something else lies right after it. The list gets round this by keeping spare room, and when the room runs out it asks for a new, bigger block and carries everything it has accumulated into it. Below are real measurements from this site's sandbox: how a Python list and a Go slice grow over a million appends, and for comparison three growth rules computed by formula.

The stepped line is the capacity: how many cells are allocated. The dashed line is how many are used. Each bar is a move, and its height equals the number of elements carried: a move carries everything. Some of the Python list's bars are grey: there the block grew in place, more on this below. The bars get more expensive but sparser, and on the lower graph the average cost of one append levels off for all rules except “+1000”. There the capacity grows not by a factor but by a constant addition, and the average cost creeps up without end: by a million it is five hundred copies per append.

The idea

Keep the elements in an ordinary array with spare room: the size is how many are used, the capacity how many are allocated. While there is room, append writes to the next cell. When there is no room, set up an array r times larger and copy everything into it. Since the capacity grows geometrically, moves are so rare that their total cost is at most a constant per element added.

Everything else comes free from the ordinary array. The elements lie in memory one after another, and the address of the i-th is the start plus i times the element size, so access by index costs one action, however large the array. Neighbouring elements lie side by side, and the processor reads them in whole cache lines: going over an array is faster than over almost any other structure. How an array is laid out in memory and why a Python list stores not numbers but references to them is taken apart in detail in the course chapter on arrays and lists.

Why O(1) on average

An append that triggered a move costs O(n): n elements must be carried. The promise of “O(1)” refers to the average over any sequence of operations: this is the amortised cost (more in the article on amortised analysis). It is not about luck or random data: the bound holds for any sequence of appends, with no probability involved.

The same conclusion can be told as bookkeeping. Let each append under doubling pay three coins: one for writing itself, two put aside. By the time capacity C is used up, C/2 elements have been added since the last move and put aside C coins, exactly what it costs to carry all C elements. The account never goes negative, so three coins per operation are always enough.

And now “+1000”. Moves happen at 1000, 2000, 3000 elements, by n elements there are about n/1000 of them, and 1000 + 2000 + … ≈ n²/2000 elements are carried. That is O(n²) for n operations, O(n) for each on average. It does not matter whether the addition is a thousand or a million: a constant addition only postpones the square, it does not cancel it. In the scene, over a million appends the rule “+1000” carried 499,500,000 elements, and doubling 1,048,575.

Which factor to choose

The proof shows that the factor is a trade-off. A large r means fewer copies (from 1/(r − 1) to r/(r − 1) per append on average) but more idle memory: right after a move only the share 1/r of the capacity is used. Real languages settle this trade-off differently:

The numbers for Python and Go are measured, for Java and ×2 computed by their rules; all of them are in the first scene. Python looks wasteful: more than eight copies per element. But it copies eight-byte references in one solid piece, and above all it often does not copy at all. It asks the system to lengthen the block with the function realloc, and if the memory right after the block is free, the block grows in place. In our measurement, of the list's 85 moves over a million appends the buffer actually changed its address 42 times, in another run 35. A comment in the CPython source says just that: the over-allocation is mild, but even with a poorly performing realloc it is enough for linear time in total. Go does not lengthen its memory like this: every move of a slice is a new block and a copy (35 out of 35).

There is also an argument against the factor 2, about reusing memory. With doubling each new block is larger than all the previous ones taken together: 1 + 2 + … + 2^k < 2^k+1. The pieces freed behind will never hold the next block, and the array creeps forward through the addresses. With a smaller factor, after a few moves the freed pieces add up to a large enough hole, and the block returns to the start. Strictly speaking, if the old block is freed only after the copying, r must be less than the golden ratio φ ≈ 1.618: the condition 1 + r + … + r^k−1 ≥ r^k+1 reduces for large k to r² − r − 1 < 0. The authors of fbvector in the Folly library rely on this argument, and chose the factor 1.5.

The model here is ideal: the allocator puts a block into the first suitable free place and merges neighbouring holes. Real allocators put blocks of different sizes in different areas, so the gain from 1.5 is smaller in practice than in the picture. But the direction is right.

The trap: shrinking

If an array can grow, one wants it to be able to shrink too: 90 % of the elements were deleted, give the memory back. The most obvious rule, “halve when half is used”, breaks the whole amortisation. Take a full array of 8 elements and push and pop in turn:

push overflows the array, and it moves into 16 cells. pop leaves 8 of 16, exactly half, and the array moves back into 8. Every operation carries all the elements, and its cost is no longer O(1) but O(n). The cure is a gap between the thresholds: grow when full, and halve when a quarter is used. After any move the array is about half full, and before the next move in either direction at least n/4 cheap operations are needed; their saved coins pay for the carrying. This is how the table in the textbook by Cormen and co-authors shrinks, and so does the listing below.

Python shrinks a list when less than half is used, but takes the new size by the same growth formula, with an eighth to spare: there is a gap, and the seesaw does not rock it. A Go slice never shrinks. s = s[:0] keeps the capacity as it was, and that is convenient: the buffer can be reused. But a common leak sits right here: a small slice cut from a huge one keeps the whole huge array in memory. If ten elements are needed from a gigabyte buffer, copy them: slices.Clone(big[:10]).

Code

A dynamic array assembled by hand. Underneath is a block of constant length: in Python a list created at the needed size at once, in Go a slice that never grows by itself. A move is an explicit copying loop, and the program counts how many elements it carried:

The last lines of the output are the same theorem in numbers:

n =   1000: 10 moves,   1023 copied, 1.02 per append,    24 cells spare
n =  10000: 14 moves,  16383 copied, 1.64 per append,  6384 cells spare
n = 100000: 17 moves, 131071 copied, 1.31 per append, 31072 cells spare

There are always fewer than two copies per append, while the spare room wanders from 2 to 39 % of the capacity: it depends on how far the next move is. And here is how the real list and slice grow. The program adds an element a million times and prints each move: the new capacity, by what factor it grew and whether the buffer changed its address. In Python the buffer's address is obtained through ctypes, which is done only for an experiment like this. Run it several times: the capacities are always the same, while “moved” or “grew in place” changes from run to run.

What it costs

Memory is O(n) with spare room up to (r − 1)/r of the capacity: with doubling, at the worst moment half the cells stand empty. Plus, in Python, the objects themselves: a list stores eight-byte references, and each number is a separate object in memory.

Amortisation is a promise about the sum, not about each operation. An array of a hundred million eight-byte elements copies 800 megabytes on a move, and that very append may fall at the moment the program must answer a user. If the size is known in advance, the room is reserved at once: make([]T, 0, n) in Go, reserve in C++, new ArrayList<>(n) in Java. The measurement below is the cost of one append when growing from zero and with room allocated in advance:

Both lines are horizontal on the whole: this is O(1) amortised, visible to the eye. In Go growing from zero costs several times more than room allocated in advance: each element bears its share of moves and memory allocations. In Python there is almost no difference: writing by index into a ready list is now slightly faster, now slightly slower than append. The interpreter spends more on each line of the loop than all the moves cost together.

Where it is used

Almost everywhere a program says “list”. list in Python, slices in Go, ArrayList in Java, std::vector in C++, Vec in Rust, arrays in JavaScript are dynamic arrays with different factors. Other structures stand on them: a stack is a dynamic array of which only the end is touched; a binary heap lives in an array, and a hash table grows by exactly the same law with the same proof.

The weak spot is insertion at the start and in the middle: to free a cell, the whole tail has to be shifted. For a queue this means that list.pop(0) in Python costs O(n), and collections.deque, which works fast with both ends, is used instead. For a text editor that inserts characters in the middle of a megabyte file, the rope and the gap buffer were invented. And a linked list inserts in the middle in O(1), but loses to an array on scanning because of the cache.

History

Growing tables with doubling turned up in programs long ago, but the word for their cost appeared later. In 1985 Robert Tarjan, in the survey “Amortized Computational Complexity”, described how to bound not each operation separately but their sum over the whole sequence, and showed two ways of such accounting: the banker's, with saved coins, and the potential method. The rule “grow when full, shrink at a quarter” became a classic example of such analysis; it is taken apart, for example, in the textbook by Cormen, Leiserson, Rivest and Stein.

Problems

In the first problem you predict the growth of a real Python list for any number of appends, up to 10¹⁸, which one-by-one simulation cannot reach in time. In the second a warehouse now rents a bigger hall, now moves to a smaller one, and you count how many boxes are carried under two moving rules.