Prefetch bằng tay — sách bảo cứu truy cập ngẫu nhiên, máy tôi lại nói ngược sạch

Hình dung bạn gọi món trước khi tới nhà hàng, để vừa ngồi xuống là có đồ ăn ngay, không phải chờ bếp. Đó là ý tưởng của prefetch: báo trước "sắp cần cái này" để dữ liệu kịp về trước khi bạn dùng. Mẹo này tuyệt — nếu bạn biết trước mình sẽ gọi gì. Nhưng có những tình huống bạn không thể gọi trước: khi món tiếp theo chỉ được quyết định sau khi ăn xong món này. Với những chuỗi phụ thuộc kiểu đó, "gọi trước" là vô nghĩa về mặt cấu trúc. Prefetch bộ nhớ vấp đúng cái ranh giới ấy, và tôi đã đo ra một câu chuyện ngược hẳn sách vở.

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 đo trong container gcc:13 (ARM), tin rằng "thêm prefetch là nhanh hơn" — và thu về kết quả ngược hẳn sách vở.

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 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. Đúng cái cảnh không thể gọi món trước khi biết món này ăn xong sẽ dẫn tới món gì. 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à chỗ tôi nhầm, và là loại nhầm đắ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ề đến code hằng ngày

Điều đầ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. 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.

Điều 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à kỹ thuật đòi hiểu sâu và đo kỹ.

Và đây là chỗ đáng an ủi: cái ý "báo trước để giấu độ trễ" thật ra được các tầng cao tự động hóa để bạn không phải mó tay vào cái dao mổ khó chịu này. JVM và phần cứng hiện đại đã có hardware prefetcher lo phần tuần tự; muốn giấu độ trễ ngẫu nhiên, cách bền hơn là đủ luồng song song để khi luồng này chờ RAM thì luồng khác chạy (chính là điều JVM/CPU siêu phân luồng khai thác). Ở tầng dữ liệu, ý này thành đọc trước (read-ahead) của hệ điều hành và CSDL: Postgres có effective_io_concurrency và prefetch cho bitmap heap scan, hệ điều hành tự đọc trước khi thấy đọc file tuần tự — cùng một ý "nạp trước cái sắp cần", nhưng ở tầng I/O nơi độ trễ đĩa lớn hơn nhiều nên lợi rõ hơn nhiều. Mẫu số chung: giấu độ trễ bằng cách nạp trước là một ý tưởng đúng ở mọi tầng, nhưng nó chỉ hiệu quả khi bạn đoán được cái sắp cần — và với chuỗi phụ thuộc (con trỏ đuổi, truy vấn phải xong bước trước mới biết bước sau), không tầng nào giấu được, nên cách chữa thật là đổi cấu trúc dữ liệu, không phải thêm prefetch.

Muốn tự thấy thì cấp một mảng lớn hơn cache (vài trăm MB), duyệt 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".