Bạn viết một microbenchmark, chạy nó trên một mảng vài chục KB, và thấy 0,9 ns mỗi phần tử — tuyệt vời. Rồi lên production với dữ liệu vài trăm MB, và nó chậm gấp trăm lần. Không phải code sai; là kích thước dữ liệu đã đổi. Phần 5 đo bậc thang cache bằng độ trễ; phần này dùng cùng hiện tượng để rút một bài học về đo lường: cùng một thuật toán O(n), chi phí mỗi phần tử thay đổi hàng trăm lần tùy dữ liệu vừa tầng cache nào — nên một con số benchmark chỉ có nghĩa kèm kích thước. Tôi quét kích thước từ vài KB tới 256 MB trong container gcc:13 trên host ARM.
Cùng thao tác, chi phí mỗi phần tử tùy working set
Tôi lấy một thao tác O(n) đơn giản — đuổi con trỏ qua n phần tử — và quét kích thước working set, đo ns mỗi phần tử, cả kiểu truy cập tuần tự (dự đoán được, prefetch) lẫn ngẫu nhiên:
ns/phần tử theo kích thước working set, host ARM (cùng thuật toán O(n)):
working set | tuần tự | ngẫu nhiên | tầng
------------|---------|------------|-----
32 KB | 0,87 | 0,91 | L1
128 KB | 0,90 | 0,92 | L1
512 KB | 0,80 | 4,26 | L2 (nhảy!)
8 MB | 0,27 | 7,82 | L2
16 MB | 0,30 | 10,6 | L2
32 MB | 0,26 | 48,4 | RAM (nhảy!)
256 MB | 0,24 | 103,9 | RAM
Nhìn cột ngẫu nhiên — một đường cong bậc thang hiện ra. Khi dữ liệu ≤ 128 KB, nó nằm gọn trong L1: 0,91 ns mỗi phần tử. Vượt L1 (512 KB), thời gian nhảy lên 4,26 ns; leo dần qua L2 tới 10,6 ns ở 16 MB; rồi nhảy vọt ở 32 MB lên 48 ns khi ra RAM, và ổn định quanh 104 ns ở 256 MB. Từ L1 (0,91 ns) tới RAM (104 ns) là ~114 lần — cho đúng cùng một thao tác "đọc một phần tử", đúng cùng thuật toán O(n). Chỉ kích thước dữ liệu thay đổi.
Cột tuần tự thì phẳng lì dưới 1 ns ở mọi kích thước — vì prefetcher đoán mẫu và nạp trước, giấu hết bậc thang. Nên cách truy cập quyết định ngang kích thước: cùng dữ liệu lớn, tuần tự nhanh gấp trăm lần ngẫu nhiên.
Một lần tôi đo hớ: "benchmark mảng nhỏ phản ánh thật" và "O(n) là tuyến tính"
Tôi vào đo với thói quen tiện lợi: "chạy microbenchmark trên một mảng gọn (cho nhanh, cho ổn định) là biết hiệu năng thật của thao tác". Đo phá tan: mảng nhỏ vừa L1 báo 0,91 ns — đẹp và ổn định — nhưng chính thao tác ấy trên dữ liệu 256 MB sản xuất tốn 104 ns, chậm 114 lần. Benchmark trên mảng nhỏ nói dối: nó đo tốc độ khi dữ liệu ở L1, không phải khi dữ liệu ở RAM như thực tế. Rất nhiều "tối ưu" trông thắng trên benchmark nhỏ lại vô nghĩa hoặc thua khi dữ liệu tràn cache — phải đo ở đúng quy mô production.
Nhưng đo cũng phá một niềm tin nền tảng của tư duy thuật toán: "thời gian tỉ lệ tuyến tính với n; O(n) là O(n)". Sai một cách tinh vi: O(n) chỉ nói số thao tác tỉ lệ n; nó không nói chi phí mỗi thao tác cố định. Đường cong cho thấy chi phí mỗi phần tử nhảy bậc khi n vượt ranh giới cache — 0,9 ns trong L1, 100 ns ở RAM. "Tuyến tính" chỉ đúng trong một tầng cache; qua ranh giới, hằng số ẩn của O(n) nhảy hàng chục-trăm lần. Hai thuật toán cùng O(n) có thể chênh nhau trăm lần vì một cái giữ working set trong cache còn cái kia không.
Bài học đo lường: cùng thuật toán O(n), ns/phần tử vẽ thành ĐƯỜNG CONG BẬC THANG theo working set: đo (đuổi con trỏ ngẫu nhiên) L1 (≤128KB) 0,91 ns -> L2 (tới 16MB) 4-10 ns -> RAM (≥32MB) 48-104 ns = ~114x từ L1 tới RAM. Tuần tự (prefetch) PHẲNG <1ns mọi cỡ. 'Benchmark mảng nhỏ (L1) phản ánh thật' SAI (nói dối về dữ liệu lớn); 'O(n) luôn tuyến tính' SAI (đúng trong 1 tầng; qua ranh giới hằng số nhảy chục-trăm lần). Nếu tin "benchmark nhỏ đủ" tôi tối ưu cho L1 rồi sốc ở production; nếu tin "O(n) là tuyến tính" tôi bỏ qua hằng số cache định đoạt tốc độ thật.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đo benchmark ở đúng quy mô dữ liệu thật. Nếu production xử lý mảng 500 MB, đừng đo trên 50 KB — hãy đo trên kích thước vượt cache để thấy con số RAM thật. Một tối ưu "nhanh 2x" trên mảng nhỏ có thể không đổi gì khi memory-bound, và ngược lại. Benchmark phải phản ánh working set thật, không phải mảng đồ chơi vừa L1.
Hệ quả thứ hai: biết working set của bạn rơi tầng cache nào, và cố giữ nó gần. Đây là gốc của mọi tối ưu bố cục trong sê-ri: chặn/tiling để làm việc trên khối vừa cache, nén dữ liệu để giảm working set, truy cập tuần tự để prefetch giấu bậc thang. Cùng một O(n), giữ dữ liệu trong cache thắng đưa nó ra RAM cả trăm lần.
Hệ quả thứ ba là tinh thần đo lường: O(n) không kể toàn bộ câu chuyện — hằng số ẩn của nó là một hàm của working set. Con số mang theo: ns/phần tử = đường cong bậc thang theo kích thước (L1 ~1ns, L2 vài ns, RAM ~100ns, chênh ~114x); tuần tự phẳng nhờ prefetch. Đo ở đúng quy mô sản xuất; giữ working set trong cache. Cùng một thuật toán, trên dữ liệu nhỏ hay lớn, nhanh chậm cách nhau trăm lần — và chỉ đo trên đúng kích thước thật mới cho bạn con số không dối.
Thử ba mươi giây
Viết một chương trình đuổi con trỏ (như phần 5) và chạy nó với kích thước mảng tăng dần: 8 KB, 64 KB, 256 KB, 2 MB, 16 MB, 64 MB, 256 MB — mỗi lần đo ns mỗi bước. Vẽ kết quả lên đồ thị (trục hoành log kích thước, trục tung ns): bạn sẽ thấy một bậc thang — phẳng thấp trong L1, nhảy lên khi vượt L1, phẳng cao trong L2, nhảy lần nữa ra RAM. Các ngưỡng nhảy cho bạn kích thước cache của máy; độ cao mỗi bậc cho bạn độ trễ mỗi tầng. Rồi làm lại với next[i] = i+1 (tuần tự): đường cong phẳng ở mọi kích thước, vì prefetch. Cuối cùng, tưởng tượng bạn chỉ đo một điểm — mảng 64 KB — và báo cáo "thao tác này tốn 0,9 ns": con số ấy đúng cho L1 nhưng dối cho production 256 MB (104 ns). Ba mươi giây đó cho bạn thấy điều mà một phép đo đơn lẻ giấu đi: hiệu năng không phải một con số, mà một đường cong theo kích thước dữ liệu — và bạn phải đo ở đúng điểm mà production đang đứng.
