memory - 如果它们都需要两次内存访问，什么使 TLB 比页表更快？

Question

刚走wikipedia :

The page table, generally stored in main memory, keeps track of where the virtual pages are stored in the physical memory. This method uses two memory accesses (one for the page table entry, one for the byte) to access a byte. First, the page table is looked up for the frame number. Second, the frame number with the page offset gives the actual address. Thus any straightforward virtual memory scheme would have the effect of doubling the memory access time. Hence, the TLB is used to reduce the time taken to access the memory locations in the page table method.

鉴于此，我很好奇为什么 TLB 实际上更快，因为据我所知，它只是页表的一个更小、更精确的副本。

您仍然需要访问TLB以找到物理地址，然后一旦有了物理地址，您仍然需要实际访问物理地址处的数据，这与页表一样是两次查找。

我只能想到TLB更快的两个原因:

在 TLB 或页表中查找地址不是 O(n)(我假设它像哈希表一样是 O(1))。因此，由于 TLB 小得多，因此查找速度更快。同样在这种情况下，为什么不使用哈希表而不是 TLB？

我错误地解释了 TLB 的工作原理，它实际上并没有进行两次访问。

Answer 1

我意识到这个问题已经三年了，但由于它仍然具有相关性，并且仍然出现在搜索引擎中，我会尽力提供完整的答案。
通过 TLB 而不是页表访问主内存更快，主要有两个原因:
1. TLB 比主存(页表所在的位置)快。
The typical access time is in the order of <1 ns for the TLB and 100 ns for main memory
TLB 访问是 L1 缓存命中的一部分，并且 modern CPUs can do 2 loads per clock如果它们都命中 L1d 缓存。
造成这种情况的原因有两个:

TLB 位于 CPU 内，而主存——因此页表——不在。

TLB 与其他缓存一样，由快速且昂贵的 SRAM 构成，而主存储器通常由速度慢且价格低廉的 DRAM 组成(阅读更多 here)。

因此，如果 TLB 和页表都只需要一次内存访问的假设是正确的，那么粗略地说，TLB 命中仍会将内存访问时间减半。然而，正如我们接下来将看到的，这个假设是不正确的，拥有 TLB 的好处更大。
2. 访问页表通常需要多次内存访问。
这确实是问题的关键。
现代 CPU 倾向于使用 multilevel page tables为了节省内存。最值得注意的是，x86-64 页表目前最多包含四个级别 ( and a fifth may be coming )。这意味着通过页表访问内存中的单个字节最多需要五次内存访问:四次用于页表，一次用于数据。显然，如果没有 TLB，成本将高得难以承受；很容易理解为什么 CPU 和操作系统工程师付出了很多努力来最小化 TLB 未命中的频率。
最后，请注意，即使这种解释也有些简化，因为它忽略了数据缓存等。现代台式机 CPU 的详细机制很复杂，并且在某种程度上尚未公开。有关该主题的更详细讨论，请参阅 this thread ， 例如。
页表访问可以并且由现代 CPU 上的数据缓存进行缓存，但是页遍历中的下一次访问取决于第一次访问的结果(指向页表下一级的指针)，因此 4 级即使所有访问都命中 L1d 缓存，页面遍历也会有大约 4x 4 个周期 = 16 个周期的延迟。对于管道来说，隐藏的时间比大约 3 到 4 个周期的 TLB 延迟要多得多，后者是现代英特尔 CPU(当然使用 TLB 进行数据和指令访问)中 L1d 缓存命中负载的一部分。