Sê-ri này đã đo cache (phần 5), bộ nạp trước (phần 14), song song mức bộ nhớ (phần 15), băng thông (phần 20). Phần này gộp tất cả vào một hình để trả lời câu hỏi nền tảng: "chạm bộ nhớ tốn bao lâu?" Câu trả lời không phải một con số, mà ba — tùy bạn truy cập thế nào. Trên cùng một mảng, cùng số lần chạm, thời gian có thể chênh nhau hàng trăm lần. Tôi đo cả ba chế độ trong container gcc:13 trên host ARM.
Hai cái trần: băng thông và độ trễ
Bộ nhớ có hai giới hạn khác hẳn nhau. Băng thông (bandwidth) là bao nhiêu byte mỗi giây — cái trần khi bạn kéo nhiều dữ liệu liên tục. Độ trễ (latency) là bao lâu cho một lần chạm tính từ lúc hỏi tới lúc có dữ liệu — cái trần khi mỗi lần chạm phải đợi lần trước. Truy cập tuần tự đụng trần băng thông; truy cập ngẫu nhiên phụ thuộc đụng trần độ trễ. Giữa hai cực ấy có một vùng trung gian, khi truy cập ngẫu nhiên nhưng độc lập.
Tôi đo trên cùng một mảng 256 MB (32 triệu số int64), cùng số lần truy cập, ba kiểu: (A) tuần tự — đọc a[0], a[1], ...; (B) ngẫu nhiên độc lập — đọc a[idx[i]] với các chỉ số idx biết trước, không phụ thuộc nhau; (C) ngẫu nhiên phụ thuộc — đuổi con trỏ, mỗi bước lấy địa chỉ từ giá trị vừa đọc.
Đo: cùng mảng, chênh 424 lần
Cùng mảng 256 MB int64, cùng số truy cập, host ARM, g++ -O2:
kiểu truy cập | ns/truy cập | GB/s | trần
---------------------------------|-------------|--------|------------------
TUẦN TỰ (a[0],a[1],...) | 0,240 | 33,3 | BĂNG THÔNG
NGẪU NHIÊN, ĐỘC LẬP (a[idx[i]]) | 3,303 | 2,42 | MLP (song song miss)
NGẪU NHIÊN, PHỤ THUỘC (đuổi c.trỏ)| 101,746 | 0,08 | ĐỘ TRỄ RAM
Đọc từ nhanh tới chậm, trên cùng một mảng:
Tuần tự — 0,240 ns mỗi phần tử (33 GB/s). Bộ nạp trước đoán mẫu và kéo dòng kế về trước, nên CPU gần như không bao giờ đợi. Đây là chế độ bandwidth-bound: đo bằng GB/s, và tốc độ do băng thông quyết định.
Ngẫu nhiên nhưng độc lập — 3,303 ns mỗi truy cập. Không đoán được mẫu nên bộ nạp trước bó tay, nhưng vì các truy cập không phụ thuộc nhau, lõi out-of-order phóng nhiều lần chạm hụt bay song song (MLP) — nhanh hơn đuổi con trỏ 31 lần. Đây là vùng trung gian.
Ngẫu nhiên và phụ thuộc (đuổi con trỏ) — 101,7 ns mỗi truy cập. Mỗi bước cần địa chỉ từ bước trước nên không chồng miss được, trả trọn độ trễ RAM. Đây là chế độ latency-bound: đo bằng ns mỗi truy cập, chậm nhất.
Chênh lệch tuần tự ↔ ngẫu nhiên phụ thuộc là ~424 lần — cùng dữ liệu, cùng số lần chạm, khác nhau chỉ ở cách truy cập. Không phép đo nào trong sê-ri phơi bày rõ hơn: cách bạn đi qua dữ liệu quan trọng ngang, hay hơn, bao nhiêu dữ liệu.
Một lần tôi đo hớ: "bộ nhớ có một tốc độ" và "random luôn ~100 ns"
Tôi vào đo với mô hình đơn giản nhất: "chạm bộ nhớ tốn một lượng cố định". Đo phá tan: cùng mảng, tuần tự 0,24 ns còn ngẫu nhiên phụ thuộc 101,7 ns — 424 lần. Bộ nhớ không có "một tốc độ"; nó có hai cái trần (băng thông và độ trễ) và bạn đụng cái nào là do cách truy cập. Nếu tôi tin "một tốc độ", tôi không thể giải thích vì sao hai vòng lặp "cùng số phép đọc, cùng lượng dữ liệu" chênh nhau hàng trăm lần — câu trả lời luôn là một bên tuần tự (băng thông), một bên đuổi con trỏ (độ trễ).
Nhưng đo cũng chỉnh một niềm tin ngược mà chính sê-ri này dễ gieo: "truy cập ngẫu nhiên luôn ~100 ns". Sai — thiếu chữ phụ thuộc. Ngẫu nhiên độc lập chỉ 3,3 ns nhờ MLP, nhanh hơn ngẫu nhiên phụ thuộc 31 lần. Con số 100 ns chỉ đúng cho đuổi con trỏ (mỗi bước chờ bước trước). "Random" không phải một tốc độ; điều quyết định là các truy cập phụ thuộc nhau hay độc lập. Một bảng băm tra hàng loạt (độc lập) nhanh hơn nhiều một danh sách liên kết duyệt tuần tự con trỏ (phụ thuộc), dù cả hai đều "truy cập ngẫu nhiên".
Bài học đo lường: "truy cập bộ nhớ" có BA chế độ, chọn bởi CÁCH truy cập, chênh ~424x trên CÙNG mảng: TUẦN TỰ 0,24 ns/phần tử (33 GB/s, bandwidth-bound, prefetch giấu); NGẪU NHIÊN ĐỘC LẬP 3,3 ns (MLP che, out-of-order); NGẪU NHIÊN PHỤ THUỘC (đuổi con trỏ) 101,7 ns (latency-bound, full độ trễ RAM). Tuần tự đo bằng GB/s, phụ thuộc đo bằng ns/truy cập. 'Bộ nhớ một tốc độ' và 'random luôn ~100 ns' đều SAI. Nếu tin "một tốc độ" tôi bỏ qua khác biệt 400x; nếu tin "random luôn chậm" tôi bỏ lỡ chuyện làm truy cập độc lập giúp 31x.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: ưu tiên truy cập tuần tự — đó là con đường nhanh nhất. Bố cục dữ liệu liền mạch (mảng thay danh sách liên kết, SoA khi quét một trường, duyệt theo thứ tự bộ nhớ) để bộ nạp trước giấu độ trễ và bạn chạm trần băng thông thay vì trần độ trễ. Đây là gốc rễ của rất nhiều tối ưu bố cục trong sê-ri.
Hệ quả thứ hai: khi buộc phải ngẫu nhiên, làm cho các truy cập độc lập. Tra băm hàng loạt, gather, duyệt nhiều cây — sắp để các lần chạm không phụ thuộc nhau (xử lý một lô cùng lúc), để MLP che bớt độ trễ, chuyển từ 100 ns/truy cập xuống vài ns. Tránh chuỗi đuổi con trỏ dài trên dữ liệu lớn — đó là kịch bản chậm nhất, trả trọn độ trễ mỗi bước.
Hệ quả thứ ba là tinh thần đo lường: hỏi đúng câu — code của tôi bandwidth-bound hay latency-bound? — rồi đo bằng đúng đơn vị. Con số mang theo: tuần tự (bandwidth) ~0,24 ns/phần tử = chục GB/s; ngẫu nhiên độc lập (MLP) vài ns; ngẫu nhiên phụ thuộc (latency) ~100 ns/truy cập; chênh tới ~424x trên cùng mảng. Tuần tự hóa; nếu random thì độc lập hóa. Cùng dữ liệu, cùng số lần chạm, mà cách truy cập đặt bạn vào một trong ba thế giới tốc độ khác nhau hàng trăm lần — đo mới thấy cả ba.
Thử ba mươi giây
Cấp một mảng lớn hơn cache nhiều (vài trăm MB) và đo ns mỗi truy cập ba cách. Một: cộng dồn tuần tự s += a[i] — bạn được ~0,2–0,3 ns mỗi phần tử (băng thông, vì prefetch nạp trước). Hai: đọc theo một mảng chỉ số ngẫu nhiên s += a[idx[i]] với idx xáo trộn sẵn — chậm hơn nhiều (vài ns), nhưng vẫn nhanh vì các truy cập độc lập (MLP). Ba: đuổi con trỏ qua một chu trình ngẫu nhiên p = a[p] — chậm khủng khiếp (cả trăm ns mỗi bước), vì mỗi bước phải đợi bước trước. Chia con số nhanh nhất cho chậm nhất: bạn sẽ thấy khoảng vài trăm lần, trên cùng mảng đó. Ba mươi giây ấy cho bạn thấy điều mà "chạm bộ nhớ tốn một lượng cố định" giấu đi: có hai cái trần — băng thông và độ trễ — và cách bạn đi qua dữ liệu, chứ không phải bao nhiêu dữ liệu, quyết định bạn đụng cái nào.
