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). Mọi địa chỉ chương trình bạn dùng là địa chỉ ảo — phần cứng phải dịch nó sang địa chỉ vật lý thật, theo từng trang nhớ. TLB là cache nhỏ giữ vài trăm-nghìn á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.
Đ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.
Một lần tôi đo hớ: "chỉ cache mới quyết định" và "dịch địa chỉ nào cũng như nhau"
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". Đo phá tan: 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 đo cũng phá một niềm tin ngược: "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". 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. Khi nó không trong TLB (spread rộng), page walk ngốn chục-trăm chu kỳ mỗi lần — đ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.
Bài học đo lường: mỗi truy cập bộ nhớ phải DỊCH địa chỉ ảo -> vật lý theo TRANG; TLB cache vài trăm ánh xạ trang. Trải NHIỀU TRANG hơn TLB chứa -> TLB miss -> page walk cộng thêm chục-trăm chu kỳ, NGOÀI chi phí cache. Đo: cùng ~128KB dòng cache, spread 1024 trang 14 ns vs dense ~16 trang 0,9 ns = 15x thuần TLB; L1 TLB ~128-256 mục (trang 4KB đo được). 'Chỉ cache quyết định' và 'dịch địa chỉ nào cũng như nhau' đều SAI. Nếu tin cache là tất cả tôi bỏ sót một tầng phí; nếu tin dịch địa chỉ là hằng số tôi coi thường page walk.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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.
Hệ quả thứ ba là tinh thần đo lường: giữa CPU và RAM có nhiều hơn một tầng phí — cache dữ liệu và TLB dịch địa chỉ, và chúng đo tách được. Con số mang theo: TLB miss thêm page walk (đo: spread 1024 trang 14 ns vs dense ~16 trang 0,9 ns = 15x, cùng cache footprint); L1 TLB ~128-256 mục, trang 4KB; gom ít trang, cân nhắc huge page. Cùng lượng dữ liệu, cùng số dòng cache chạm, mà cách bạn trải nó qua các trang có thể làm chậm chục lần — thứ Big-O không nói, chỉ đo mới thấy.
Thử ba mươi giây
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 bạn 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.
