Cache Memory — Bridging the Speed Gap

The memory speed gap: CPUs operate at ~3 GHz (one operation every ~0.3ns). DRAM (main RAM) has ~100ns latency — 300× slower than the CPU. Without cache, the CPU would spend 99% of its time waiting for memory. Cache is the solution.

Cache = small, fast SRAM (Static RAM) between the CPU and DRAM. The CPU checks cache first. If data is there (cache hit) → fast. If not (cache miss) → fetch from next level → slow.

Principle of Locality — why cache works:
- Temporal locality: recently accessed data will likely be accessed again soon. (Loop variables, hot code paths)
- Spatial locality: if you access address X, you'll likely access X+1, X+2 soon. (Arrays, sequential code execution)
Cache exploits BOTH: it stores recently used data (temporal) and fetches an entire cache line (64 bytes) per access, not just one byte (spatial).

The Memory Hierarchy:
- Registers: 1 cycle, ~1 KB total
- L1 cache: 4 cycles, 32-64 KB per core, per-core private
- L2 cache: 12 cycles, 256 KB - 1 MB per core, per-core private
- L3 cache: 40 cycles, 8-32 MB, shared across all cores
- DRAM (RAM): ~200 cycles, 16-64 GB
- NVMe SSD: ~100,000 cycles

Cache organization — Direct-Mapped Cache:
Each memory block maps to exactly one cache line.
Address is split into: [Tag | Index | Block Offset]
- Block Offset: which byte within the 64-byte cache line
- Index: which cache set (which line to look in)
- Tag: the upper bits — checked to verify this is the right block

Set-Associative Cache:
- N-way set associative: each index maps to N possible lines
- 4-way: any block can go in 1 of 4 lines in its set
- Higher associativity → fewer conflicts → better hit rate
- 8-way or 16-way is common for L2/L3
- Fully associative: any block anywhere (best hit rate, hardware-expensive)

Write policies:
- Write-through: write to cache AND memory simultaneously. Simple, always consistent. Memory bus becomes bottleneck.
- Write-back: write only to cache, mark line as "dirty". Write to memory only when the line is evicted. Better performance, more complex.

Replacement policies (when cache is full, which line to evict):
- LRU (Least Recently Used): evict the line not used for longest time. Best hit rate, expensive to track exactly.
- Pseudo-LRU: approximate LRU with a bit tree. Most real CPUs use this.
- FIFO, Random: simpler, used in some L3 designs.

Cache-friendly code: the difference between cache-friendly and cache-unfriendly code can be 10-100× performance difference. Row-major vs column-major access of a 2D array is the classic example — covered in the code section.

1import time
2import random
3
4# ── Cache hit/miss simulation ──────────────────────────
5class DirectMappedCache:
6    def __init__(self, num_lines=8, block_size=4):
7        self.num_lines  = num_lines
8        self.block_size = block_size
9        self.cache = [{"valid": False, "tag": -1, "data": []} for _ in range(num_lines)]
10        self.hits = self.misses = 0
11
12    def access(self, address, memory):
13        offset = address % self.block_size
14        index  = (address // self.block_size) % self.num_lines
15        tag    = address // (self.block_size * self.num_lines)
16
17        line = self.cache[index]
18        if line["valid"] and line["tag"] == tag:
19            self.hits += 1
20            return "HIT ", line["data"][offset]
21        else:
22            self.misses += 1
23            # Fetch entire block from memory
24            block_start = address - offset
25            line["valid"] = True
26            line["tag"]   = tag
27            line["data"]  = [memory[block_start + i] for i in range(self.block_size)
28                             if block_start + i < len(memory)]
29            return "MISS", line["data"][offset]
30
31    def stats(self):
32        total = self.hits + self.misses
33        rate  = 100 * self.hits / total if total > 0 else 0
34        print(f"  Hits: {self.hits}, Misses: {self.misses}, Hit rate: {rate:.1f}%")
35
36# Simulate memory
37memory = list(range(256))
38cache  = DirectMappedCache(num_lines=8, block_size=4)
39
40print("Cache Access Simulation:")
41# Sequential access — great spatial locality
42print("
43Sequential access (cache-friendly):")
44for addr in range(0, 32, 1):
45    result, val = cache.access(addr, memory)
46    if addr < 12:
47        print(f"  addr={addr:3d} → {result} (val={val})")
48cache.stats()
49
50# Strided access — poor locality
51cache2 = DirectMappedCache(num_lines=8, block_size=4)
52print("
53Strided access (cache-unfriendly, stride=8):")
54for addr in range(0, 64, 8):
55    result, val = cache2.access(addr, memory)
56    print(f"  addr={addr:3d} → {result} (val={val})")
57cache2.stats()
58
59# ── THE CLASSIC: row vs column major access ────────────
60print("
61" + "="*50)
62print("CACHE LOCALITY: Row-major vs Column-major")
63print("="*50)
64N = 1000
65matrix = [[random.random() for _ in range(N)] for _ in range(N)]
66
67# Row-major (cache-friendly: adjacent in memory)
68start = time.perf_counter()
69total = 0.0
70for i in range(N):
71    for j in range(N):
72        total += matrix[i][j]   # row-major: matrix[i] is contiguous
73t_row = time.perf_counter() - start
74
75# Column-major (cache-unfriendly: strided access)
76start = time.perf_counter()
77total = 0.0
78for j in range(N):
79    for i in range(N):
80        total += matrix[i][j]   # column-major: every access is N elements apart
81t_col = time.perf_counter() - start
82
83print(f"Row-major (friendly):    {t_row*1000:.1f} ms")
84print(f"Column-major (unfriendly): {t_col*1000:.1f} ms")
85print(f"Slowdown from cache misses: {t_col/t_row:.1f}x")
86print("
87Lesson: always iterate over the LAST index in inner loop!")