Phần 5 và phần 11 đo được một con số đáng sợ: đuổi con trỏ ngẫu nhiên ra RAM tốn ~100 ns mỗi bước. Từ đó rất dễ kết luận: bộ nhớ chậm, mỗi lần chạm hụt cache là một cú chờ trăm nanô giây, và N lần miss thì tốn N lần độ trễ. Tôi cũng từng đóng đinh mô hình đó trong đầu.

Nhưng hãy nghĩ về việc gửi thư đặt hàng. Nếu bạn gửi một lá thư, chờ hàng về rồi mới viết lá tiếp theo — vì phải xem món này mới biết đặt món kế — thì mười món mất mười lần thời gian chờ bưu điện. Nhưng nếu bạn biết trước cả mười thứ cần mua, bạn nhét cả mười lá thư vào thùng thư cùng lúc, rồi ngồi chờ chúng lần lượt về. Tổng thời gian chỉ nhỉnh hơn một lần chờ. Bí quyết không nằm ở bưu điện nhanh hơn, mà ở chỗ mười đơn hàng độc lập nhau nên gửi được song song. Con số 100 ns kia có một điều kiện ẩn mà tôi đã bỏ qua: các lần miss ấy phụ thuộc nhau. Điều gì xảy ra nếu chúng độc lập? Tôi đo trong container gcc:13 trên host ARM, và câu trả lời lật ngược trực giác.

Nhiều lần miss độc lập bay cùng lúc

Một lõi CPU hiện đại thực thi ngoài thứ tự (out-of-order): khi gặp một lệnh phải chờ (một load đang đợi dữ liệu từ RAM), nó không đứng im. Nó chạy tiếp các lệnh sau độc lập, và nếu trong đó có thêm những load khác cũng miss cache, nó phát luôn các lần nạp đó — như nhét thêm thư vào thùng. Kết quả: nhiều lần chạm hụt cache cùng bay trong không trung một lúc, chờ RAM song song. Hiện tượng này gọi là song song mức bộ nhớ (MLP — memory-level parallelism).

Hệ quả then chốt: nếu bạn có N lần miss độc lập, tổng thời gian không phải N × độ trễ — mà gần bằng một độ trễ (miễn N còn trong khả năng "chứa" của phần cứng). Nhưng nếu các miss phụ thuộc nhau (mỗi cái cần kết quả cái trước, như đuổi con trỏ), chúng buộc phải nối đuôi — không chồng lên nhau được, và bạn trả đủ N × độ trễ. Câu hỏi đo: phần cứng chứa được bao nhiêu miss độc lập cùng lúc?

Đo: từ 102 ns xuống 3,9 ns

Tôi đuổi con trỏ trên một mảng 256 MB (mỗi bước là một cú miss ra RAM), nhưng chạy K chuỗi độc lập song song: K con trỏ, mỗi vòng cập nhật cả K. Vì K con trỏ ở K vị trí khác nhau, K lần nạp độc lập nhau. Tăng K, đo ns mỗi lần truy cập:

Đuổi con trỏ 256 MB, K chuỗi ĐỘC LẬP song song, host ARM:

   K  | ns/truy cập | tăng tốc vs K=1
   ---|-------------|----------------
    1 |   102,3     | 1,0x   (1 miss/lúc = full latency)
    2 |    52,6     | 1,9x
    4 |    26,8     | 3,8x
    8 |    13,6     | 7,5x
   16 |     7,29    | 14x
   24 |     4,99    | 20x
   32 |     3,91    | 26x    (vẫn đang scale)

Đường cong gần như tuyến tính nghịch: K=1 tốn 102 ns (một miss mỗi lúc, đúng độ trễ RAM), K=2 còn 52,6 ns (1,9x — hai miss chồng nhau), K=8 xuống 13,6 ns (7,5x), K=16 còn 7,29 ns (14x), và K=32 chỉ 3,9 ns — nhanh gấp 26 lần so với một chuỗi. Cùng thao tác "chạm một ô nhớ ngẫu nhiên ở RAM", nhưng làm 32 cái độc lập thì mỗi cái rẻ đi 26 lần, vì lõi cho chúng bay song song.

Chú ý ở K=32 nó vẫn đang scale (26x, chưa bão hòa) — nghĩa là lõi này giữ được ít nhất ~26–32 lần miss outstanding cùng lúc. Đây là độ sâu MLP rất lớn (Apple Silicon nổi tiếng với hàng đợi bộ nhớ khổng lồ). Một lõi không chỉ rộng về tính toán (phần 10) mà còn sâu về số lần chờ bộ nhớ nó chịu được cùng lúc.

Hai niềm tin bị đo cho gãy

Tôi vào đo với mô hình tuần tự trong đầu: "cache miss là một cú chờ; gặp miss thì CPU đứng lại chờ xong mới đi tiếp; nên N lần miss tốn N × độ trễ". Con số bác ngay: lõi không đứng chờ — nó phát tiếp các miss độc lập, và 32 lần miss độc lập hoàn thành trong thời gian chỉ hơn một lần miss chút ít (3,9 ns/cái so với 102 ns khi đơn lẻ). "N miss = N × latency" chỉ đúng khi chúng phụ thuộc nhau; với miss độc lập, chi phí gần như chia đều cho độ song song. Nếu tin mô hình cũ, tôi không giải thích nổi vì sao một vòng quét băm hay gather "toàn miss" lại nhanh hơn hẳn con số N × 100 ns dự đoán.

Nhưng đo cũng chỉnh một niềm tin khác tôi vừa rút ra từ phần 5: "truy cập RAM ngẫu nhiên luôn ~100 ns". Sai — thiếu một chữ. Truy cập ngẫu nhiên phụ thuộc (đuổi con trỏ đơn, mỗi bước cần bước trước) mới là 102 ns. Truy cập ngẫu nhiên độc lập (nhiều luồng, biết trước các địa chỉ) chỉ 3,9 ns nhờ MLP — cùng là "chạm RAM ngẫu nhiên" nhưng chênh 26 lần. Cái quyết định không phải "ngẫu nhiên hay không", mà là "phụ thuộc hay độc lập". Con trỏ chase chậm không vì nó ngẫu nhiên, mà vì nó nối đuôi — bỏ phí toàn bộ khả năng MLP của lõi.

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

Việc đầu tiên: làm các truy cập bộ nhớ ĐỘC LẬP để chúng chồng lên nhau. Nếu phải chạm nhiều vị trí rải rác (tra băm hàng loạt, gather, duyệt nhiều cây), hãy sắp để các lần chạm không phụ thuộc nhau — xử lý một lô khóa cùng lúc thay vì lần lượt, để lõi phát nhiều miss song song. Đây là ý tưởng sau batching và software pipelining trong cấu trúc dữ liệu: cùng số lần miss, nhưng độc lập thì nhanh hơn hàng chục lần.

Việc thứ hai: tránh chuỗi phụ thuộc dài của các truy cập bộ nhớ. Đuổi con trỏ qua danh sách liên kết hay cây là phản đề của MLP — mỗi bước phải chờ bước trước, không miss nào chồng được, trả đủ độ trễ. Nếu có thể, thay bằng cấu trúc cho phép biết trước nhiều địa chỉ (mảng chỉ số, cây phẳng hóa) để phát nhiều truy cập độc lập. Đây là một lý do sâu nữa vì sao mảng thắng danh sách liên kết — không chỉ prefetch, mà cả MLP.

Điều làm tôi thấy MLP thú vị là nó ngầm chống lưng cho những kỹ thuật ở tầng cao mà ta vẫn dùng vì lý do khác. Trong Java hay Go, gom nhiều thao tác thành batch (một lượt mget Redis thay vì N lần get, một truy vấn WHERE id IN (...) thay vì N truy vấn) thường được biện minh bằng "giảm round-trip mạng" — mà đúng là vậy — nhưng ở tầng CPU, batching cũng chính là biến N truy cập phụ thuộc thành N truy cập độc lập để MLP nuốt song song. Ngược lại, một ORM lười nạp quan hệ theo kiểu N+1 (nạp cha, rồi với mỗi cha lại nạp con) là bản sao hoàn hảo của đuổi-con-trỏ: mỗi truy vấn chờ kết quả truy vấn trước, không gì chồng được. Cùng một nguyên lý ở mọi tầng: cái đắt không phải độ trễ một thao tác, mà là chuỗi phụ thuộc buộc chúng nối đuôi. Bẻ chuỗi ra, cho độc lập, là mở khóa song song.

Muốn tự thấy thì cấp một mảng lớn hơn cache (vài trăm MB), tạo một chu trình đuổi con trỏ ngẫu nhiên, rồi đo hai cách. Một: đuổi một con trỏ p = a[p] vài chục triệu bước — bạn được ~100 ns mỗi bước, độ trễ RAM đầy đủ, vì mỗi bước phụ thuộc bước trước. Hai: giữ K con trỏ độc lập (p0=a[p0]; p1=a[p1]; ...) và cập nhật cả K mỗi vòng, chia thời gian cho tổng số lần chạm. Tăng K = 2, 4, 8, 16, 32: ns mỗi lần chạm giảm gần tỉ lệ nghịch với K — tới K=16, 32 vẫn còn giảm — vì lõi cho hàng chục miss bay song song. Điểm nó ngừng giảm cho bạn độ sâu MLP của máy (số miss tối đa nó giữ cùng lúc). Ba mươi giây đó cho thấy điều mà "mỗi cache miss là một cú chờ trăm nanô giây" giấu đi: lõi không đứng chờ từng miss — nó phóng cả một bầy miss độc lập cùng lúc, và bí quyết tăng tốc code nặng bộ nhớ là cho nó nhiều việc độc lập để phóng.