Numbers worth knowing

What does one operation cost? Adding two numbers is a third of a nanosecond. A read from memory, if the number is not in the cache, about a hundred nanoseconds. A packet across an ocean and back, a hundred and fifty milliseconds. There are nine orders of magnitude between the first and the last, and at such distances intuition does not work. Let us stretch time a billion times: a nanosecond becomes a second, and the rest becomes minutes, days and years.

The memory rows are measured on this site’s server. The “request to the server” row is being measured by your browser right now: it is the way to the server and back together with the server’s work, the best of five requests. The button measures your device’s memory the same way as on the server. The rest are typical orders of magnitude: your SSD has its own number, but it is closer to tens of microseconds than to units or thousands.

The idea

An estimate needs not exact values but orders of magnitude, and the fact that neighbouring rungs of the ladder differ tens and hundreds of times. Cache is nanoseconds, memory a hundred nanoseconds, SSD tens of microseconds, the network inside a datacenter fractions of a millisecond, a hard disk milliseconds, a network across an ocean a hundred milliseconds. An estimate is a sum of terms “how many times × how much it costs”, and almost always one term is bigger than all the others together. Finding it means understanding what to speed up and what can be left alone.

Tables of such numbers have long circulated among programmers. Peter Norvig gives one with his essay “Teach Yourself Programming in Ten Years”, and Jeff Dean showed another in talks on large distributed systems in the late 2000s under the title “Numbers Everyone Should Know”. Since then processors have got faster and hard disks have given way to SSDs, but a read from memory has stayed around a hundred nanoseconds, and light has not got faster: in optical fibre it travels about 200 kilometres per millisecond, and a 10,000-kilometre path there and back will not take less than 100 ms however fast the servers. The orders of magnitude hold for decades. How caches are built and why the ladder is just so is in the course chapter “Near and far”; here is how to use these numbers.

The cheat sheet

Notice the “random” and “in order” pairs. Latency is how long to wait for the first byte, throughput how many bytes per second after that. A random read from an SSD is 50 µs for 4 KB, about 80 MB/s if you read one at a time, while in order the same SSD delivers gigabytes a second, tens of times more. Memory is the same, and the measurement shows it.

The memory staircase on the site’s server

Why is there one memory read in the table but three in the scene? Because the cost of a read depends on how much memory the program touches. The program below runs through an array in random order, and each next read depends on the previous one: the address of the next step lies in the current cell. The processor can neither guess the address nor read ahead, and the time of a step is the latency of the rung the array fits into. The second series is the same numbers read in order.

In Go, with the switch above the chart, the steps are clearly visible. While the array fits in the first-level cache, a step costs a couple of nanoseconds, in the next caches a few, and when the array stops fitting in the cache altogether, about a hundred. In order it is a quarter of a nanosecond per number at any size: the processor notices that the addresses go in order and fetches memory lines in advance, and one cache line is 16 numbers. At 64 megabytes the difference is hundreds of times with the same number of reads and the same O(n). This is the difference between walking an array and a linked list whose nodes are scattered over memory.

In Python both series almost coincide and are almost flat: each step of the loop costs the interpreter about 40 ns, and the cache steps drown in that cost. Only on the largest array does scattered reading become noticeably dearer: memory latency grows to the interpreter’s cost.

Estimate it yourself

Ten tasks. Put an estimate on the scale from a microsecond to a day, then look at the answer and how it came from the table. Being off by two or three times is normal for an estimate. Being off a hundred times means a different decision: different storage, a different algorithm, a different architecture.

The tasks come in pairs, and the pairs matter more than the answers: in order and scattered, memory and disk, SSD and hard disk, the database nearby and across an ocean. In almost every pair the number of operations is the same, while the time differs hundreds and thousands of times. Big O does not see this difference: it counts steps, not their cost. The last task explains why databases keep indexes not in binary trees but in B-trees: on disk what matters is not the number of comparisons but the number of reads.

Code

An estimate is usefully written down as a small program: a price table and terms “how many times × how much it costs”. Here is a report on 10,000 orders that needs, for each order, the customer’s card from a database in the same datacenter.

The first option spends 90% of its time on the way to the database and back, not on work: speeding up the database is useless. One query for all the cards makes reading from disk the dominant term: 0.6 s instead of 5.6. Cards already in the service’s memory are fetched in 2 ms. Each step changes the dominant term, and the estimate suggests what to do next.

And this is the measurement the staircase is built from: pointer chasing. The array is turned into a single ring by Sattolo’s permutation, in which each element points to the next so that a walk from cell zero goes through the whole array rather than getting stuck in a small cycle. An ordinary random shuffle would give several rings, and the measurement might run along a short one that sits entirely in the cache.

How far to trust these numbers

These are orders of magnitude, not constants. A laptop and a server answer from memory differently, on a two-processor server a read from the other processor’s memory takes longer still, SSDs differ from each other several times over, and the network inside datacenters has got faster than in the old tables. So:

• Remember the ratios. Memory is a hundred times slower than cache, a random SSD read hundreds of times slower than memory, a hard disk hundreds of times slower than an SSD. Ratios change more slowly than the numbers themselves.
• Being off by two is a good estimate. Being off by a hundred means a term is missing: an extra network request, a cache miss at every step, a disk read instead of memory. Look for it.
• Concurrency changes the picture. SSDs and networks serve many requests at once, and a thousand simultaneous requests are not a thousand latencies in a row. An estimate “one at a time” is an upper bound.
• When the decision depends on an exact number, measure. How to do it honestly is told in the article “How to benchmark honestly”.

Problems

The problem is about where the time goes when a page loads. Resources are found inside one another: a font in a stylesheet, data in a script. With each new server the browser first says hello, and these greetings cost several round trips each. The editorial shows that on the example page they take more than half the loading time.