TLB 与大页

一次读取在到达缓存之前，需要先拿到物理地址，而地址翻译有它自己的小缓存，也就是 TLB，只有大约 64 项。如果程序在比这更多的页之间跳来跳去，哪怕数据缓存表现很好，也可能几乎每次读都在 TLB 上未命中。本讲搭一个 TLB，并说明一个 2 MB 的页如何把 250 个页变成一个。

程序使用的地址是虚拟的：每个程序都以为自己拥有一长串从零开始的内存。机器用物理地址保存真实内存，并把这两个世界都切成页。内存里有一张表，叫页表，说明每个虚拟页放在哪个物理页里。每次读取都先要做这个翻译：取虚拟地址的页号，去查表，并保留字节在页内的位置。这和缓存行的划分是同一回事，只是块更大。

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. 1页号是地址除以页大小，余数是页内的字节位置。

每次读取都去内存里走一遍页表，会让内存访问的代价翻倍，所以处理器把最近的翻译结果存在一张又小又快的表里，叫TLB。页号在 TLB 里的读取是命中，几乎不花什么；不在的就是 TLB 缺失，会触发一次页表遍历，要几十纳秒。一级数据 TLB 大约有 64 项。除了存的是页而不是缓存行，它的工作方式和前面的缓存一样：最近最少使用的先出局。

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

遍历 48 页或 64 页的循环只在第一轮缺失。多一页，65 页，TLB 在 5 轮的每一次读取上都缺失：325 次读取缺失 325 次。这和工作集那一主题里的 LRU 悬崖是同一回事，只是这次是页。关键是覆盖范围：TLB 一次能覆盖多少内存。

取一张 2,000 条记录的表，每条 512 字节：一天的数据外加一些额外字段。它占 1,000 KB，也就是 250 个 4 KB 的页，差不多是 TLB 能装下的 64 页的四倍。按顺序读记录很轻松：每页放八条记录，所以 TLB 每页缺失一次，共 250 次。按随机顺序读就难了：每次读都可能落在 250 页中的任何一页，而 TLB 只记得 64 页。下面的代码用 4 KB 页和 2 MB 页分别测量这两种读法。

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

按顺序读时，4 KB 页要缺失 250 次。打乱之后，2,000 次读取里缺失 1,541 次，占 77%，是前者的六倍。用 2 MB 的页，整个 1,000 KB 装进一个页：不论顺序，都只缺失一次。按每次遍历 30 ns 算，打乱的读取光是翻译就花 46 微秒，够做 10 万次加法。

实验沿着本讲走：地址所在的页、采用 LRU 替换的 TLB、缺失计数、轨迹碰到的页数、按某种顺序读取记录的地址、页大小的比较，以及对 SPY 记录的研究。

• 函数 · 问题依赖
• page_of(address, page_bytes)这个地址在哪一页？整数除法
• TLB(entries).access(address, page_bytes)这次翻译是否命中 TLB？page_of
• tlb_misses(trace, entries, page_bytes)一条轨迹要付出多少次 TLB 缺失？TLB
• pages_touched(trace, page_bytes)一条轨迹碰到多少个不同的页？page_of
• record_trace(order, record_bytes)按这个顺序读记录会碰到哪些地址？简单算术
• compare_pages(trace, entries)大页能帮上多少？tlb_misses
• study(bars)大页在 SPY 记录上节省了什么？compare_pagespages_touchedrecord_trace

下一个主题：到目前为止都是一个程序、一个核心。在伪共享与填充里，两个核心各写同一条缓存行里的两个不同变量，这条缓存行就在它们之间来回弹跳。你要数出失效次数，并用填充把它解决。