title: What makes a TLB faster than a Page Table if they both require two memory accesses?
body: <p>Just going off <a href="https://en.wikipedia.org/wiki/Translation_lookaside_buffer" rel="nofollow noreferrer">wikipedia</a>:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>So given that, what I'm curious about is why the TLB is actually faster because from what I know it's just a smaller, exact copy of the page table.</p>
  
  <p>You still need to access the TLB to find the physical address, and then once you have that, you still need to actually access the data at the physical address, which is two lookups just like with the page table.</p>
  
  <p>I can only think of two reasons why the TLB is faster:</p>
  
  <ul>
  <li><p>looking up an address in the TLB or page table is not O(n) (I assumed it's O(1) like a hash table). Thus, since the TLB is much smaller, it's faster to do a lookup. Also in this case, why not just use a hash table instead of a TLB?</p></li>
  <li><p>I incorrectly interpreted how the TLB works, and it's not actually doing two accesses.</p></li>
  </ul>