What a program costs

At the end of the last chapter, every time we packed the island twice as densely, it ran four times slower: sixteen thousand rabbits cost almost a second a day, and a hundred thousand would cost half a minute. We asked why, and whether we could have known in advance. Chapter 0 asked the same thing on a larger scale, as the second of the course’s big questions: why does one program solve a problem in a second while another wouldn’t finish before the end of the universe? The story starts with a player who got tired of waiting.

Six minutes

The first rule of an investigation is to measure before you guess. “The game is complex” and “it’s the network” are guesses. Four minutes on one core while the disk and the network are silent is evidence: the processor is computing something, for a long time and on its own. The hardware has nothing to do with it; everything depends on how the program computes. Before we explain anything, then, we too will learn to time things.

The stopwatch

Python’s stopwatch is the function time.perf_counter(): it returns the time in seconds since some starting point, and the difference between two calls tells you how much time has passed. But a single number says little. Is 0.4 seconds fast or slow? Far more telling is how the time changes as the input grows, so we measure at several sizes, doubling each time. Here is a function that looks for duplicates in a list the most direct way, comparing every item with every other, like the loop inside a loop in Chapter 4.

Each doubling makes it four times slower. This technique is worth remembering: watch the ratio of the times. If doubling the input doubles the time, the work grows in proportion to $n$; if it quadruples, the work grows as $n^2$; if it goes up eightfold, as $n^3$. The seconds depend on the computer, the ratios on the algorithm.

For fast operations that take microseconds, one measurement drowns in noise: everything else the machine is doing at the same moment affects the time. The cure is to repeat the operation many times and divide the total by the number of repetitions. That is what the timeit module does.

The sum and the search in the list grow tenfold with every tenfold growth of $n$: to add up all the numbers, or to make sure that $-1$ isn’t among them, you have to visit each one. The search in the set doesn’t grow at all. On a million items it takes as long as on ten thousand, a few hundredths of a microsecond. In Chapter 8 we saw this difference on War and Peace; now you can see how it grows.

The next stopwatch takes these measurements for you. Type the body of a function f(data), and the server will call it on lists of random numbers of length one thousand, two thousand, four thousand and so on, until a single call takes about a second, and draw a graph. Both scales are logarithmic: on such a scale $n^k$ turns into a straight line with slope $k$, and you can see the slope at a glance.

Hot spots

Timing the whole program is not enough: the game has millions of lines, and you need to find the ones that burn the time. That is the job of a profiler. t0st had no source code for the game, so he used a simpler kind of profiler, a sampling one. At regular intervals it peeks into the running program, notes which function is executing and who called it, and keeps a tally. Whichever function is caught at work most often over the four minutes is the one holding the game back. t0st knew of only one such profiler for Windows, Luke Stackwalker, and it “hasn’t been updated in over 10 years.” Still, it did its job: it found two hot spots.

Python comes with a profiler built in: the cProfile module counts how many times each function is called and how much time is spent in it. Here it is on our island from the last chapter, for one day with eight thousand rabbits and eight hundred foxes.

The ncalls column says how many times a function was called, tottime how many seconds were spent in the function itself, and cumtime the same plus everything it called. The culprit is plain to see: rabbit_at. It was called only 800 times, once per fox, yet it ate up almost the whole day. And isinstance was called more than six million times. Where do so many calls come from?

Remember how a fox looks for a rabbit in its cell: rabbit_at walks through the whole list of animals until it finds one. Usually there is no rabbit in the cell, and the fox checks all 8,800 animals. Eight hundred foxes make about seven million checks. Now double the population: there are twice as many foxes, and each one checks a list twice as long. That is four times as many checks, hence “twice the animals, four times the day.” If foxes are a tenth of the animals, then with $N$ animals there are about $\frac{N}{10} \cdot N = \frac{N^2}{10}$ checks: a square.

Not a single line of the island is wrong. The mistake is in the price: one walk through the list is cheap, but it is repeated for every fox. Linear work repeated a linear number of times gives a square. Remember this rule: in GTA it will strike twice.

Clue one: strlen

The profiler gave t0st addresses in the machine code but no names: the game guards itself against tampering, and its code is scrambled. t0st dumped the game’s memory in the middle of loading (code has to be unscrambled to run) and took the copy apart with a disassembler. One of the hot addresses had a name: strlen, the standard C function that counts the length of a string. It was being called by a text-parsing function, by all appearances sscanf. And the text it was parsing was JSON: ten megabytes of it, the catalog of the in-game store, some 63 thousand items you can buy in the game. One item looked like this:

What could be expensive about counting the length of a string? In C, a string is a row of bytes in memory, with its end marked by a zero byte. The string doesn’t remember its own length. To find it, strlen starts at the beginning and counts bytes until it meets the zero, and for a ten-megabyte string that is ten million steps. And many implementations of sscanf, asked to read one number from the current position, begin by calling strlen on everything from that position to the end of the catalog. Read a five-digit number, and you have run through megabytes. The next number: megabytes again, slightly fewer.

If a string of length $L$ holds $K$ values spread evenly along it, parsing them makes strlen run through about $K \cdot \frac{L}{2}$ bytes in total, the area of that orange triangle. A catalog twice as big has twice as many values, and each costs twice as much: four times as long. Linear work repeated a linear number of times, once again. “To be fair,” t0st admitted, “I had no idea most sscanf implementations called strlen so I can’t blame the developer who wrote this.”

Python strings do remember their length: len(s) reads a number that is already stored. But the same trap is easy to set here too. Below is a catalog parser that cuts off what it has read after every number: text = text[j:]. A slice is a new string, a copy of the whole tail, which means the same run to the end as strlen makes. Next to it is the same parser keeping track of its current position instead.

The answers are the same, but the times grow differently: the second parser’s time doubles with each doubling, the first one’s comes closer and closer to quadrupling. On a small catalog the difference is hundredths of a second, because a machine copies a megabyte of memory very quickly. The square wakes up on big data, and the GTA catalog weighed ten megabytes.

Clue two: the duplicate check

The second hot spot sat right next to the first. The game puts every parsed item into an array of pairs: the item’s hash and a pointer to the item itself. A hash is a number that serves as the item’s ID. But before putting an item in, the game checks whether it is already in the array. It checks by walking the array from the start and comparing the hash with every entry.

The first item has nothing to compare against, the second is compared with one entry, the thousandth with nine hundred and ninety-nine. For $n$ items that makes

comparisons. This is the sum that, as legend has it, little Gauss worked out in his head. t0st counted a little more generously, $\frac{n^2+n}{2}$, and for 63 thousand items got 1,984,531,500 checks, nearly two billion, “if my math is right.” The two formulas differ by 63 thousand comparisons out of two billion, which changes nothing.

And here is the most galling part. The array is empty before loading, and every item in the catalog is different. The check could never find a duplicate, and the game even had a function that inserts an item without checking. t0st’s comment was short: “You have unique hashes why not use a hash map.” Here is the same experiment in Python: loading a catalog with the check against a list, and with the check against a set.

Each doubling quadruples the time, and the last line forecasts 63 thousand items without waiting for them: the time at 16 thousand, multiplied by the square of the ratio of sizes. Fifteen to twenty seconds in Python; by t0st’s measurements, this check cost the game a minute and a half. The set handles everything in milliseconds, because its in doesn’t go through the items. The coming chapters explain how it manages that.

The patch

t0st had no source code, so he made his fix from the outside. He wrote a small library that can be injected into the running game, and through it replaced two functions. The new strlen, when it meets a very long string, remembers where the string starts and how long it is; asked later about a position inside that string, it answers with a subtraction instead of running anywhere. The new catalog insert puts an item in at once, without the check. Then he timed the result:

Loading time fell by $\frac{360 - 110}{360} \approx 69.4\,\%$. On February 28, 2021, t0st published his investigation under the title “How I cut GTA Online loading times by 70%.” The post reached the top of Hacker News and went around the world. On March 15, t0st reported that Rockstar had promised a fix soon and had paid him \$10,000 through its bug bounty program, as an exception: the program usually pays only for security issues. The next day a game update came out, and t0st, having tested it on the same computer, wrote: “Fully fixed!”

As on the island, not a single line was wrong: each did what it was supposed to, but cost more than it seemed to. On a test catalog of a hundred items the square costs milliseconds, and nobody notices it. Make the catalog a hundred times bigger, and the square grows ten thousand times. To catch such things before the players do, you need to learn to estimate a program’s cost from its text, without a stopwatch.

How functions grow

Both clues, like the island, come down to one thing: how the number of steps grows with the size of the input, $n$. This is called the complexity of an algorithm. A few kinds of growth turn up so often that they have names:

• constant time, $1$: the number of steps doesn’t depend on $n$, as when you take a list item by its index or check in on a set;
• logarithmic, $\log n$: double the input and one step is added; this is how the binary search from Chapter 0 works, a million possibilities in twenty questions;
• linear, $n$: visit every item once, as a sum, a maximum or an in on a list does;
• $n \log n$: good sorting algorithms, such as merge sort from the race in Chapter 0;
• quadratic, $n^2$: every item against every other, as in bubble sort, a brute-force duplicate check, the foxes on the island;
• exponential, $2^n$: every new item doubles the work, as in going through all subsets, or the naive recursive fib.

Here and below, logarithms are base 2, although in these estimates the base doesn’t matter (you’ll see why shortly). In numbers, these functions look like this:

An ordinary processor does on the order of a billion simple operations a second. At that rate $n^2$ on a million is $10^{12}$ operations, about a quarter of an hour, while $n \log n$ takes twenty milliseconds. And $2^n$ at $n = 100$ is already $10^{30}$ operations: $4 \cdot 10^{13}$ years, three thousand ages of the universe. Try other combinations yourself.

Switch the machine’s speed to the supercomputer. The fastest supercomputers of the mid-2020s perform on the order of $10^{18}$ operations a second, a billion times more than a laptop. For $n^2$, this means that in the same time you can take an input $\sqrt{10^9} \approx 31\,600$ times larger. For $2^n$, it means that $n$ can grow by 30, since $2^{30} \approx 10^9$. A billionfold speedup pushes the exponential wall back by only thirty steps.

Big O

Counting steps rarely gives a tidy formula. The duplicate check makes $\frac{n(n-1)}{2}$ comparisons, plus one assignment per turn of the outer loop, plus some setup: something like $0.5\,n^2 + 2n + 7$. But for large $n$ the term $0.5\,n^2$ swamps everything else: at a million it is two hundred and fifty thousand times bigger than $2n$. And the factor $0.5$ depends on what counts as one step, on the language and on the processor. So the convention is to drop both the lower-order terms and the constant factors and say that the duplicate check runs in $O(n^2)$, “big O of n squared.”

In plain words: $O$ means “grows no faster than,” up to a constant factor and from some point on; $\Omega$ means “grows no slower than”; $\Theta$ means “grows like.” The number $n_0$ lets a function behave however it likes for small $n$: what interests us is what happens when there is a lot of data.

Pick $c$ and $n_0$ yourself. Then take a $g$ that grows more slowly than $f$: now no $c$ can save you, and sooner or later a violation turns up.

The definition shows at once why the base of the logarithm doesn’t matter. $\log_{10} n = \frac{\log_2 n}{\log_2 10} \approx 0.3 \log_2 n$: logarithms to different bases differ by a constant factor, and $O$ doesn’t see constant factors. How logarithms work is explained in detail in our math course, which also shows, in “The main heat,” why any exponential function sooner or later overtakes any power function.

One more subtlety. $O$ is an upper bound, and formally it is true that summing a list takes $O(n^2)$: it is certainly no slower than a square. But nobody talks that way. Calling a linear algorithm “$O(n^2)$” is like answering “how long is the drive?” with “less than a year.” When people say “$O(\ldots)$,” they usually mean the tightest bound, which strictly speaking is $\Theta$.

Guess the complexity

A few rules help you estimate complexity from a program’s text. Blocks that follow one another add up, and the heaviest one wins: $O(n) + O(n^2) = O(n^2)$. Nested loops multiply: an outer loop of $n$ steps around an inner loop of $n$ steps gives $n^2$. A loop that halves $n$ every time makes $\log n$ steps. And then there is the rule GTA broke: every line has a price, even when it looks like a single operation. x in a_list, s[i:], sorted(a), a_list.insert(0, x), sum(a): each of them walks through the data. Put such a line inside a loop and you get a square.

The exponential

In Chapter 9 we saw that the recursive fib(n) becomes eleven times slower with every five units of $n$. Now we can do the exact count.

So $T(n)$ grows exponentially, somewhere between $1.41^n$ and $2^n$, and to be exact, as $1.618^n$, where 1.618 is the golden ratio Chapter 9 talked about. Measure the price of one call, and the rest can be predicted.

Forty takes ten-odd seconds, fifty about half an hour, sixty a couple of days, eighty a human lifetime, a hundred more than a million years. And fib(120), computed by recursion, would run longer than the universe has existed. All this for numbers that the loop from Chapter 9 finds in microseconds. The exponential lives in the algorithm, not in the problem: the algorithm solves the same subproblems billions of times. How to fix that with one line is the subject of Chapter 22.

Worst, average and best

How many comparisons does x in a_list make? It depends on where x is. If it comes first, one. If it isn’t there at all, $n$. If it sits in a random place, about $\frac{n}{2}$ on average. One algorithm can have several estimates, and you have to keep them apart.

The worst case is the longest time over all inputs of size $n$. It is a guarantee: the algorithm will never be slower. The average case is the time averaged over the inputs, and it always needs a proviso about which inputs: “if all orders of the items are equally likely.” The best case says almost nothing, since any algorithm can be taught to answer one convenient input instantly.

When people say an algorithm “runs in $O(n^2)$,” they usually mean the worst case. But sometimes the average tells you more. Quicksort from Chapter 21 is quadratic in the worst case, yet on average it makes about $1.39\, n \log_2 n$ comparisons, and in practice it beats many rivals that guarantee $n \log n$. On the other hand, an adversary who knows your algorithm can feed it the worst input on purpose: in Chapter 16 that is how hash tables will be attacked. “Worst case” and “$O$” are easy to confuse, but they are different things. The first says which input we are looking at, the second how coarsely we describe the time. One algorithm can be $\Theta(n)$ in the best case and $\Theta(n^2)$ in the worst, like insertion sort, which you’ll meet in Chapter 20.

The answer to the second question

In Chapter 0 bubble sort and merge sort raced on five thousand numbers, and we promised that you would learn to work out such races in advance. Bubble sort makes $\frac{n(n-1)}{2}$ comparisons, merge sort at most $n \log_2 n$. Measure the price of one “step” of each sort on a small input, and you can predict the time on a big one before running anything.

At five thousand the forecast and the measurement almost coincide; at a million they differ by no more than a quarter: merge sort takes about a second and a half, as predicted from twenty thousand. Bubble sort on the same million would need, by the forecast, about five and a half hours. We won’t check: the whole point of a forecast is to know a program’s time without running it.

Tasks

Four tasks, and in three of them the main test holds a stopwatch: an “every item against every other” solution won’t make the time limit on big inputs. The first task has no stopwatch, but it has a catch: you have to count on paper.

What next

This whole chapter has leaned on something we haven’t explained: x in a_set doesn’t go through the items and doesn’t get more expensive as $n$ grows, while x in a_list goes through them one by one. Where does the difference come from? And why is a_list.append(x) instant, while a_list.insert(0, x) is noticeably slower on a million items? The answer lies in how a list and a set sit in the machine’s memory, and we have never looked in there: for us, a list has been “values in order.” In the next chapter we’ll run experiments the way naturalists do and, from measurements alone, before we know how it is built, work out how Python stores a list.