Benchmark TLB (Translation Lookaside Buffer) Performance

Topic Overview

Translation Lookaside Buffer

Every virtual address lookup can walk page tables (four levels on x86-64). The TLB caches recent virtual-to-physical mappings. TLB misses trigger expensive page walks handled by the MMU.

cCopy
Loading…

Working Set vs TLB Capacity

A 4 KiB page and a 64-entry TLB cover only 256 KiB without misses. Jumping across thousands of pages intentionally blows the TLB.

• 4 KiB pages: fine-grained mapping, more TLB pressure
• 2 MiB huge pages: fewer entries cover more RAM (common for databases)

For this exercise, you will benchmark pointer chasing across increasing page counts. This task asks you to correlate miss spikes with page-table walk cost, the same knob hugetlbfs and JVM -XX:+UseLargePages adjust in production.

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

Simulate a TLB (translation lookaside buffer) to see why access patterns that stride across pages are slow, and why huge pages help. Every memory access needs its virtual page translated. A TLB hit is free, and a miss costs a page-table walk. Run each access pattern with 4 KiB pages and with 2 MiB huge pages, and compare the misses and walk costs.

Input

cCopy
Loading…

For random, use x = (x · 1103515245 + 12345) mod 2^31 starting from x = SEED. Advance x before each access, then the address is x mod TOTAL. All numbers are decimal bytes, and a pattern makes at most 200000 accesses.

Model

• The TLB is fully associative with ENTRIES entries and LRU replacement. It is empty at the start of every pattern and for each page size.
• The page number is address / page_size, with page size 4096 (4K) or 2097152 (2M).
• A miss costs a page walk of 4 memory references with 4K pages (4-level table), and 3 with 2M pages (the walk stops one level early).

Output

First TLB reach: 4K pages R1, 2M pages R2, where reach = ENTRIES × page size. Then one line per pattern:

cCopy
Loading…

Sizes (TOTAL, reach) print as N GiB, N MiB or N KiB when they divide evenly (largest unit first), else N B. Percentages have one decimal.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

The first pattern touches 256 pages cyclically with a 64-entry LRU TLB, so the second pass misses as well.

Requirements

1. A TLB struct with lookup(page) that returns hit/miss and updates LRU; run each pattern twice (4K and 2M) on a fresh TLB.
2. Generate the random addresses exactly as specified.

Hidden tests cover random access over a large region and within the TLB reach, a stride larger than a page, and a tiny TLB.