# Cache and the Memory Hierarchy

Computer Science I · Introduction to Computers · https://tryals.app/learn/computer-science-i/cache-and-the-memory-hierarchy

## The Memory Hierarchy

Fast storage is small and expensive; large storage is slow and cheap. Computers bridge this gap using a **memory hierarchy** of stacked layers.

| Level | Speed | Size | Cost |
| --- | --- | --- | --- |
| Registers | Fastest | Bytes | Highest |
| Cache | Very fast | KB-MB | High |
| RAM | Fast | GB | Medium |
| SSD / Disk | Slow | TB | Low |

A **cache** is a small, fast memory sitting between the CPU and RAM. It holds **copies** of recently used data, not unique data.

**Common pitfall:** A cache never stores separate data from main memory. It only keeps fast copies of what lives in RAM to speed up access.

## Locality and Hits

When the CPU needs data, it checks the cache first. A **cache hit** is fast, while a **cache miss** forces a slow fetch from main memory.

Caches succeed because programs show **locality of reference**:

| Locality Type | Meaning | CPU Action |
| --- | --- | --- |
| **Temporal** | Used recently? | Use again soon |
| **Spatial** | Address accessed? | Fetch nearby block |

The **hit rate** is the fraction of accesses found in the cache. Because misses are so slow, even small drops in hit rate hurt performance.

## Practice questions

3 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Order these storage layers from fastest to slowest.

**Answer:**

1. Registers
2. L1 cache
3. L3 cache
4. Main memory (RAM)
5. Disk or SSD

**Why:** Speed falls and capacity rises as you go down: registers hold bytes, caches hold kilobytes to megabytes, RAM gigabytes, disk terabytes. L1 is nearer the CPU and faster than L3. The hierarchy exists precisely because no single technology is both fast and huge.

Page: https://tryals.app/practice/computer-science-i/cache-and-the-memory-hierarchy/order-these-storage-layers-from-fastest-to-slowest

### 2. A cache works because programs access memory addresses uniformly at random.

**Answer:** False

**Why:** False. A cache depends on the opposite, **locality**: recently used data is reused (temporal) and neighbours follow (spatial). Genuinely random access defeats it entirely, which is why pointer-chasing through a large linked list can be far slower than scanning an array of the same size.

Page: https://tryals.app/practice/computer-science-i/cache-and-the-memory-hierarchy/a-cache-works-because-programs-access-memory-addresses-uniformly-at

### 3. Traversing a 2D array row by row can run several times faster than column by column, with identical operation counts. Why?

A. Because the compiler optimises row loops and not column loops
B. Because row-major storage makes row-wise access walk contiguous memory
C. Because column-major traversal performs more comparisons
D. Because row indices are computed faster than column indices

**Answer:** B. Because row-major storage makes row-wise access walk contiguous memory

**Why:** Row-major means [i][j] and [i][j+1] are neighbours, so one cache line serves several iterations; stepping down a column loads a line and uses one element of it. Same instructions, different memory behaviour, which is why loop interchange is a standard optimisation and why the language's storage order is worth knowing.

Page: https://tryals.app/practice/computer-science-i/cache-and-the-memory-hierarchy/traversing-a-2d-array-row-by-row-can-run-several-times-faster-than