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 tôi gộp tất cả vào một hình để trả lời câu hỏi nền tảng nhất: "chạm bộ nhớ tốn bao lâu?" Câu trả lời hóa ra không phải một con số, mà ba — tùy bạn truy cập thế nào.

Nghĩ tới một thư viện lớn. Có ba cách lấy sách, và tốc độ chênh nhau khủng khiếp. Cách một: lấy nguyên một dãy sách xếp liền kề trên kệ — thủ thư đẩy cả xe một lượt, nhanh như chớp. Cách hai: bạn đưa cho thủ thư cả danh sách mười cuốn nằm rải rác, họ chia nhau đi lấy song song, gom lại một lần. Cách ba: mỗi cuốn sách ghi mã số của cuốn tiếp theo, bạn phải đọc xong cuốn này mới biết đi tìm cuốn nào — không thể lấy trước, phải đi từng chuyến một, chậm nhất. Bộ nhớ máy tính vận hành đúng ba kiểu đó. Trên cùng một mảng, cùng số lần chạm, thời gian 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, và lẫn lộn chúng là gốc của mọi hiểu nhầm. 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 (cái xe đẩy nguyên dãy sách). Độ 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 (đi từng chuyến một). 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 có một vùng trung gian: 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, 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 ông thủ thư cầm cả danh sách đi lấy song song.

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: chậm nhất, đi từng chuyến một.

Chênh lệch tuần tự so với 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, có khi hơn, bao nhiêu dữ liệu.

Hai niềm tin đối nghịch, cùng sai

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". Con số bác ngay: 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 tin "một tốc độ" thì không tài nào giải thích nổi 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 — mà 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 nếu vì thế mà tin điều ngược lại — "truy cập ngẫu nhiên luôn ~100 ns" — thì cũng sai, vì thiếu mất 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 mang tiếng "truy cập ngẫu nhiên".

Về đến code hằng ngày

Việc đầ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.

Việc 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ễ, kéo 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.

Ba chế độ này giải thích được rất nhiều thứ khó hiểu ở tầng cao. Vì sao duyệt một LinkedList trong Java chậm hơn ArrayList nhiều hơn cả những gì lý thuyết Big-O gợi ý? Vì LinkedList là đuổi con trỏ thuần túy — mỗi node một cú nhảy latency-bound — còn ArrayList duyệt tuần tự, bandwidth-bound. Vì sao dò một chuỗi băm dài (chaining) đau hơn tưởng? Cùng lý do. Ở phía database thì đây chính là câu chuyện của prefetch/read-ahead: một sequential scan trên bảng lớn đọc đĩa (hay page cache) theo kiểu băng thông và nhanh đến bất ngờ, trong khi một index scan nhảy lung tung qua các trang lá lại latency-bound — đó là một lý do bộ tối ưu đôi khi cố tình chọn quét tuần tự cả bảng thay vì đi index, khi phải chạm nhiều hàng. Và các engine hiện đại còn cố "độc lập hóa" bằng cách prefetch nhiều trang cùng lúc — đúng mẹo MLP ở trên. Câu hỏi cần hỏi luôn là: code của tôi bandwidth-bound hay latency-bound? Rồi đo bằng đúng đơn vị — GB/s cho cái trước, ns mỗi truy cập cho cái sau.

Muốn tự thấy thì 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] — được ~0,2–0,3 ns mỗi phần tử (băng thông, 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 sẵn — chậm hơn nhiều (vài ns) nhưng vẫn nhanh nhờ 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 thấy vài trăm lần, trên cùng mảng đó. Ba mươi giây ấy cho 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.