Dữ liệu nằm sẵn trong cache mà vẫn chậm 1,52 lần — thủ phạm là cache thứ hai ai cũng quên

Hình dung một tổng đài viên: khách gọi tới bằng "mã đặt phòng" nhưng nhân viên cần biết "số phòng thật" để nối máy. Có một cuốn danh bạ nhỏ để ngay trên bàn ghi các mã vừa tra gần đây — mã nào có trong đó thì nối ngay tức khắc. Mã nào không có, phải chạy xuống kho lật cuốn sổ tổng dày cộp, mất thời gian. Cuốn danh bạ trên bàn chỉ chứa được ít mã; nếu khách gọi rải rác khắp một danh sách khổng lồ, tổng đài viên liên tục phải chạy xuống kho — dù người khách cần nối máy đang ngồi ngay phòng bên cạnh. Cuốn danh bạ nhỏ đó là TLB của CPU, và nó là một cache thứ hai mà hầu như ai cũng quên khi tối ưu bộ nhớ.

Ở phần page fault và chuyển ngữ cảnh ta gặp một cái tên: TLB. Giờ đo nó trực tiếp. Khi ta nói tối ưu truy cập bộ nhớ, hầu như ai cũng nghĩ tới cache dữ liệu (L1/L2/L3). Nhưng có một cache thứ hai, ít được nhắc mà cũng giới hạn tốc độ y như vậy: TLB — cache của các bản dịch địa chỉ từ ảo sang vật lý. Bài này đo cái giá khi vượt quá tầm phủ của TLB, và tách nó ra khỏi cache dữ liệu — trong container gcc:13 (ARM).

Vì sao mỗi truy cập cần một bản dịch

Chương trình của bạn dùng địa chỉ ảo, nhưng phần cứng đọc/ghi theo địa chỉ vật lý — đúng mã đặt phòng so với số phòng thật. Mỗi lần truy cập bộ nhớ, CPU phải dịch ảo → vật lý bằng cách tra bảng trang (page table). Bảng trang nằm trong RAM và có nhiều tầng, nên tra nó mỗi lần thì quá chậm. Giải pháp: TLB (Translation Lookaside Buffer) — một cache nhỏ chứa các bản dịch gần đây, ngay trong CPU (cuốn danh bạ trên bàn). TLB rất nhỏ: thường ~64 mục ở tầng L1, ~1.000–2.000 mục ở tầng L2.

Khi bản dịch cần thiết có trong TLB (TLB hit), việc dịch gần như tức thì. Khi không có (TLB miss), CPU phải đi bộ bảng trang (page-table walk) — vài lần truy cập bộ nhớ để lần theo các tầng bảng — rồi mới có địa chỉ vật lý. Đó là cái chạy-xuống-kho, chi phí thêm cho mỗi truy cập bị miss.

Điểm mấu chốt: TLB chỉ phủ được số mục × cỡ trang bộ nhớ. Với trang 4 KB và ~2.000 mục TLB L2, tầm phủ chỉ khoảng 8 MB. Nếu vùng làm việc của bạn trải rộng hơn 8 MB (về địa chỉ, không phải dung lượng dữ liệu chạm), TLB không đủ chỗ cho mọi bản dịch, và bạn bắt đầu miss liên tục — dù dữ liệu vẫn nằm gọn trong cache.

Đo: đường cong, và tách TLB khỏi cache

Tôi duyệt một chuỗi con trỏ, mỗi con trỏ nằm ở đầu một trang khác nhau (bước nhảy đúng 1 trang), theo thứ tự hoán vị ngẫu nhiên, chỉ chạm một phần tử mỗi trang. Tăng dần số trang để mở rộng tầm địa chỉ:

   16 trang (0,1 MB) :   0,7 ns/truy cập
  256 trang (1,0 MB) :  10,0 ns
 1024 trang (4,2 MB) :   8,6 ns
 4096 trang (16,8 MB):  38,4 ns
16384 trang (67,1 MB):  53,5 ns
65536 trang (268 MB) : 123,6 ns

Đường cong tăng mạnh khi tầm địa chỉ lớn lên. Nhưng — thành thật — phép đo này lẫn hai hiệu ứng: chạm các trang khác nhau vừa vượt tầm phủ TLB, vừa vượt cache (mỗi trang một cache line). Để tách riêng TLB, tôi so cùng một tầm 67 MB nhưng đổi cỡ trang: trang 4 KB (cần 16.384 mục TLB) so với huge page 2 MB (chỉ cần 34 mục cho cùng 67 MB):

span 67 MB, chase 1 con trỏ/trang:
  trang 4 KB (thường)  : 54,1 ns
  huge page 2 MB       : 35,5 ns
  -> 4KB chậm 1,52×  (chênh ~19 ns)

Với huge page, cùng vùng 67 MB chỉ cần 34 bản dịch — vừa khít TLB, gần như không miss. Với trang 4 KB, cần 16.384 bản dịch — vượt xa TLB, miss liên tục. Dữ liệu chạm y hệt, cache y hệt — khác biệt duy nhất là số bản dịch TLB. Nên ~19 ns chênh lệch đó là chi phí TLB miss thuần (một page-table walk mỗi truy cập). (AnonHugePages trong /proc/meminfo xác nhận huge page thực sự được cấp.)

(Môi trường đo: container gcc:13 trên host ARM AArch64, chase 1 con trỏ mỗi trang theo hoán vị ngẫu nhiên, mỗi số lấy sau warmup. Con số tuyệt đối và tầm phủ TLB đổi theo CPU; cái bền vững là: vượt tầm phủ TLB thì mỗi truy cập gánh thêm một page-table walk, và tách được nó khỏi cache bằng cách đổi cỡ trang.)

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

Tôi vào đo với niềm tin phổ biến: "tốc độ truy cập bộ nhớ chỉ do cache dữ liệu quyết định — dữ liệu vào được L1/L2 là nhanh, ra DRAM là chậm". Đúng, nhưng thiếu. Phép đo tách trang cho thấy: cùng dữ liệu, cùng hành vi cache, mà đổi cỡ trang thôi đã làm chậm 1,52 lần. Cái làm chậm không phải nơi dữ liệu nằm, mà nơi bản dịch địa chỉ nằm. Có một cache thứ hai — TLB — và nó cũng có thể là nút thắt.

Niềm tin ngược, và là cái bẫy thực tế hơn: "thấy truy cập bộ nhớ chậm thì chắc chắn do cache miss dữ liệu — cứ tối ưu bố cục cache là xong". Đây là cách người ta tối ưu nhầm cache: một chương trình truy cập ngẫu nhiên một vùng rộng (bảng băm lớn, cây trải khắp bộ nhớ, ma trận thưa) có thể có phần lớn dữ liệu nóng trong cache nhưng vẫn chậm — và mọi nỗ lực "làm dữ liệu vừa cache hơn" không cứu được, vì nút thắt là bản dịch không vừa TLB. Bạn sẽ bối rối vì sao "dữ liệu trong cache mà vẫn chậm", loay hoay tối ưu sai chỗ, cho tới khi nhìn ra cache thứ hai. Sự thật: "dữ liệu nằm trong cache" chưa đủ để nhanh — bản dịch địa chỉ cũng phải nằm trong TLB. Đây cũng là lý do huge page tồn tại: một mục TLB phủ 2 MB thay vì 4 KB, nới tầm phủ TLB lên 512 lần, biến hàng nghìn TLB miss thành gần như không — điều phần sau về huge page đo kỹ hơn.

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

Điều đầu tiên: khi truy cập ngẫu nhiên một vùng lớn, TLB — không chỉ cache — có thể là nút thắt. Nếu cấu trúc dữ liệu của bạn trải rộng hơn ~8 MB tầm địa chỉ và bị truy cập ngẫu nhiên, hãy nghi TLB miss ngay cả khi dữ liệu vừa cache. Dấu hiệu: chậm hơn dự đoán từ mô hình "chỉ cache", và cải thiện khi bật huge page.

Điều thứ hai: bố cục gọn về địa chỉ giúp cả cache lẫn TLB. Gom dữ liệu nóng vào ít trang (mảng liên tục thay vì con trỏ rải rác, cấu trúc-của-mảng thay vì mảng-của-cấu-trúc) giảm số trang chạm, nên giảm cả cache miss lẫn TLB miss. Và với vùng lớn truy cập nhiều, cân nhắc huge page (madvise(MADV_HUGEPAGE) hay MAP_HUGETLB) để một mục TLB phủ 2 MB.

Chỗ này cái "cache thứ hai" giải thích nhiều bí ẩn hiệu năng ở tầng cao. Đây là một lý do sâu vì sao pointer-chasing (linked list, cây, đồ thị với node rải rác qua new/malloc) chậm hơn nhiều so với duyệt một mảng liên tục cùng kích thước: không chỉ cache miss, mà mỗi node ở một trang mới còn là một TLB miss. Đây cũng là vì sao GC nén (compacting GC của Java) và bố cục cột (columnar) trong database giúp: gom dữ liệu về gần nhau trên trang cải thiện cả hai cache. Database lớn cấp buffer pool bằng huge page chính để né TLB miss khi truy cập ngẫu nhiên hàng chục GB. Và khi một kỹ sư hiệu năng nhìn perf stat thấy dTLB-load-misses cao, họ biết ngay thủ phạm là cache thứ hai này, không phải cache dữ liệu. Cùng một bài học cuốn-danh-bạ-nhỏ, ẩn dưới nhiều "vì sao chậm" khó hiểu.

Muốn tự thấy thì nghĩ về cấu trúc dữ liệu lớn nhất mà chương trình của bạn truy cập ngẫu nhiên — một hash map nhiều triệu phần tử, một đồ thị, một chỉ mục. Ước lượng nó trải bao nhiêu megabyte địa chỉ. Nếu hơn ~8 MB và bị truy cập ngẫu nhiên (không tuần tự), thì ngay cả khi phần dữ liệu nóng vừa cache, mỗi truy cập vẫn có thể trả một TLB miss (~vài chục ns). Chạy perf stat -e dTLB-load-misses ./chương-trình (nếu máy bạn có perf) để xem con số thật. Vài phút ước lượng "tầm địa chỉ" đó — khác với "dung lượng dữ liệu" — cho bạn một trực giác mà mô hình "chỉ cache" bỏ lỡ: đôi khi thứ chậm không phải lấy dữ liệu, mà là dịch địa chỉ để tới được dữ liệu.