Mấy phần trước đo cache: độ trễ từng tầng, rồi conflict miss theo tập. Nhưng có một tầng nữa nằm trước cả cache dữ liệu, âm thầm cộng chi phí vào mỗi lần chạm bộ nhớ, mà hiếm khi ai nghĩ tới: TLB (Translation Lookaside Buffer).

Hình dung một tòa nhà văn phòng khổng lồ. Địa chỉ bạn ghi trên phong bì ("phòng Kế toán") không phải vị trí thật — phải có một quyển sổ tra "phòng nào ở tầng mấy, phòng số bao nhiêu". Tra sổ mỗi lần gửi thư thì chậm chết, nên cô lễ tân thuộc lòng vị trí của vài trăm phòng hay lui tới. Hỏi một phòng cô thuộc: chỉ ngay, gần như tức thì. Hỏi một phòng lạ: cô phải lật quyển sổ dày — mất một lúc. Mọi địa chỉ chương trình bạn dùng cũng là địa chỉ ảo phải được dịch sang địa chỉ vật lý thật, theo từng trang nhớ, và TLB chính là trí nhớ của cô lễ tân — cache nhỏ giữ vài trăm ánh xạ trang gần đây. Nếu code của bạn trải trên nhiều trang hơn TLB chứa được, mỗi truy cập phải đi bảng trang (page walk) — cộng thêm chục tới trăm chu kỳ, ngoài mọi chi phí cache. Tôi đo trong container gcc:13 trên host ARM, và con số tách bạch rõ TLB miss khỏi cache miss.

Mỗi truy cập phải dịch địa chỉ, theo trang

Chương trình chạy trên bộ nhớ ảo: mỗi tiến trình thấy một không gian địa chỉ liền mạch của riêng nó, nhưng những địa chỉ ấy không phải chỗ thật trong RAM. Hệ điều hành chia bộ nhớ thành các trang (page — ở container này đo được 4 KB mỗi trang) và giữ một bảng trang (page table) nhiều tầng ánh xạ mỗi trang ảo sang một khung trang vật lý. Mỗi lần CPU chạm một địa chỉ, nó phải tra bảng đó để biết dữ liệu nằm đâu thật — quyển sổ tra phòng.

Đi bảng trang mỗi lần truy cập thì quá chậm — bảng trang nhiều tầng nghĩa là vài lần đọc bộ nhớ chỉ để dịch một địa chỉ. Nên CPU có TLB: một cache rất nhỏ, rất nhanh, giữ những ánh xạ trang vừa dùng. Cơ chế:

  • TLB hit: ánh xạ của trang đang chạm nằm sẵn trong TLB → dịch gần như miễn phí, truy cập chạy đúng tốc độ tầng cache chứa dữ liệu.
  • TLB miss: ánh xạ không có trong TLB → CPU phải đi bảng trang (page walk), vài lần đọc bộ nhớ để tra ra khung vật lý, rồi mới truy cập được dữ liệu. Chi phí này cộng thêm chục-trăm chu kỳ.

Điểm mấu chốt: đây là một tầng phí thứ hai, độc lập với cache dữ liệu. Kể cả khi dữ liệu bạn cần đang nằm trong cache, nếu ánh xạ trang của nó không trong TLB, bạn vẫn trả giá page walk. TLB đếm theo số trang bạn đụng tới, không theo số byte.

Cách đo: tách TLB miss khỏi cache miss

Muốn chứng minh TLB là một chi phí riêng, phải dựng hai mẫu truy cập chạm cùng số dòng cache nhưng khác số trang:

  • spread (trải): đặt đúng một node mỗi trang, cách nhau một trang (4 KB). Đuổi con trỏ qua N node nghĩa là đụng N trang khác nhau — cần N ánh xạ trang.
  • dense (gói): xếp các node sát nhau (mỗi 64 byte một node), dồn hết vào rất ít trang. Đuổi qua N node vẫn chạm đúng chừng ấy dòng cache như bản spread ở cùng N, nhưng chỉ dùng vài trang.

Cả hai đều đuổi con trỏ theo một chu trình Sattolo (ngẫu nhiên, để không bị prefetch che) và lấy min nhiều lần. Nếu spread chậm hơn dense trong khi cùng lượng dòng cache, phần chênh đó không thể là cache — nó là TLB.

Đo: cùng cache footprint, trải nhiều trang chậm 15 lần

Tôi quét N từ 16 tới 32768 node, so spread (1 node/trang) với dense (64 B/node):

Đuổi con trỏ, ns/truy cập, trang 4 KB, host ARM, g++ -O2:

   N node | spread (1/trang, N trang) | dense (64B/node, ít trang)
   -------|---------------------------|----------------------------
      128 |   4,10 ns                 | 0,91 ns
      256 |   7,38 ns  (L1 TLB hết)   | 0,91 ns
     1024 |  14,07 ns  (page walk)    | 0,92 ns   <- cùng #dòng cache
     2048 |  27,21 ns                 | 0,92 ns
     4096 |  42,13 ns                 | 4,74 ns   <- dense nhảy = CACHE
    32768 | 101,21 ns                 | 6,77 ns

Nhìn cột dense trước: phẳng lì 0,91–0,92 ns tới tận N=2048. Các node gói trong ~16–32 trang, cả TLB lẫn L1 cache đều thừa sức chứa — mọi truy cập là hit đôi. Chỉ ở N=4096 nó mới nhảy lên 4,74 ns: lúc này dữ liệu (~512 KB) vượt L1, đó là cache miss thuần, không dính TLB (vẫn ít trang).

Giờ cột spread — cùng số node, cùng số dòng cache chạm, nhưng mỗi node một trang riêng. Nó leo đều: 4,10 ns ở N=128, nhảy lên 7,38 ns ở N=256, rồi 14,07 ns ở N=1024, 42 ns, tới 101 ns ở N=32768. So sánh sắc nhất ở N=1024: spread 14,07 ns còn dense 0,92 ns — chênh 15 lần, mà cache footprint y hệt nhau (cùng 1024 node, cùng ~128 KB dòng cache). Cache không thể giải thích khác biệt này. Chỉ có một biến khác nhau: spread đụng 1024 trang, dense đụng ~16 trang. Phần 15 lần đó là TLB miss → page walk, đo được tách bạch.

Và các ngưỡng của spread lộ cấu trúc TLB: nhanh tới N≈128, bắt đầu đắt ở N=256 (vượt TLB tầng 1), leo mạnh từ N=1024 (page walk thường xuyên). Nghĩa là L1 TLB của host này giữ khoảng 128–256 mục — mỗi mục một trang 4 KB, nên TLB tầng 1 chỉ "với tới" khoảng 0,5–1 MB nếu dữ liệu trải mỗi trang một ít. Vượt tầm đó, bạn trả page walk dù cache còn rỗng.

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với một niềm tin đã ăn sâu sau sáu phần trước: "tốc độ truy cập bộ nhớ do cache quyết định — dữ liệu ở tầng nào thì nhanh chậm theo tầng đó, hết". Con số bác ngay: dense và spread ở N=1024 chạm cùng số dòng cache, cùng ~128 KB — theo mô hình cache thuần chúng phải bằng nhau. Nhưng spread chậm 15 lần (14 ns so với 0,9 ns) chỉ vì nó trải trên 1024 trang thay vì ~16. Cache đầy đủ không cứu được: page walk cộng thêm bất kể dữ liệu có sẵn trong cache hay chưa. Có một tầng phí thứ hai — TLB — đếm theo số trang, và nếu chỉ nhìn cache tôi sẽ không bao giờ giải thích được khác biệt 15 lần này.

Nhưng nếu vì thế mà nghĩ "mọi truy cập bộ nhớ đều phải dịch địa chỉ, nên chi phí dịch là hằng số, chẳng cần bận tâm" thì cũng sai. Dịch địa chỉ rất không đều. Khi ánh xạ trang nằm trong TLB (dense), dịch gần như miễn phí, ẩn hoàn toàn dưới truy cập — cô lễ tân thuộc phòng. Khi nó không trong TLB (spread rộng), page walk ngốn chục-trăm chu kỳ mỗi lần — cô phải lật sổ; đo được spread N=32768 lên 101 ns còn dense chỉ 6,77 ns. Cùng là "truy cập một số từ bộ nhớ", nhưng một bên trả giá dịch bằng 0, bên kia trả gấp bội. Chi phí dịch địa chỉ có cấu trúc, và cấu trúc đó là số trang bạn trải ra so với sức chứa TLB.

Về đến code hằng ngày

Việc đầu tiên: gom dữ liệu nóng vào ít trang, tránh trải mỏng. Một cấu trúc buộc truy cập rải rác nhiều trang — bảng băm khổng lồ chạm ngẫu nhiên, danh sách liên kết node rải khắp heap, bước nhảy lớn qua mảng thưa — đốt TLB dù tổng dữ liệu chạm nhỏ. Gói dữ liệu bạn dùng cùng lúc vào chung ít trang (giống nguyên tắc gói vào ít dòng cache, nhưng ở quy mô trang) giữ ánh xạ trong TLB. Đây cũng là một mặt của phân mảnh bộ nhớ: dữ liệu vỡ vụn khắp nhiều trang không chỉ phí RAM mà còn phí TLB.

Việc thứ hai: biết tới huge page khi làm việc với vùng nhớ lớn. Trang lớn (2 MB thay vì 4 KB) khiến một mục TLB phủ được vùng lớn gấp 512 lần — cùng số mục TLB "với tới" bộ nhớ xa hơn hẳn, giảm mạnh page walk cho các workload duyệt vùng lớn (cơ sở dữ liệu, mảng khoa học, máy ảo). Nhiều hệ thống bật transparent huge pages tự động; khi tối ưu vùng nhớ rất lớn, đây là một nút chỉnh có thật.

Cái tầng ẩn này giải thích được vài chuyện khó hiểu ở tầng cao mà người ta thường đổ nhầm cho cache. Một database như PostgreSQL hay các JVM heap lớn (hàng chục GB) thường khuyến nghị bật huge page chính vì lý do TLB: heap khổng lồ trải trên hàng triệu trang 4 KB làm TLB miss liên miên, và huge page cắt số ánh xạ cần thiết đi 512 lần. Trong Java, một mảng long[] liền mạch không chỉ thắng một LinkedList vì cache và prefetch, mà còn vì các node linked-list rải khắp heap đụng nhiều trang hơn — cộng thêm áp lực TLB. Ở phía ngôn ngữ có GC, một bộ thu gom nén (compacting) dồn object sống lại gần nhau vô tình cũng giảm số trang nóng, giúp TLB. Nguyên tắc chung không đổi: giữa CPU và RAM có hai tầng phí — cache dữ liệu và TLB dịch địa chỉ — và gom dữ liệu lại gần nhau trả cổ tức cho cả hai.

Muốn tự thấy thì cấp một buffer lớn, căn theo trang. Dựng hai chu trình đuổi con trỏ trên cùng N node: bản spread đặt mỗi node cách nhau đúng một trang (4 KB, hoặc 16 KB nếu máy bạn dùng trang lớn), bản dense xếp node sát nhau mỗi 64 byte. Cả hai chạm cùng số node, cùng số dòng cache. Đuổi p = next[p] vài chục triệu lần, lấy min, chia ra ns mỗi truy cập. Quét N: 64, 256, 1024, 4096. Bạn sẽ thấy dense phẳng cho tới khi dữ liệu vượt cache, còn spread leo sớm hơn nhiều — và ở một N mà cả hai chạm cùng lượng dòng cache, spread chậm gấp cả chục lần. Phần chênh đó không phải cache (cùng footprint) — nó là TLB miss, page walk cộng thêm cho mỗi trang mới. Điểm spread bắt đầu đắt cho bạn số mục TLB của máy. Ba mươi giây đó cho thấy điều mà "cache là tất cả" giấu đi: trước khi chạm được dữ liệu, CPU còn phải dịch địa chỉ — và nếu bạn trải quá nhiều trang, chính việc dịch đó là thứ làm bạn chậm.