Nhiều lần trong hai sê-ri, "cache" hiện ra như thủ phạm giấu mặt sau những khác biệt hiệu năng khó hiểu. Phần này tôi đo thẳng vào nó.

Hình dung chỗ bạn ngồi làm việc. Thứ hay dùng nhất nằm ngay trên mặt bàn — với tay là có. Thứ dùng ít hơn ở ngăn kéo — mở ra mất một giây. Nhiều hơn nữa thì trong tủ hồ sơ cuối phòng — phải đứng dậy đi lấy. Còn thứ hiếm khi đụng thì cất dưới kho — mất cả buổi. Không ai để tất cả lên mặt bàn (không đủ chỗ), cũng không ai cất mọi thứ dưới kho (quá chậm). Bộ nhớ máy tính tổ chức y hệt: nó không phải một khối phẳng với một tốc độ, mà phân tầng — L1 nhỏ và nhanh (mặt bàn), L2 lớn hơn và chậm hơn (ngăn kéo), L3/SLC lớn hơn nữa (tủ hồ sơ), rồi RAM lớn nhất và chậm nhất (kho). CPU tự động giữ dữ liệu nóng ở tầng gần. Câu hỏi đo: mỗi tầng nhanh chậm ra sao, và máy này có những tầng cỡ nào? Tôi đo bằng kỹ thuật đuổi con trỏ trong container gcc:13 trên host ARM, và đường cong kết quả — một bậc thang — vừa cho thấy khoảng cách trăm lần giữa các tầng, vừa tiết lộ kích thước từng tầng cache của máy.

Đuổi con trỏ để lộ độ trễ mỗi tầng

Muốn đo độ trễ thật của một tầng cache, phải ngăn CPU "gian lận" bằng prefetch (đoán trước và nạp sẵn dữ liệu). Kỹ thuật kinh điển là đuổi con trỏ: tạo một chu trình ngẫu nhiên (một hoán vị) qua vùng làm việc, rồi lặp p = next[p]. Vì địa chỉ tiếp theo phụ thuộc giá trị vừa đọc, CPU không thể prefetch — mỗi truy cập phải đợi truy cập trước xong và trả đúng độ trễ của tầng chứa dữ liệu.

Rồi quét kích thước vùng làm việc từ vài KB tới hàng trăm MB. Khi vùng còn nhỏ, nó nằm gọn trong L1 → mọi truy cập nhanh. Khi vùng vượt L1, dữ liệu tràn xuống L2 → độ trễ nhảy lên. Vượt L2 → L3. Vượt L3 → RAM. Đường cong ns/truy cập theo kích thước là một bậc thang, và mỗi ngưỡng nhảy đánh dấu kích thước một tầng cache.

Đo: bậc thang từ 0,9 ns tới 103 ns

Tôi đuổi con trỏ trên các vùng từ 4 KB tới 256 MB, đo ns mỗi truy cập, và so với truy cập tuần tự (được prefetch):

Đuổi con trỏ, ns/truy cập theo kích thước vùng làm việc, host ARM, g++ -O2:

   vùng làm việc  | ngẫu nhiên (đuổi con trỏ) | tuần tự (prefetch)
   ---------------|---------------------------|-------------------
   4 – 128 KB     |  0,91 ns                  |  ~0,9 ns   <- L1
   256 KB         |  3,50 ns  (nhảy!)         |  0,59 ns
   1 MB           |  5,50 ns                  |  0,37 ns
   8 MB           |  7,78 ns                  |  0,26 ns
   16 MB          | 10,94 ns                  |  0,25 ns   <- L2
   32 MB          | 46,22 ns  (nhảy!)         |  0,25 ns
   128 MB         | 92,70 ns                  |  0,24 ns
   256 MB         | 103,18 ns                 |  0,24 ns   <- RAM

Nhìn cột ngẫu nhiên — bậc thang hiện rõ. Từ 4 tới 128 KB, mọi truy cập tốn đúng 0,91 ns: dữ liệu nằm gọn trong L1, thứ trên mặt bàn. Đến 256 KB, thời gian nhảy lên 3,50 ns — vùng đã vượt L1, tràn xuống tầng sau. Nó leo dần tới 10,94 ns ở 16 MB (tầng L2 rộng). Rồi ở 32 MB nhảy vọt lên 46,22 ns — vượt tầng cache cuối, ra RAM (xuống kho) — và ổn định quanh 92–103 ns ở các vùng lớn. Từ L1 (0,9 ns) tới RAM (103 ns) là ~113 lần khác biệt, cho cùng một thao tác "đọc một số từ bộ nhớ".

Và các ngưỡng nhảy tiết lộ kiến trúc máy: nhảy ở ~128–256 KB → L1 cỡ 128 KB; leo phẳng tới ~16 MB → L2 cỡ 16 MB; nhảy lớn ở 32 MB → hết cache, sang RAM. (Đây trông giống một lõi Apple Silicon: L1 lớn 128 KB, L2 chung nhiều MB, không có L3 truyền thống. Kích thước cache khác nhau theo máy — đo mới biết máy của bạn.)

Nhìn cột tuần tự: truy cập theo thứ tự (bước 1) phẳng lì ~0,24–0,9 ns ở mọi kích thước, kể cả 256 MB. Vì prefetcher đoán được mẫu tuần tự và nạp dữ liệu trước khi CPU cần — nó giấu hoàn toàn phân tầng. Cùng dữ liệu, cùng lượng, nhưng truy cập tuần tự không thấy bậc thang nào. Đây là bằng chứng vì sao cách truy cập quan trọng ngang đâu là dữ liệu.

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

Tôi vào đo với mô hình đơn giản nhất: "đọc một ô nhớ tốn một lượng cố định, RAM là RAM". Con số bác ngay: cùng một thao tác đọc, thời gian nhảy 113 lần tùy dữ liệu nằm ở tầng nào — 0,91 ns nếu ở L1, 103 ns nếu ở RAM. Bộ nhớ là một bậc thang, không phải một mặt phẳng. "Truy cập bộ nhớ tốn như nhau" là mô hình sai đến mức nó khiến bạn không thể giải thích tại sao hai vòng lặp "cùng số phép đọc" chênh nhau cả trăm lần — câu trả lời luôn là working set của chúng rơi vào tầng cache nào.

Nhưng nếu vì thế mà nghĩ ngược — "vậy chỉ cần biết độ phức tạp O(n), cache là chi tiết phần cứng nhỏ nhặt" — thì cũng sai. Cache quyết định hằng số của O(n), và hằng số đó chênh trăm lần. Cùng một thuật toán O(n) duyệt một mảng chạy nhanh khi mảng vừa L1, rồi chậm 100 lần khi mảng tràn ra RAM — cùng độ phức tạp, cùng số thao tác, khác nhau ở dữ liệu ở tầng nào. Và truy cập tuần tự (được prefetch) phẳng 0,24 ns còn giấu hết bậc thang — nên bố cục dữ liệu và mẫu truy cập cũng quyết định hiệu năng ngang Big-O. Bỏ qua cache là bỏ qua thứ thường chi phối thời gian chạy thật.

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

Việc đầu tiên: giữ working set nóng vừa trong tầng cache gần nhất có thể. Nếu phần dữ liệu bạn chạm liên tục vừa L1/L2, code nhanh gấp trăm lần so với khi nó tràn RAM. Đây là lý do chặn (blocking/tiling) trong nhân ma trận, xử lý theo lô vừa cache, và giữ cấu trúc dữ liệu nhỏ gọn lại quan trọng đến thế — không phải để giảm số thao tác, mà để giữ dữ liệu ở tầng nhanh.

Việc thứ hai: truy cập tuần tự bất cứ khi nào được — prefetch là bạn. Một vòng lặp quét mảng theo thứ tự được prefetcher che gần hết độ trễ (phẳng ~0,24 ns dù dữ liệu ở RAM), trong khi truy cập ngẫu nhiên/đuổi-con-trỏ trả đủ độ trễ tầng (tới 100 ns). Đây là gốc rễ của mảng thắng linked list, của việc thích chỉ số hơn con trỏ, của SoA hơn AoS: tất cả để giữ truy cập tuần tự và dữ liệu liền.

Cái bậc thang này không dừng ở CPU — nó là mô hình chung của cả ngành lưu trữ, chỉ đổi tên các tầng. Kiến trúc máy tính vẽ nó thành một kim tự tháp kéo dài: thanh ghi → L1/L2/L3 → RAM → SSD → ổ cứng → mạng, mỗi tầng lớn hơn và chậm hơn tầng trên cả bậc độ lớn. Redis và memcached tồn tại chính vì chúng là "cache trên bàn" đặt trước một database "dưới kho"; page cache của hệ điều hành giữ dữ liệu đĩa nóng trong RAM; CDN là cache đặt gần người dùng để né chuyến đi xa tới máy chủ gốc. Trong Java, buffer pool của database hay heap nóng vừa cache CPU đều là cùng một bài toán "giữ thứ hay dùng ở tầng gần". Con số đáng nhớ — chênh ~100 lần mỗi khi tụt một tầng — là lý do vì sao "nó vừa cache hay chưa" thường quyết định hiệu năng nhiều hơn cả thuật toán. Đo cache hierarchy của máy bạn một lần, và bạn có một lăng kính giải thích được phần lớn khác biệt hiệu năng mà Big-O im lặng.

Muốn tự thấy thì viết một chương trình đuổi con trỏ: cấp một mảng next[] kích thước S, điền nó thành một hoán vị ngẫu nhiên tạo một chu trình (thuật toán Sattolo cho một chu trình duy nhất), rồi lặp p = next[p] vài chục triệu lần và chia thời gian cho số bước. Chạy với S tăng dần: 8 KB, 64 KB, 256 KB, 2 MB, 16 MB, 64 MB, 256 MB. Bạn sẽ thấy ns/truy cập nhảy bậc mỗi khi vùng vượt một tầng cache — và các ngưỡng nhảy cho bạn biết L1/L2/L3 của máy cỡ nào. Rồi làm lại với next[i] = i+1 (truy cập tuần tự) và đo: lần này thời gian phẳng và nhanh ở mọi kích thước, vì prefetcher nạp trước. Ba mươi giây đó cho thấy điều mà "đọc một ô nhớ tốn một lượng cố định" giấu đi: bộ nhớ có tầng, mỗi tầng chậm hơn tầng trên cả chục lần, và cả nơi dữ liệu nằm lẫn cách bạn đi qua nó quyết định code chạy nhanh hay chậm trăm lần.