Cảnh này quen với ai từng đo hiệu năng: bạn viết một microbenchmark, chạy nó trên một mảng vài chục KB, thấy 0,9 ns mỗi phần tử — tuyệt vời, ghi vào slide. Rồi đẩy lên production với dữ liệu vài trăm MB, và nó chậm gấp trăm lần. Bạn ngồi soi lại code, không tìm ra lỗi nào. Đúng là không có lỗi. Cái đổi không phải code, mà là kích thước dữ liệu.
Hãy nghĩ về nó như đi lấy đồ trong nhà. Món để trên bàn làm việc lấy tức thì; món trong tủ bếp phải đứng dậy đi vài bước; món trong nhà kho ngoài vườn thì mất cả buổi. Vẫn là động tác "đi lấy một món", nhưng thời gian tùy món đó nằm ở đâu. Cache của CPU y hệt: cùng thao tác "đọc một phần tử", giá phải trả tùy dữ liệu đang nằm tầng nào. Phần 5 đã đo bậc thang cache bằng độ trễ; ở đây tôi dùng chính 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 khi kèm kích thước. Tôi quét working set 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 nhất có thể — đ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 trước — một đường bậc thang hiện ra rõ mồn một. Dữ liệu ≤ 128 KB 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, ổn định quanh 104 ns ở 256 MB. Từ L1 (0,91 ns) tới RAM (104 ns) là khoảng 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). Thứ duy nhất đổi là kích thước dữ liệu.
Còn cột tuần tự thì phẳng lì dưới 1 ns ở mọi kích thước — vì prefetcher đoán được mẫu và nạp trước, giấu sạch bậc thang. Nên cách bạn truy cập quan trọng 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. Chi tiết này về sau tôi thấy còn quan trọng hơn cả cái bậc thang, vì nó là thứ mình điều khiển được.
Hai điều đo cho tôi tỉnh ra
Tôi vào đo với một thói quen tiện lợi mà chắc nhiều người có: "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". Con số cho thấy thói quen đó lừa mình: 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 như production tốn 104 ns — chậm 114 lần. Benchmark trên mảng nhỏ đo tốc độ khi dữ liệu ở L1, không phải khi dữ liệu ở RAM như thực tế nó phải chạy. Rất nhiều "tối ưu" trông thắng đậm trên benchmark nhỏ lại vô nghĩa, thậm chí thua, khi dữ liệu tràn cache. Muốn con số có nghĩa thì phải đo ở đúng quy mô production.
Điều thứ hai đụng vào một niềm tin nền tảng hơn, thứ ai học thuật toán cũng mang theo: "thời gian tỉ lệ tuyến tính với n; O(n) là O(n)". Nó sai một cách tinh vi. O(n) chỉ nói số thao tác tỉ lệ với n; nó không hề 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 phạm vi một tầng cache; qua ranh giới, hằng số ẩn của O(n) nhảy hàng chục tới hàng trăm lần. Đây là lý do hai thuật toán cùng O(n) có thể chênh nhau cả trăm lần: một cái giữ working set gọn trong cache, cái kia thì không.
Rút gọn lại thì hai câu này đáng dán lên tường: benchmark trên mảng vừa L1 nói dối về dữ liệu lớn, và "O(n) tuyến tính" chỉ đúng bên trong một tầng cache. Nếu tin cái thứ nhất, bạn tối ưu cho L1 rồi lãnh cú sốc ở production. Nếu tin cái thứ hai, bạn bỏ qua đúng cái hằng số cache đang định đoạt tốc độ thật.
Về đến code hằng ngày
Việc đầu tiên, và trực tiếp nhất: đo ở đú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ể chẳng đổi gì khi bài toán memory-bound, và đôi khi ngược lại. Benchmark phải phản ánh working set thật, không phải một mảng đồ chơi vừa vặn L1.
Tiếp theo: biết working set của bạn rơi vào tầng cache nào, và cố giữ nó gần. Đây là gốc rễ của gần như mọi tối ưu bố cục trong sê-ri này: chặn/tiling để làm việc trên khối vừa cache, nén dữ liệu để thu nhỏ 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.
Cái bẫy này không dừng ở C. Nó theo bạn lên tận tầng cao, chỉ là khoác áo khác. Một HashMap Java vài triệu entry đọc ngẫu nhiên đúng là mẫu "đuổi con trỏ ngẫu nhiên" trong bài — mỗi get() là một cú nhảy RAM, và JMH chạy trên map nhỏ sẽ giấu chuyện đó y như microbenchmark C ở đây. Một map[key] trong Go, một lần nạp lazy quan hệ trong ORM cũng vậy. Còn phía database thì cả ngành đã đặt tên cho đúng cái bậc thang này: một index scan gọn trong buffer pool nhanh khủng khiếp, cùng câu truy vấn khi bảng vượt RAM và phải đọc đĩa thì rơi xuống một tầng chậm nữa — cùng "đường cong theo kích thước", chỉ là các tầng mang tên buffer pool và ổ đĩa thay vì L1 và RAM. Quy tắc chung không đổ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.
Muốn tự thấy thì nhanh thôi. Viết một chương trình đuổi con trỏ (như phần 5) và chạy 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ẽ lên đồ thị (trục hoành log kích thước, trục tung ns): bạn sẽ thấy đúng một bậc thang — phẳng thấp trong L1, nhảy 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, nhờ 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). Đó, chỉ ba mươi giây mà thấy được điều mà một phép đo đơn lẻ luôn giấu đi.
