Part 4 of 6 · 2 min read
TLB reach
In plain words: A TLB has a fixed number of entries. Typical sizes are tens to a few thousand entries, in one or two levels (a small, fast first level and a larger, slower second level). The memory that its entries can map at one time is the TLB reach: the number of entries times the page size.
A TLB with 64 entries and 4 KiB pages reaches 64 × 4 KiB = 256 KiB. A program whose working data is larger than that, and which jumps among its pages, keeps missing. A second-level TLB of 1,536 entries reaches 1,536 × 4 KiB = 6 MiB. If the same 64 entries hold 2 MiB huge pages (page 4), the reach is 64 × 2 MiB = 128 MiB, 512 times more with the same hardware.
A test shows these effects. The program builds a chain of pointers through N pages, one pointer in each page, in random order, and follows the chain 20 million times. Each step is one memory read in a different page. The time per step was:
| Pages in the chain | Memory they span | Time per access |
|---|---|---|
| 4 to 64 | up to 256 KiB | 1.8 ns |
| 128 | 512 KiB | 4.2 ns |
| 512 | 2 MiB | 4.3 ns |
| 1,024 | 4 MiB | 8.2 ns |
| 2,048 | 8 MiB | 10.1 ns |
| 4,096 | 16 MiB | 17.6 ns |
| 8,192 | 32 MiB | 19.0 ns |
| 16,384 | 64 MiB | 24.6 ns |
| 32,768 | 128 MiB | 46.0 ns |
The curve is flat up to 64 pages, jumps at 128 pages, and rises step by step later. The first step, from 1.8 ns to 4.2 ns, happens when the number of pages passes 64. That is the size of a typical first-level data TLB, and the chain has only 128 cache lines, so the data cache cannot explain the jump. The later steps are harder to read, because the chain also grows out of the processor's data caches (the machine has a 96 KiB first-level data cache per core and a 4 MiB second-level cache), and the two effects add up. This test cannot split them. The lesson holds anyway: a program that touches many pages in a scattered way pays for it, even if every page is already in memory.
TLB reach
The TLB reach is the amount of memory whose translations the TLB can hold at one time, equal to the number of entries times the page size.
Example: a TLB of 64 entries with 4 KiB pages reaches 256 KiB, and with 2 MiB pages it reaches 128 MiB.
Check yourself: 1. What is the reach of a TLB with 1,024 entries and 4 KiB pages? 2. Why does using huge pages raise the reach without more entries? 3. Why can the test not tell the TLB effect from the cache effect for large chains?