TLB and huge pages

Before a read can reach the cache it needs a physical address, and the translation has its own small cache, the TLB, with only about 64 entries. A program that jumps between more pages than that can miss the TLB on almost every read, even when its data caches do well. This lecture builds a TLB and shows how a 2 MB page turns 250 pages into one.

The addresses a program uses are virtual: each program believes it owns a long row of memory starting at zero. The machine keeps real memory in physical addresses and cuts both worlds into pages. A table in memory, the page table, says which physical page holds each virtual page. Every read first needs this translation: take the page number of the virtual address, look it up, and keep the byte position inside the page. It is the same split as the line of a cache, with a bigger block.

page_bytes = 4096for address in (0, 4095, 4096, 123456789):    print(address, "-> page", address // page_bytes, "byte", address % page_bytes)1

0 -> page 0 byte 0
4095 -> page 0 byte 4095
4096 -> page 1 byte 0
123456789 -> page 30140 byte 3349

1. 1The page number is the address divided by the page size; the remainder is the byte inside the page.

Walking the page table in memory for every read would double the cost of memory access, so the processor keeps its latest translations in a small, fast table called the TLB. A read whose page is in the TLB is a hit and costs almost nothing. A read whose page is not there is a TLB miss and triggers a page walk, tens of nanoseconds. A first-level data TLB holds about 64 entries. Apart from keeping pages instead of lines, it works like the caches before: least recently used goes first.

class TLB:    def __init__(self, entries):        self.entries = entries        self.pages = []        self.hits = 0        self.misses = 0    def access(self, address, page_bytes):        page = address // page_bytes        if page in self.pages:            self.pages.remove(page)            self.pages.append(page)            self.hits += 1            return True        self.misses += 1        self.pages.append(page)        if len(self.pages) > self.entries:            self.pages.pop(0)        return Falsedef tlb_misses(trace, entries, page_bytes):    tlb = TLB(entries)    for address in trace:        tlb.access(address, page_bytes)    return tlb.missesfor n_pages in (48, 64, 65, 80):    trace = [page * 4096 for page in range(n_pages)] * 5    print(n_pages, "pages, 5 rounds:", tlb_misses(trace, 64, 4096), "misses")

48 pages, 5 rounds: 48 misses
64 pages, 5 rounds: 64 misses
65 pages, 5 rounds: 325 misses
80 pages, 5 rounds: 400 misses

A loop over 48 or 64 pages misses only on the first round. One page more, 65, and the TLB misses on every single read of the 5 rounds: 325 misses out of 325. This is the same LRU cliff as in the working-set topic, now with pages. The reach is what matters: how much memory the TLB covers at once.

Take a table of 2,000 records, each 512 bytes: a day of data plus extra fields. It takes 1,000 KB, which is 250 pages of 4 KB, nearly four times the 64 pages the TLB can hold. Reading the records in order is gentle: eight records share each page, so the TLB misses once per page, 250 times. Reading them in a random order is hard: each read can land on any of the 250 pages and the TLB keeps only 64 of them. The code below measures both, with 4 KB pages and with 2 MB pages.

import randomorder = list(range(2000))shuffled = random.Random(7).sample(order, len(order))for name, records in (("in order", order), ("shuffled", shuffled)):    trace = [record * 512 for record in records]    print(name, "4 KB pages:", tlb_misses(trace, 64, 4096), "- 2 MB pages:", tlb_misses(trace, 64, 2 * 1024 * 1024))

in order 4 KB pages: 250 - 2 MB pages: 1
shuffled 4 KB pages: 1541 - 2 MB pages: 1

In order, the 4 KB pages cost 250 misses. Shuffled, they cost 1,541 misses out of 2,000 reads, 77% of the reads, six times more. With 2 MB pages all 1,000 KB fit in a single page: one miss whatever the order. At 30 ns a walk, the shuffled read spends 46 microseconds on translations alone, which would be spent on the arithmetic of 100,000 additions.

The lab follows the lecture: the page of an address, the TLB with LRU replacement, the miss count, the pages a trace touches, the addresses of records in an order, the comparison of page sizes and the study on the SPY records.

• Function · questionBuilds on
• page_of(address, page_bytes)Which page holds this address?Integer division
• TLB(entries).access(address, page_bytes)Is this translation a TLB hit?page_of
• tlb_misses(trace, entries, page_bytes)How many TLB misses does a trace cost?TLB
• pages_touched(trace, page_bytes)How many different pages does a trace touch?page_of
• record_trace(order, record_bytes)Which addresses does reading records in this order touch?Plain arithmetic
• compare_pages(trace, entries)How much do huge pages help?tlb_misses
• study(bars)What do huge pages save on the SPY records?compare_pagespages_touchedrecord_trace

Next topic: until now there was one program and one core. In False sharing and padding two cores write to two different variables that sit in the same cache line, and the line ping-pongs between them. You count the invalidations and fix them by padding.