Một lần trượt cache — CPU cần dữ liệu chưa có trong cache, phải xuống RAM — tốn khoảng 100 nano giây, hàng trăm chu kỳ CPU đứng chờ. __builtin_prefetch(addr) là cách báo trước cho phần cứng: "sắp cần địa chỉ này, nạp nó vào cache đi", để lúc thật sự dùng thì dữ liệu đã ở đó, độ trễ được giấu. Nghe như một nút tăng tốc thần kỳ cho mã nghẽn bộ nhớ. Tôi vào đo, tin rằng "thêm prefetch là nhanh hơn" — và thu về một kết quả ngược hẳn sách vở, dạy đúng bài học đo lường của sê-ri.
Prefetch: báo trước để giấu độ trễ
__builtin_prefetch(addr, rw, locality) sinh một lệnh prfm trên ARM — nó không đọc giá trị, chỉ yêu cầu hệ thống bộ nhớ kéo dòng cache chứa addr về. Ý tưởng: nếu bạn biết vài vòng lặp nữa sẽ cần một địa chỉ, prefetch nó ngay bây giờ, và trong lúc phần cứng nạp (song song với công việc khác), CPU không phải đứng chờ khi tới lúc dùng.
Lý thuyết nói prefetch chỉ đáng ở mẫu truy cập khó đoán: truy cập ngẫu nhiên, con trỏ đuổi (pointer-chase). Với truy cập tuần tự, bộ nạp trước phần cứng (hardware prefetcher) đã tự nhận ra bước đều và kéo sẵn dòng kế, nên prefetch thủ công thừa. Tôi đo cả ba mẫu trong container gcc:13 (ARM AArch64) trên mảng 128MB (lớn hơn cache nhiều), và kết quả buộc tôi viết lại toàn bộ trực giác.
Đo: prefetch làm ngược điều sách nói
Tuần tự. Cộng tuần tự một mảng 128MB, có và không prefetch dòng phía trước:
không prefetch : 0,48 ns/phần tử
prefetch nhìn 16: 0,32 ns/phần tử -> nhanh ~1,5 lần
Prefetch thủ công giúp truy cập tuần tự — đúng cái mà lý thuyết bảo là vô ích! Lời giải thích trung thực: trên chiếc máy ảo hóa này (ARM chạy qua ảo hóa trên Apple Silicon), bộ nạp trước phần cứng có vẻ yếu hơn máy bare-metal, nên báo tay lại lấp được khoảng trống. Đây là dấu hiệu đầu tiên rằng prefetch phụ thuộc rất mạnh vào phần cứng cụ thể.
Gather ngẫu nhiên. Truy cập mảng theo một hoán vị ngẫu nhiên (cache-miss nặng, phần cứng không đoán được), prefetch phần tử sẽ cần vài bước sau:
không prefetch : 3,10 - 3,48 ns/phần tử
prefetch (dist 4..256): 3,22 - 3,35 ns/phần tử -> gần như vô ích / nhiễu
Nghịch lý thứ hai: prefetch gần như không giúp mẫu ngẫu nhiên — đúng cái lý thuyết bảo nó nên tỏa sáng. Vì vòng gather này đã bão hòa băng thông bộ nhớ và các phép nạp đã được phát ra nhanh nhất có thể; prefetch chỉ thêm một phép nạp nữa, cạnh tranh băng thông, nên đôi khi còn chậm hơn.
Con trỏ đuổi. Duyệt một danh sách liên kết trải khắp 128MB — mỗi bước cur = a[cur].next là một trượt cache, khoảng 105 ns/bước. Đây là ca kinh điển "prefetch cứu được":
không prefetch : 105,7 ns/bước
prefetch nhìn 2: 105,5 ns/bước -> KHÔNG giúp
Không nhúc nhích. Và đây là bài học sâu nhất: để prefetch node sau node kế, tôi phải p = a[p].next — tức phải giải tham chiếu chính chuỗi con trỏ đang chậm. Prefetch không thể chạy trước chuỗi phụ thuộc, vì địa chỉ nó muốn nạp nằm sau đúng cái trượt cache mà nó định giấu. Software prefetch bó tay với pointer-chase thuần vì lý do cấu trúc, không phải vì phần cứng. (Đây cũng là vì sao cấu trúc dữ liệu dạng con trỏ đuổi — danh sách liên kết, cây trải rác — chậm kinh niên trên phần cứng hiện đại: mỗi bước là một trượt cache không giấu được, khác hẳn một mảng nơi truy cập đoán được và căn lề cùng bố cục tuần tự cho phần cứng chạy trước.)
Đây là đo hớ của tôi, và nó là loại đo hớ đắt nhất: tôi tin "prefetch tăng tốc, nhất là cho ngẫu nhiên/con trỏ đuổi", và đo ra ngược lại từng điểm trên máy này — giúp tuần tự, vô ích cho ngẫu nhiên, bó tay với con trỏ đuổi.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: prefetch phụ thuộc mạnh vào phần cứng cụ thể — kết quả trên máy này có thể ngược trên máy khác. Bộ nạp trước phần cứng, độ trễ RAM, băng thông, kích thước cache đều khác nhau giữa các chip; và như tôi vừa thấy, một môi trường ảo hóa còn đổi cả hành vi. Điều này nghĩa là bạn không thể suy từ lý thuyết hay từ một bài blog (kể cả bài này) rằng prefetch có giúp code của bạn không — phải đo trên đúng máy sẽ chạy.
Hệ quả thứ hai: prefetch là dao mổ có nhiều tham số dễ sai. Khoảng nhìn trước (prefetch distance) phải vừa đúng: quá gần thì phần cứng chưa kịp nạp xong khi tới lúc dùng; quá xa thì dòng đã prefetch bị đẩy khỏi cache trước khi dùng. Sai khoảng cách không chỉ vô ích mà còn hại — ô nhiễm cache (đẩy dữ liệu hữu ích ra), tốn băng thông. Và với pointer-chase, nó bất lực về nguyên tắc. Đây không phải nút "cho nhanh", mà là một kỹ thuật đòi hiểu sâu và đo kỹ.
Hệ quả thứ ba là bài học đo lường bao trùm sê-ri: khi lý thuyết và đo lường mâu thuẫn, tin cái đồng hồ. Sách nói prefetch giúp ngẫu nhiên, hại-nếu-thừa ở tuần tự; máy tôi nói ngược. Không phải sách sai, mà là "phần cứng" trong sách khác phần cứng của tôi. Cách tối ưu bộ nhớ đáng tin hơn prefetch thủ công là làm dữ liệu thân thiện cache từ đầu — bố cục tuần tự, cấu trúc gọn — để không cần giấu độ trễ vì không có độ trễ để giấu. Con số mang theo: __builtin_prefetch sinh lệnh prfm nạp trước dòng cache để giấu độ trễ RAM, NHƯNG kết quả phụ thuộc mạnh phần cứng + mẫu truy cập: trên máy ARM ảo hóa này nó GIÚP tuần tự ~1,5 lần (0,48 xuống 0,32 ns — trái lý thuyết, do HW prefetcher yếu), gần như VÔ ÍCH cho gather ngẫu nhiên (thêm traffic), và KHÔNG cứu được con trỏ đuổi (105,7 so 105,5 ns) vì phải deref mới biết địa chỉ kế. Đừng rắc prefetch theo lý thuyết; đo trên đúng máy đích, và ưu tiên bố cục cache tốt hơn là vá bằng prefetch.
Thử ba mươi giây
Cấp một mảng lớn hơn cache (vài trăm MB), duyệt nó theo một hoán vị ngẫu nhiên (cache-miss nặng), đo thời gian mỗi phần tử. Rồi thêm __builtin_prefetch(&a[idx[i+D]]) với D là khoảng nhìn trước (thử D = 8, 32, 128), đo lại. Trên một số máy bạn sẽ thấy một giá trị D cho tốc độ tốt hơn rõ; trên máy khác (như của tôi) gần như không đổi. Rồi thử cùng prefetch trên một vòng tuần tự — kết quả có thể khiến bạn ngạc nhiên. Ba mươi giây đó cho bạn thấy prefetch không phải công tắc, mà là một tham số phải dò trên chính phần cứng của bạn — và đôi khi câu trả lời là "đừng dùng".
