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. 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ột lần tôi đo hớ: "RAM truy cập nào cũng như nhau"
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". Sai — 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)". 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.
Bài học đo lường: 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 lượng dữ liệu — prefetcher (phần cứng và nhân) thưởng cho mẫu đều, trừng phạt mẫu ngẫu nhiên, và khoảng cách chênh có thể tới hàng trăm lần. 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ì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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.
Hệ quả thứ ba là tinh thần đo lường: đo với mẫu truy cập thật, đừng giả định "một lần đọc bộ nhớ là một lần đọc bộ nhớ". Con số mang theo: đoán-trước có hai tầng (kernel file readahead: đĩa->cache, phần 40; hardware prefetcher: RAM->cache line), cả hai chỉ thắng khi mẫu ĐOÁN ĐƯỢC. Đo thuần RAM: duyệt mảng 512MB tuần tự stride 1 = 0,28 ns/phần tử vs ngẫu nhiên pointer-chase = 107 ns = CHẬM 423×; stride đều lớn (64=512B) vẫn 1,25 ns (86× nhanh hơn ngẫu nhiên) vì prefetcher xử lý được stride đều — cái giết nó là tính KHÔNG đoán được, không phải khoảng cách. Nên mảng liền + duyệt tuần tự nhanh hơn con trỏ nhảy (list/cây/hash) dù cùng số phần tử. "Random Access Memory" truy cập được ngẫu nhiên, nhưng đừng nhầm là rẻ như nhau.
Thử ba mươi giây
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. Ba mươi giây đó 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.
