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 đo thẳng vào nó: bộ nhớ không phải một khối phẳng với một tốc độ. Nó phân tầng — L1 nhỏ và nhanh, L2 lớn hơn và chậm hơn, L3/SLC lớn hơn nữa, rồi RAM lớn nhất và chậm nhất. CPU tự động giữ dữ liệu nóng ở tầng gần. Câu hỏi đo lường: 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ỏ (pointer chase) 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. Đế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 — 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.
Một lần tôi đo hớ: "truy cập bộ nhớ tốn như nhau" và "chỉ cần biết O(n)"
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". Đo phá tan: 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 đo cũng phá một niềm tin ngược mà dân thuật toán hay có: "chỉ cần biết độ phức tạp O(n), cache là chi tiết phần cứng nhỏ nhặt". 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.
Bài học đo lường: bộ nhớ phân TẦNG — đuổi con trỏ (ngẫu nhiên, defeat prefetch) quét kích thước cho BẬC THANG độ trễ: L1 0,91 ns tới RAM 103 ns = ~113x theo tầng; ngưỡng nhảy (đo: ~128KB, ~16MB, 32MB) chính là kích thước L1/L2/cache cuối của máy. Truy cập TUẦN TỰ được prefetch giấu hết phân tầng (phẳng 0,24 ns). 'Một truy cập bộ nhớ' không có giá cố định — tùy dữ liệu ở tầng nào VÀ truy cập tuần tự hay ngẫu nhiên. Nếu tôi tin "truy cập tốn như nhau" tôi không giải thích được khác biệt 100x; nếu tin "cache là chi tiết nhỏ" tôi bỏ qua thứ định đoạt hằng số của O(n).
Vì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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.
Hệ quả thứ ba là tinh thần đo lường: bộ nhớ là một bậc thang, và biết máy mình có tầng nào giúp đặt kỳ vọng đúng. Con số mang theo: độ trễ truy cập ngẫu nhiên nhảy theo tầng (L1 ~1 ns, L2 ~vài ns, RAM ~trăm ns, chênh ~100x); ngưỡng nhảy = kích thước tầng cache (đo được của máy); tuần tự (prefetch) phẳng và nhanh mọi kích thước. Giữ dữ liệu nóng trong cache và truy cập tuần tự. Đo cache hierarchy của máy bạn một lần — nó giải thích phần lớn những khác biệt hiệu năng mà Big-O không nói.
Thử ba mươi giây
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 bạn 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.
