Measure L1/L2/L3/RAM Latency with Pointer Chasing

Topic Overview

Pointer Chasing

Cache latency benchmarks avoid compiler optimizations by chasing pointers through a large buffer. Each load depends on the previous address, serializing memory access and exposing true RAM or cache miss cost.

cCopy
Loading…

Typical Latencies (order of magnitude)

• L1: ~4 cycles
• L2: ~12 cycles
• L3: ~40 cycles
• DRAM: ~200+ cycles

Sweep array size from 4 KiB (fits L1) to 64 MiB (exceeds last-level cache) and plot nanoseconds per access.

For this exercise, you will implement pointer chasing and print latency versus working set size. This task asks you to measure the cliff when data falls out of each cache level, grounding every optimization task that follows in real hardware numbers.

Working Through the Exercise

Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.

• Trace first: walk one failing input by hand before changing random lines
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.

Your Task

A real pointer-chasing benchmark depends on the machine, so here you build the model behind it: a multi-level cache hierarchy simulator. For each working-set size, it "chases pointers" through the array and reports the average latency per access. As the working set outgrows each level, the latency jumps. The staircase you print is the latency pyramid the benchmark measures on real hardware.

Input

cCopy
Loading…

Every SIZE is a multiple of the line size. Each level holds at most 4096 lines, and a chase covers at most 1 MiB.

Model

• Each level is fully associative with LRU replacement and holds SIZE / line lines.
• An access looks in each level in order and is served by the first one that holds the line (or by memory). It costs that level's latency. The line is then inserted into (or refreshed as most-recently-used in) every level, which may evict each level's LRU line.
• chase SIZE starts with all caches empty. It walks lines 0, 1, …, N-1 (N = SIZE / line) once to warm up, then walks them again and measures only the second pass.

Output

One line per chase:

cCopy
Loading…

SIZE is written as N MiB if it's a multiple of 1 MiB, else N KiB if a multiple of 1 KiB, else N B. X.X is the average latency of the measured pass, with one decimal. The bracket counts how many measured accesses each level served.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

(With LRU and a cyclic walk, a working set even one line larger than a level misses in it every time. That is the "cliff" the benchmark looks for.)

Requirements

1. A level struct with its lines' tags and last-use timestamps; one access(line) function that walks the levels.
2. Reset the whole hierarchy before each chase.

Hidden tests cover a three-level hierarchy with a working set that fits exactly, one just larger than a level, sizes printed in KiB and MiB, and a hierarchy whose levels differ in size by less than a factor of two.