The memory hierarchy and latency numbers

A processor adds two numbers in a fraction of a nanosecond, but fetching a number that is not in a cache can take 80 ns. This lecture turns those latency numbers into one figure, the average cost of a memory access, and shows which level of memory eats your time.

A trading program spends most of its life waiting for data: a price, an order, a row of a table. The arithmetic on that data is nearly free, but the data has to travel from memory to the processor first, and the farther away it is, the longer that takes. Think of a desk, a bookshelf, the library floor and a warehouse across town. The few papers on your desk are instant, the bookshelf takes seconds, the library a minute and the warehouse an afternoon. Computers copy the data you use most into small, fast memories next to the processor, called caches, so that most requests are answered at the desk.

A typical server core has three caches in front of main memory. We call them L1, L2 and L3, and the main memory RAM. A request answered by a cache is a hit; a request that has to go on to the next level is a miss. The table below puts the four latencies side by side.

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}for level, ns in LATENCY_NS.items():    print(level, ns, "ns", ns / LATENCY_NS["L1"], "x L1")

L1 1.0 ns 1.0 x L1
L2 4.0 ns 4.0 x L1
L3 15.0 ns 15.0 x L1
RAM 80.0 ns 80.0 x L1

Each level is several times slower than the one above it, and RAM is 80 times slower than L1. The whole skill is about making sure that most accesses are answered near the top.

An access starts at L1. If the value is there, the access costs the L1 latency and is over. If not, the processor asks L2, then L3, then RAM, which always has the value. Every level it asks costs time, whether it hits or not, so an access found in L3 has paid for L1, L2 and L3.

1. 1
   Ask L1Pay 1 ns. A hit ends the access.
2. 2
   On a miss, ask L2Pay 4 ns more. A hit ends the access.
3. 3
   On a miss, ask L3Pay 15 ns more. A hit ends the access.
4. 4
   On a miss, go to RAMPay 80 ns more. RAM always has the value.

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}cost_found_in_l3 = LATENCY_NS["L1"] + LATENCY_NS["L2"] + LATENCY_NS["L3"]print(cost_found_in_l3, "ns")

20.0 ns

An access answered by L3 costs 20 ns, not 15: the 1 ns and 4 ns spent on the two earlier misses are part of the bill.

No single access is typical, so we ask for the average over many accesses. Weight the cost of each path by how often it happens. Every access pays the L1 latency; only the share that misses L1 pays for L2; only the share that misses both pays for L3; and so on. Written as one expression, with brackets that nest like the levels:

This is the average memory access time. Read the brackets from the inside out: the innermost bracket is what a miss in L3 costs, the next bracket adds the L3 visit, and so on up to the L1 visit that every access pays.

LATENCY_NS = {"L1": 1.0, "L2": 4.0, "L3": 15.0, "RAM": 80.0}h1, h2, h3 = 0.9, 0.8, 0.7t = LATENCY_NSamat = t["L1"] + (1 - h1) * (t["L2"] + (1 - h2) * (t["L3"] + (1 - h3) * t["RAM"]))1print(round(amat, 2), "ns")

2.18 ns

1. 11 - h is the share of accesses that miss, so each bracket is multiplied by the share that gets that far.

With 90% of the accesses hitting L1, the average is still 2.18 ns, more than twice the L1 latency. The few accesses that go deep are so expensive that they drive the average. That is why a hit rate that looks excellent can still hide a slow program.

Two questions look alike but have different answers. Which level answers the accesses? And which level takes the time? The first counts accesses, the second counts waiting. A level is reached by a share of the accesses, and each visit costs its latency, so a level that is rarely reached but slow can still dominate the wait.

h1, h2, h3 = 0.9, 0.8, 0.7served = [h1, (1 - h1) * h2, (1 - h1) * (1 - h2) * h3, (1 - h1) * (1 - h2) * (1 - h3)]reach = [1.0, 1 - h1, (1 - h1) * (1 - h2), (1 - h1) * (1 - h2) * (1 - h3)]1cost = [r * ns for r, ns in zip(reach, [1.0, 4.0, 15.0, 80.0])]2print([round(x, 3) for x in served])print([round(c / sum(cost), 3) for c in cost])

[0.9, 0.08, 0.014, 0.006]
[0.459, 0.183, 0.138, 0.22]

1. 1reach is the share of the accesses that visit each level: all of them visit L1.
2. 2sum(cost) is the average access time: the same 2.18 ns as before.

RAM answers only 0.6% of the accesses but accounts for 22% of the waiting time, while L1 answers 90% of them and takes 46% of the time. This is the key fact behind every optimisation in this skill: do not count accesses, count where the time goes.

How much does this matter for a real table? The SPY daily-bars table in the lab has 5,405 rows and five columns (open, high, low, close, volume), so 27,025 values. Read each value once under three conditions: hot caches where almost everything hits, warm caches, and cold caches where half of the accesses miss at every level.

The lab turns this lecture into six small functions, each one built on the ones before it, and ends by pricing the reading of the real SPY table. Here they are with the question each answers.

• Function · questionBuilds on
• average_access_time(hit_rates)What does one access cost on average?The latency table
• slowdown(hit_rates)How many times slower than always hitting L1?average_access_time
• levels_served(hit_rates)Which level answers the accesses?Local hit rates
• time_shares(hit_rates)Which level takes the time?average_access_time
• scan_time_us(n_accesses, hit_rates)How long do n accesses take?average_access_time
• study(bars)What does reading the whole SPY table cost?scan_time_ustime_shares

Next topic: this lecture took the hit rates as given. In Cache lines and spatial locality you build the cache that produces them, and find out why reading a value next to one you just read is almost free.