Suốt sê-ri, một con số cứ hiện đi hiện lại: chạm bộ nhớ RAM tốn cả trăm nanô giây (phần 5, phần 11 đo ~100 ns cho một lần nạp phụ thuộc). Vậy mà một vòng lặp duyệt mảng khổng lồ vẫn chạy vèo vèo, mỗi phần tử chưa tới một nanô giây. Nghịch lý ấy có một thủ phạm tốt bụng: bộ nạp trước (hardware prefetcher). Đó là mạch trong CPU đoán địa chỉ bạn sắp cần rồi kéo dòng cache đó về trước, để khi bạn chạm tới thì dữ liệu đã nằm sẵn — giấu độ trễ RAM. Tôi đo nó làm việc trong container gcc:13 trên host ARM, và mức độ giỏi của nó lớn đến bất ngờ — cùng với đúng chỗ nó bó tay.
Đoán mẫu đều đặn, nạp trước dòng kế
Bộ nạp trước quan sát chuỗi địa chỉ bạn đang chạm. Nếu thấy một mẫu đều đặn — tuần tự tiến, tuần tự lùi, hay bước đều (constant stride) — nó suy ra dòng cache kế tiếp và phát lệnh nạp dòng đó từ trước, trong lúc CPU còn đang xử lý dòng hiện tại. Khi vòng lặp tới nơi, dữ liệu đã ở cache: độ trễ RAM bị che hoàn toàn.
Nhưng nó chỉ đoán được mẫu. Với truy cập ngẫu nhiên — đuổi con trỏ qua node rải rác, hay nhảy tới chỉ số không đoán được — không có mẫu để suy, nên mỗi lần chạm phải chờ dòng về từ RAM, trả trọn độ trễ. Câu hỏi đo: bộ nạp trước giấu được bao nhiêu, và với những mẫu nào?
Đo: tuần tự 0,24 ns, ngẫu nhiên 101 ns
Tôi duyệt một mảng int64 256 MB (vượt xa cache) theo ba kiểu — tuần tự tiến, tuần tự lùi, và ngẫu nhiên (đuổi con trỏ):
Mảng 256 MB (vượt cache), host ARM, g++ -O2 -fno-tree-vectorize:
tuần tự (stride 8B) : 0,24 ns/phần tử
lùi (backward, stride 8B) : 0,24 ns/phần tử
ngẫu nhiên (đuổi con trỏ) : 101,4 ns/truy cập <- ~420x
Khác biệt choáng váng: cùng một mảng, cùng số byte chạm, nhưng tuần tự chỉ 0,24 ns mỗi phần tử còn ngẫu nhiên tới 101,4 ns — chênh ~420 lần. Toàn bộ khác biệt là bộ nạp trước: với tuần tự, nó kéo dòng kế về trước nên CPU không bao giờ phải chờ; với ngẫu nhiên, nó không đoán nổi, và mỗi lần chạm là một cú đi RAM đầy đủ (đúng bằng độ trễ đo ở phần 5/11). Và điều đẹp: duyệt lùi cũng 0,24 ns — bộ nạp trước bắt được cả chiều giảm dần, không chỉ tuần tự tiến.
Đo: quét bước đều, tìm chỗ prefetcher đuối
Bộ nạp trước theo được bước đều tới đâu? Tôi đọc mảng với bước (stride) tăng dần:
Bước đều, ns/truy cập (host ARM, cùng hàm nên chi phí vòng như nhau):
stride 8 B : 0,69 stride 1024 B : 3,28
stride 16 B : 0,72 stride 2048 B : 3,28
stride 32 B : 0,73 stride 4096 B : 3,79
stride 64 B : 0,92 stride 8192 B : 4,62
stride 128 B : 2,76 stride 16 KB : 6,64
stride 256 B : 3,02 stride 64 KB : 6,39
Đọc đường cong: bước nhỏ hơn 128 byte rất rẻ (0,7–0,9 ns) vì nhiều lần chạm rơi vào cùng một dòng cache 128 byte. Ở 128 byte — mỗi lần chạm một dòng riêng — thời gian nhảy lên 2,76 ns. Nhưng chú ý: 2,76 ns vẫn thấp hơn rất nhiều con số 101 ns của ngẫu nhiên. Nghĩa là dù mỗi lần chạm là một dòng mới, bộ nạp trước vẫn theo kịp vì bước là đều: nó đoán được dòng kế và nạp trước. Từ 128 byte tới ~2 KB, thời gian giữ quanh 3,2 ns — bước đều vẫn được nạp trước tốt.
Chỉ khi bước rất lớn (16–64 KB) thời gian mới bò lên ~6,6 ns — bộ nạp trước bắt đầu đuối: bước vượt trang nhớ nên đụng cả chi phí TLB, và độ tin cậy của nó giảm. Nhưng ngay cả ở bước 64 KB, 6,6 ns vẫn nhanh hơn ngẫu nhiên (101 ns) khoảng 15 lần. Kết luận thẳng: cái duy nhất thực sự đánh bại bộ nạp trước là tính ngẫu nhiên, không phải bước lớn.
Một lần tôi đo hớ: "RAM luôn chậm trăm ns" và "prefetcher lo hết / chỉ bắt tuần tự"
Tôi vào đo với con số ám ảnh từ các phần trước: "chạm RAM là ~100 ns, chấm hết". Đo phá tan: duyệt tuần tự một mảng 256 MB chỉ tốn 0,24 ns mỗi phần tử — bộ nạp trước giấu ~420 lần độ trễ. Con số "100 ns" chỉ đúng cho truy cập ngẫu nhiên/phụ thuộc, nơi không có mẫu để nạp trước. Với dữ liệu duyệt tuần tự (phần lớn vòng lặp thực tế), RAM không hề chậm — nó gần như miễn phí. Nếu tôi tin "RAM luôn chậm" tôi sẽ sợ hãi những vòng duyệt mảng lớn một cách vô cớ.
Nhưng đo cũng chỉnh hai niềm tin ngược nhau về bộ nạp trước. Một phía tưởng "nó chỉ bắt được tuần tự bước 1" — sai: nó bắt cả duyệt lùi (0,24 ns) và bước đều rất lớn tới 64 KB (6,6 ns, vẫn hơn ngẫu nhiên 15 lần). Phía kia tưởng "nó lo hết mọi mẫu, cứ viết sao cũng được" — cũng sai: truy cập ngẫu nhiên nó bó tay hoàn toàn (101 ns), và bước quá lớn thì hiệu quả giảm dần (3 → 6,6 ns). Bộ nạp trước là một cỗ máy đoán mẫu đều; cho nó mẫu thì nó giấu độ trễ, cho nó hỗn loạn thì nó vô dụng.
Bài học đo lường: bộ NẠP TRƯỚC (prefetcher) giấu độ trễ RAM cho truy cập ĐỀU ĐẶN — đo: tuần tự (và LÙI) 0,24 ns/phần tử vs ngẫu nhiên 101 ns = ~420x, CÙNG mảng. Bước đều được nạp trước rộng rãi: 128B->2KB ~3 ns, tới 64KB vẫn 6,6 ns (>ngẫu nhiên 15x), chỉ degrade khi bước quá lớn/vượt trang. Chỉ NGẪU NHIÊN mới trả full latency. 'RAM luôn chậm ~trăm ns' SAI; 'prefetcher lo hết' và 'chỉ bắt tuần tự bước 1' đều SAI. Nếu tin "RAM luôn chậm" tôi sợ vòng duyệt mảng; nếu tin "prefetcher lo hết" tôi để mẫu ngẫu nhiên giết hiệu năng.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: thiết kế truy cập cho ĐỀU ĐẶN để bộ nạp trước làm việc. Duyệt mảng tuần tự (tiến hay lùi), dùng chỉ số thay con trỏ rải rác, chọn bố cục liền mạch (mảng thắng danh sách liên kết, SoA thắng AoS khi quét một trường). Một thuật toán "cùng số phép đọc" nhưng theo mẫu đều có thể nhanh hơn bản ngẫu nhiên hàng trăm lần nhờ bộ nạp trước — dù Big-O y hệt.
Hệ quả thứ hai: khi buộc phải truy cập không đều, cân nhắc nạp trước bằng phần mềm. Nếu bạn biết trước địa chỉ sắp cần vài bước nữa (ví dụ duyệt một danh sách chỉ số đã có sẵn), __builtin_prefetch có thể ra lệnh nạp sớm và giấu bớt độ trễ mà bộ nạp trước phần cứng không tự đoán được. Nhưng nó chỉ giúp khi bạn đoán đúng và đủ sớm; đoán sai chỉ phí băng thông.
Hệ quả thứ ba là tinh thần đo lường: "chạm RAM" không có một giá cố định — tùy mẫu truy cập, nó chênh nhau trăm lần. Con số mang theo: tuần tự/lùi 0,24 ns (prefetch giấu ~420x); bước đều nạp trước tốt tới ~2KB (~3 ns), degrade nhẹ tới 64KB (6,6 ns); ngẫu nhiên 101 ns (prefetcher bó tay). Viết truy cập đều đặn; dùng __builtin_prefetch khi buộc phải không đều. Cùng một mảng, cùng số byte, mà thứ tự bạn chạm chúng quyết định nhanh hay chậm 420 lần — điều Big-O không bao giờ nói.
Thử ba mươi giây
Cấp một mảng lớn hơn cache nhiều (vài trăm MB), rồi cộng dồn toàn bộ theo thứ tự tuần tự và bấm giờ ns mỗi phần tử — bạn sẽ thấy một con số nhỏ xíu (dưới một nanô giây), dù dữ liệu nằm ở RAM, vì bộ nạp trước kéo dòng kế về trước. Làm lại theo thứ tự lùi: gần như y hệt — nó bắt cả hai chiều. Giờ dựng một chu trình đuổi con trỏ ngẫu nhiên trên cùng mảng và đo: thời gian nhảy vọt lên cả trăm nanô giây mỗi bước, vì không còn mẫu để đoán. Cuối cùng, quét bước đều tăng dần (64 byte, 256, 1 KB, 16 KB, 64 KB): bạn sẽ thấy thời gian tăng dần nhưng vẫn thấp hơn ngẫu nhiên nhiều lần — bộ nạp trước theo kịp bước đều đến tận bước rất lớn. Ba mươi giây đó cho bạn thấy điều mà "chạm RAM luôn tốn trăm nanô giây" giấu đi: phần cứng có một cỗ máy đoán mẫu chạy ngầm, và chỉ cần bạn truy cập đều đặn, nó giấu gần trọn độ trễ bộ nhớ cho bạn — còn nếu bạn chạm hỗn loạn, bạn trả đủ giá.
