Hình dung một trợ lý đứng cạnh bạn khi đọc sách. Nếu bạn lật trang theo thứ tự, cô ấy đoán được và lật sẵn trang kế trước khi bạn đọc xong — sách luôn mở đúng chỗ, bạn không phải chờ. Nhưng nếu bạn nhảy tới những trang ngẫu nhiên, chẳng theo quy luật nào, cô ấy chịu: mỗi lần bạn phải tự dò tìm, mất thời gian. Cái trợ lý ấy chính là prefetcher trong máy tính — cả phần cứng CPU lẫn nhân hệ điều hành đều có một cái — và nó thưởng cho mẫu truy cập đoán được, trừng phạt mẫu ngẫu nhiên.

Phần trước ta thấy đọc tuần tự nhanh hơn ngẫu nhiên, và một lý do là readahead — nhân đọc trước. Bài này đào vào chính cơ chế "đoán trước" đó, và chỉ ra nó thực ra tồn tại ở hai tầng khác nhau. Cả hai cùng một ý tưởng — nạp dữ liệu trước khi bạn cần, nếu đoán được là bạn sẽ cần — nhưng ở hai chỗ khác nhau, và cả hai đều bị cùng một thứ đánh bại: truy cập không đoán được. Tôi đo tầng dễ cô lập nhất (prefetch phần cứng của CPU, thuần bộ nhớ) trong container gcc:13, và con số chênh nhau tới 423 lần.

Hai tầng đoán trước

Tầng 1 — kernel file readahead (đã gặp ở phần 40): khi bạn đọc một file tuần tự, nhân phát hiện mẫu và đọc trước các trang kế tiếp từ đĩa vào page cache. Đây là chuyện đĩa → RAM.

Tầng 2 — hardware prefetcher (phần cứng trong CPU): khi CPU thấy bạn truy cập bộ nhớ theo một stride đều (đều đặn — mỗi lần nhảy một khoảng cố định), nó chủ động nạp trước cache line kế tiếp từ RAM vào cache L1/L2. Đây là chuyện RAM → cache, xảy ra hoàn toàn trong CPU, không liên quan file hay hệ điều hành.

Điểm chung: cả hai chỉ thắng khi mẫu truy cập đoán được — đúng cái trợ lý chỉ lật trước được khi bạn đọc theo thứ tự. Truy cập ngẫu nhiên đánh bại cả hai — nhân không biết đọc trước trang nào, CPU không biết nạp trước cache line nào. Tôi cô lập tầng phần cứng bằng một mảng 512 MB đã nằm sẵn trong RAM (không đĩa, không file), và duyệt nó theo các mẫu khác nhau.

Đo: 423 lần, chỉ khác cách chạm

Duyệt mảng 512 MB (67 triệu phần tử 8 byte) trong RAM:
  TUẦN TỰ stride 1  (8 B) : 0,28 ns/truy cập
  TUẦN TỰ stride 4  (32 B): 0,31 ns
  TUẦN TỰ stride 16 (128B): 0,65 ns
  TUẦN TỰ stride 64 (512B): 1,25 ns   (stride ĐỀU -> prefetcher vẫn đoán được)
  NGẪU NHIÊN pointer-chase: 107,45 ns/truy cập  (mỗi lần một cache miss)
  -> tuần tự stride 1 (0,28 ns) vs ngẫu nhiên (107 ns) = ngẫu nhiên CHẬM 423 lần

Duyệt tuần tự stride 1 tốn 0,28 nano-giây mỗi phần tử — gần như miễn phí, vì prefetcher phần cứng chạy trước bạn, nạp sẵn cache line kế vào L1 trước khi bạn chạm tới. Duyệt ngẫu nhiên (một pointer-chase theo hoán vị vòng, mỗi bước phụ thuộc bước trước nên không thể đoán) tốn 107,45 nano-giây — đúng bằng độ trễ một truy cập RAM thật ta đo ở phần 37, vì mỗi lần chạm là một cache miss, CPU phải chờ RAM. Chênh nhau 423 lần — dù đọc cùng số phần tử từ cùng một mảng. Cái tên "Random Access Memory" gây hiểu lầm: bạn truy cập được mọi địa chỉ, nhưng chúng không đều giá.

Nhìn cột stride: từ stride 1 đến stride 64, thời gian tăng dần (0,28 → 1,25 ns) vì stride lớn hơn thì mỗi cache line 64 byte phục vụ ít phần tử hơn (ít amortize). Nhưng — điểm mấu chốt — tất cả các stride đều vẫn rất nhanh so với ngẫu nhiên: stride 64 vẫn chỉ 1,25 ns, tức ~86 lần nhanh hơn ngẫu nhiên 107 ns. Vì prefetcher xử lý được cả stride đều (nó nhận ra "cứ nhảy 512 byte một lần" và nạp trước theo nhịp đó). Thứ giết prefetch không phải khoảng cách, mà là tính không đoán được.

(Môi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, mảng 512MB nằm sẵn trong RAM, mỗi số lấy MIN sau warmup. Con số đổi theo máy; cái cần nhìn là mẫu đều (dù stride lớn) rẻ hơn mẫu ngẫu nhiên hàng trăm lần.)

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

Tôi vào đo với hai niềm tin. Thứ nhất: "bộ nhớ là Random Access Memory — truy cập địa chỉ nào cũng tốn như nhau". Con số bác thẳng — tuần tự 0,28 ns, ngẫu nhiên 107 ns, chênh 423 lần. RAM cho phép truy cập ngẫu nhiên (khác băng từ tuần tự), nhưng không có nghĩa là đều giá: mẫu đoán được rẻ hơn nhiều nhờ prefetcher.

Thứ hai: "prefetch chỉ giúp đọc tuần tự sát nhau (stride 1)". Cũng sai — prefetcher đoán được cả stride đều lớn (stride 64 vẫn nhanh 86 lần so với ngẫu nhiên); cái nó không đoán được là mẫu ngẫu nhiên/phụ thuộc dữ liệu. Nói cách khác, hiệu năng truy cập bộ nhớ được quyết định bởi mẫu đoán được hay không, không phải bởi khoảng cách hay lượng dữ liệu.

Hệ quả rất thực tế cho cấu trúc dữ liệu: một mảng liền duyệt tuần tự nhanh hơn rất nhiều so với một danh sách liên kết / cây / bảng băm nơi bạn nhảy con trỏ khắp bộ nhớ — dù cùng số phần tử. Nếu tôi tin "RAM nào cũng như nhau", tôi đã chọn cấu trúc dữ liệu theo độ phức tạp Big-O trên giấy mà bỏ qua mẫu truy cập thực — thứ có thể làm một O(n) "chậm" (mảng) đánh bại một O(1) "nhanh" (hash) trong thực tế vì prefetch.

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

Điều đầu tiên: ưu tiên cấu trúc dữ liệu liền mạch, duyệt theo mẫu đoán được. Mảng (std::vector, mảng C) duyệt tuần tự để prefetcher và cache làm việc; tránh nhảy con trỏ lung tung khi có thể. Đây là lý do "data-oriented design" trong game/hệ thống hiệu năng cao gom dữ liệu vào mảng phẳng (structure-of-arrays) thay vì rải rác qua con trỏ — cùng thuật toán, nhưng mẫu truy cập thân thiện prefetch nhanh hơn nhiều lần.

Điều thứ hai: khi mẫu bất quy tắc nhưng biết trước, dùng software prefetch. Nếu bạn biết địa chỉ sắp cần nhưng nó không theo stride đều (ví dụ duyệt một danh sách chỉ mục), __builtin_prefetch(ptr) bảo CPU nạp trước một cache line — hữu ích khi bạn có thể tính địa chỉ sớm vài vòng lặp. Ở tầng file, posix_fadvise/readahead() là công cụ tương đương cho đĩa. Nhưng cả hai chỉ giúp khi bạn đoán đúng; đoán sai chỉ phí băng thông.

Chỗ này lý giải rất nhiều hành vi ở tầng cao mà thoạt nhìn khó hiểu. Vì sao các engine phân tích cột (ClickHouse, DuckDB) và định dạng như Parquet nhanh đến vậy trên quét lớn? Vì chúng lưu mỗi cột liền mạch và quét tuần tự — prefetcher chạy hết công suất. Vì sao duyệt một ArrayList trong Java nhanh hơn hẳn LinkedList cùng số phần tử, dù cả hai "O(n)"? Cùng lý do: mảng liền cho prefetch, con trỏ nhảy thì không. Và vì sao các database khuyên quét theo thứ tự khóa chính (clustered index) thay vì truy cập ngẫu nhiên theo secondary index cho truy vấn quét dải lớn? Cũng là readahead + prefetch thưởng cho tuần tự. Ngay cả GC kiểu compacting (Java, Go) dồn đối tượng sống lại liền nhau một phần để việc duyệt sau đó thân thiện prefetch. Cùng một bài học trợ-lý-lật-trang-trước, lặp lại từ cache CPU tới đĩa tới cụm máy.

Muốn tự thấy thì cấp một mảng lớn (vài trăm MB) và tính tổng của nó theo hai cách, bấm giờ mỗi cách: một lần duyệt tuần tự (for i: s += a[i]), một lần duyệt theo một hoán vị ngẫu nhiên (mỗi bước nhảy tới một chỉ số ngẫu nhiên, kiểu pointer-chase để không thể đoán). Bạn sẽ thấy phiên bản ngẫu nhiên chậm hàng chục tới hàng trăm lần — dù đọc cùng số phần tử. Rồi thử duyệt theo stride đều nhưng lớn (mỗi lần nhảy 512 byte): nó vẫn nhanh hơn ngẫu nhiên rất nhiều, vì stride đều thì prefetcher vẫn đoán được. Vài phút đó cho bạn thấy một sự thật mà cái tên "Random Access Memory" giấu đi: truy cập được mọi địa chỉ không có nghĩa là mọi mẫu truy cập đều nhanh như nhau — và chọn cấu trúc dữ liệu, thuật toán theo mẫu truy cập thường quan trọng hơn con số Big-O.