Every way to make code faster at the memory level

Formal. For one cache level,

In a hierarchy the miss penalty of one level is the average access time of the level below it, so for an L1 cache backed by an L2 cache and memory,

where each t is a hit time (or memory's access time) and each m is a local miss rate: the fraction of the accesses reaching that level that miss there.

In plain English. Every access pays the time to look in the fast cache. Only the accesses that miss also pay for the trip further down, so you add that trip's cost weighted by how often it happens. If the next level is itself a cache, its own cost is worked out the same way first.

Example. L1: hit time 4 cycles, miss rate 5%. L2: hit time 14 cycles, local miss rate 20%. Memory: 300 cycles. The L2 average is 14 + 0.20 × 300 = 74 cycles, so AMAT = 4 + 0.05 × 74 = 7.7 cycles. With no L2 it would be 4 + 0.05 × 300 = 19 cycles. These are model figures of the size published for current cores, not measurements.

Why this formula exists. A cache's worth depends on both how fast its hits are and how often it misses, and a small change in miss rate can matter more than a faster hit. AMAT puts both in one number, so two designs, or two versions of a loop, can be compared.

Formal. Classify each miss in an address trace against a given cache:

1. Compulsory if it is the first reference to that cache line in the trace (it would miss in an infinitely large cache).
2. Otherwise capacity if a fully associative LRU cache with the same total number of lines would also miss it.
3. Otherwise conflict: only the restricted placement (too many lines competing for one set) caused it.

Remedies follow the class: compulsory misses fall with larger lines or prefetching, capacity misses with a larger cache or with code that keeps less data in use at once, conflict misses with higher associativity or a different stride or layout.

In plain English. Ask three questions about each miss. Was this the first time the line was ever used? Then nothing could have saved it. Would a cache of the same size that could put anything anywhere also have missed? Then the data simply doesn't fit. If not, the miss happened only because too many lines wanted the same few slots.

Example. A direct-mapped cache with 4 lines of 16 bytes (index = (address >> 4) & 3). The trace 0x000, 0x040, 0x000, 0x040: both addresses have index 0. The first two accesses are compulsory misses. The third and fourth also miss, but a 4-line fully associative cache would hold both lines and hit, so they are conflict misses. A loop cycling through five different lines in a 4-line fully associative LRU cache misses on every access after the first five: capacity misses.

Why this rule exists. Each kind of miss has a different cure, and the wrong cure (more ways for a capacity problem, a bigger cache for compulsory misses) costs hardware or effort and fixes nothing.

Formal. False sharing occurs when two or more cores access different bytes of the same cache line, at least one of them writes, and the accesses repeat often. Because coherence works per line, each write invalidates the other cores' copies and the line moves between caches although no byte is shared. It disappears when each core's written data occupies lines no other core touches: align or pad to the line size B (64 bytes on most x86-64 and ARM64 cores, 128 on Apple M-series), or keep per-thread copies and combine them at the end.

In plain English. Two threads that never touch each other's variables can still fight over them if the variables sit in the same cache line. Give each thread's frequently written data a line of its own.

Example. long counts[4] takes 32 bytes, all in one 64-byte line. Four threads each incrementing their own counts[t] a hundred million times make that line bounce on almost every increment. Declaring struct alignas(64) Slot { long n; }; Slot counts[4]; puts each counter on its own line (use 128 on Apple M-series), and the threads no longer interfere. The totals are identical either way; only the time changes.

Why this rule exists. False sharing makes correct parallel code slower than serial code without any visible bug, and the source code gives no hint of it; only the data layout and the line size do.

Formal.

A working set larger than the reach of a TLB level causes TLB misses at that level even when its data fits in the caches.

In plain English. Each remembered translation covers one page, so the TLB as a whole covers its number of entries times the page size. Use more memory than that, scattered over many pages, and the processor keeps having to look translations up again.

Example. A second-level TLB of 2048 entries with 4 KiB pages reaches 2048 × 4 KiB = 8 MiB. If the same entries hold 2 MiB huge pages, it reaches 2048 × 2 MiB = 4 GiB. A program whose working set is 64 MiB misses the TLB often with 4 KiB pages and almost never with huge pages. (Entry counts and which page sizes each level can hold vary by core; these numbers are illustrative.)

Why this formula exists. The caches are measured in bytes but the TLB in pages, and comparing the two explains why a program can slow down from translation alone, and why huge pages help large working sets.