Ở bài mở sê-ri, ta thấy big-O là hình dạng khi n lớn, không phải tốc độ ở n cụ thể. Bài này chỉ ra một điều big-O còn hoàn toàn bỏ qua: chi phí truy cập bộ nhớ. Hai vòng lặp cùng độ phức tạp O(n), làm đúng cùng số phép tính, có thể khác nhau hàng trăm lần về tốc độ — chỉ vì chúng chạm bộ nhớ theo hai cách khác nhau. Tôi vào bài với thói quen đếm phép toán, và một lần nữa, cái đồng hồ cho tôi một bài học khó quên.
Big-O đếm phép, nhưng phép không đắt bằng nhau
Big-O đếm số phép: một vòng lặp cộng n phần tử là O(n), dù các phần tử nằm đâu. Nhưng một "phép truy cập bộ nhớ" không phải một chi phí cố định. CPU không đọc thẳng từ RAM; nó đọc qua các tầng cache (L1, L2, L3) — những vùng nhớ nhỏ, cực nhanh, nằm ngay trên chip. Một giá trị nằm trong cache lấy ra mất vài nano giây; một giá trị phải xuống RAM mất khoảng 100 nano giây — chênh nhau cả trăm lần cho cùng một phép load.
Điều quyết định giá trị nằm trong cache hay không là cách bạn truy cập. Khi CPU đọc một địa chỉ, nó nạp cả một dòng cache (thường 64 byte) quanh đó, và bộ prefetch đoán trước bạn sắp đọc vùng kế tiếp để nạp sẵn. Duyệt tuần tự khai thác cả hai: một lần nạp dòng phục vụ nhiều phần tử kề nhau, và prefetch luôn đón đúng. Duyệt ngẫu nhiên phá cả hai: mỗi lần một chỗ khác, dòng cache vừa nạp chỉ dùng một phần tử rồi bỏ, prefetch đoán trượt. Với dòng cache 64 byte và số nguyên 4 byte, một lần nạp tuần tự mang về 16 phần tử — nghĩa là 15 trong 16 lần đọc tiếp theo được phục vụ miễn phí từ cache; còn duyệt ngẫu nhiên lãng phí 15/16 mỗi dòng.
Một lần tôi đo hớ: cùng số phép, chậm 452 lần
Tôi viết hai vòng lặp bằng C, cả hai cộng qua một mảng 256MB (lớn hơn mọi cache), làm đúng cùng số phép load và cộng:
- Tuần tự: đọc phần tử theo thứ tự địa chỉ tăng dần (stride 1).
- Ngẫu nhiên: đi theo một hoán vị — mỗi bước nhảy tới một vị trí ngẫu nhiên khác (con trỏ đuổi con trỏ, kiểu như lần theo một danh sách liên kết rải khắp bộ nhớ).
Cả hai là O(n), cùng n phép cộng. Theo thói quen đếm phép, tôi trông đợi chúng chạy xấp xỉ nhau. Đo bằng clock_gettime, lấy trung vị:
tuần tự : 0,23 ns/phần tử (15 ms cả mảng)
ngẫu nhiên : 103 ns/phần tử (6914 ms cả mảng)
-> ngẫu nhiên chậm 452 lần
Bốn trăm năm mươi hai lần, cho cùng một lượng công việc tính toán — một khoảng cách lớn hơn cả nhiều khác biệt về độ phức tạp big-O mà ta hay lo lắng. Cái sai của tôi là đếm phép cộng và tưởng đó là chi phí; thật ra phép cộng gần như miễn phí, chi phí nằm ở chờ dữ liệu về từ bộ nhớ. Duyệt tuần tự chạy 0,23ns/phần tử — nhanh tới mức nó gần như chỉ giới hạn bởi băng thông bộ nhớ, vì prefetch giữ cho dữ liệu luôn sẵn. Duyệt ngẫu nhiên chạy 103ns/phần tử — đúng bằng độ trễ một chuyến xuống RAM, vì mỗi bước là một cache-miss phải chờ. Một chi tiết đáng nói: kiểu duyệt ngẫu nhiên tôi đo là con-trỏ-đuổi-con-trỏ, nơi địa chỉ kế tiếp phụ thuộc giá trị vừa đọc — CPU không thể chồng lấn các lần chờ, nên đây là trường hợp xấu nhất; một mẫu truy cập ngẫu nhiên nhưng độc lập sẽ đỡ hơn vì CPU gối được nhiều miss. Nhưng nó mô phỏng đúng thứ ta hay gặp: lần theo một danh sách liên kết hay cây rải khắp bộ nhớ.
Đo để chắc: chính cache là thủ phạm
Con số 452 lần đủ ấn tượng, nhưng làm sao chắc cache mới là nguyên nhân, chứ không phải thứ khác? Tôi đo tiếp: chạy cùng phép duyệt ngẫu nhiên trên các mảng cỡ khác nhau, cùng số lần truy cập, chỉ khác kích thước tập làm việc (working set):
working set tuần tự ngẫu nhiên chậm x
16KB (vừa L1) 0,5 ns 0,9 ns 1,9
1MB (vừa L2) 0,5 ns 5,9 ns 12
16MB (vượt L2) 0,5 ns 11,7 ns 24
256MB (RAM) 0,5 ns 103 ns 206
Đây là bằng chứng rõ ràng. Duyệt tuần tự giữ ~0,5ns ở mọi kích thước — prefetch làm việc bất kể mảng lớn cỡ nào. Còn duyệt ngẫu nhiên chậm dần theo bậc thang: khi mảng nhỏ đủ nằm trong L1, nó gần như không chậm hơn (1,9 lần); khi mảng vượt L1 rồi L2 rồi cả L3, mỗi lần truy cập phải xuống tầng chậm hơn, và độ chậm nhảy 12 → 24 → 206 lần. Bậc thang này chính là hình dạng của phân cấp cache: random access chỉ trả giá khi tập làm việc lớn hơn cache, và trả nhiều hơn khi vượt cache lớn hơn. (Trên máy ảo, ranh giới cache chính xác có thể mờ, nhưng bậc thang chậm dần thì không thể nhầm.)
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: locality (tính cục bộ) thường quan trọng hơn số phép. Hai thuật toán cùng O(n) có thể chênh nhau hàng trăm lần tùy chúng duyệt bộ nhớ tuần tự hay nhảy lung tung. Khi tối ưu vòng lặp nóng, sắp dữ liệu để duyệt liền mạch — dùng mảng thay cho cấu trúc rải rác, duyệt theo thứ tự lưu trữ — thường thắng đậm hơn cắt vài phép tính. Đây là lý do các cấu trúc dựa trên mảng (mảng động, mảng phẳng) thường nhanh hơn cấu trúc dựa con trỏ dù cùng độ phức tạp lý thuyết — một chủ đề ta sẽ đo kỹ ở bài kế về danh sách liên kết so với mảng.
Hệ quả thứ hai: big-O là bước đầu, không phải câu trả lời cuối. Con số mang theo: big-O đếm số phép nhưng mù với vị trí dữ liệu trong bộ nhớ; cùng O(n) và cùng n phép cộng, duyệt tuần tự (0,23ns/phần tử, trúng cache + prefetch) nhanh hơn duyệt ngẫu nhiên (103ns/phần tử, cache-miss xuống RAM) tới 452 lần trên mảng 256MB, và độ chậm của random tăng theo bậc thang 1,9 → 12 → 24 → 206 khi tập làm việc vượt L1/L2/L3 — chứng minh cache là thủ phạm. Một phép load rẻ hay đắt gấp trăm lần tùy nó nằm trong cache hay RAM; muốn code nhanh thật, hãy nghĩ về nơi dữ liệu nằm, không chỉ số phép bạn làm.
Thử ba mươi giây
Trong đầu, so hai cách cộng một ma trận hai chiều lưu theo hàng (row-major, như C): duyệt theo hàng (for i: for j: a[i][j]) đọc bộ nhớ tuần tự — mỗi dòng cache phục vụ nhiều phần tử kề nhau. Duyệt theo cột (for j: for i: a[i][j]) nhảy một-bước-bằng-cả-hàng mỗi lần — với ma trận lớn, gần như mỗi lần là một cache-miss. Cùng số phép, cùng O(n²), nhưng duyệt theo cột có thể chậm vài lần tới cả chục lần trên ma trận lớn. Nếu có trình biên dịch, viết thử cả hai với ma trận 4096×4096 và bấm giờ — bạn sẽ thấy tận mắt rằng thứ tự duyệt, chứ không phải số phép, quyết định tốc độ.
