Đọc 1 byte, CPU nạp cả 128: cái giá của đọc thưa

Phần trước đo độ trễ của từng tầng cache. Phần này đo đơn vị mà cache làm việc: không phải từng byte, mà cả một dòng (cache line).

Hình dung bạn đặt nước ngọt ở cửa hàng, nhưng họ chỉ bán theo thùng 24 lon. Cần một lon? Vẫn phải khiêng về nguyên thùng. Nếu bạn dùng cả 24 lon thì tuyệt — mỗi lon coi như "miễn phí" sau cú khiêng đầu. Nhưng nếu mỗi thùng bạn chỉ lấy đúng một lon rồi vứt 23 lon còn lại, bạn đang trả tiền và công sức cho cả thùng mà chỉ hưởng một phần nhỏ. CPU nạp bộ nhớ y hệt: khi cần một byte, nó không nạp riêng byte đó — nó kéo về cả dòng chứa byte đó (thường 64 byte trên x86, và như ta sẽ đo, 128 byte trên nhiều ARM). Hai hệ quả: các byte lân cận trong cùng dòng gần như miễn phí sau đó, còn đọc dữ liệu thưa thì phí gần cả thùng mỗi lần. Tôi đo trong container gcc:13 trên host ARM, và phép đo vừa chứng minh nguyên lý "trả theo dòng", vừa tiết lộ một điều bất ngờ về máy này.

Nạp cả dòng, không nạp từng byte

Bộ nhớ được cache quản lý theo từng dòng cố định — một khối liền nhau (64 byte trên phần lớn x86; 128 byte trên nhiều lõi ARM). Khi bạn chạm một địa chỉ chưa có trong cache, CPU nạp cả dòng chứa nó từ tầng dưới lên. Sau đó, mọi byte khác trong dòng đó đã sẵn sàng — chạm chúng gần như miễn phí.

Điều này cho một cách đo kích thước dòng: duyệt một mảng lớn hơn cache (để mỗi dòng phải nạp từ bộ nhớ), cộng một byte mỗi stride byte, rồi đo ns mỗi phần tử chạm theo stride:

• Stride nhỏ hơn dòng: nhiều phần tử bạn chạm nằm chung một dòng. Một lần nạp dòng phục vụ nhiều phần tử → chi phí mỗi phần tử thấp.
• Stride bằng dòng: mỗi phần tử rơi vào một dòng riêng → mỗi phần tử tốn một lần nạp dòng → đắt nhất trên mỗi phần tử.
• Stride lớn hơn dòng: vẫn một phần tử mỗi dòng, nên ns mỗi phần tử bão hòa. Ngưỡng bão hòa chính là kích thước dòng.

Đo: đọc thưa chậm 10 lần, và dòng là 128 byte

Tôi duyệt một mảng 128 MB (vượt cache), cộng một byte mỗi stride, đo ns mỗi phần tử chạm:

Mảng 128 MB (vượt cache), cộng 1 byte mỗi stride, tuần tự, host ARM, g++ -O2:

   stride (byte) | ns/phần tử chạm | so với 4B | ghi chú
   --------------|-----------------|-----------|-------------------------
        4        |   0,246 ns      |  1,0x     | nhiều phần tử / dòng -> rẻ
        8        |   0,248 ns      |  1,0x     |
       16        |   0,256 ns      |  1,0x     |
       32        |   0,452 ns      |  1,8x     |
       64        |   0,902 ns      |  3,7x     |
      128        |   2,334 ns      |  9,5x     | 1 phần tử / dòng
      256        |   2,645 ns      | 10,7x     | bão hòa (128->256 chỉ +13%)

Nhìn đường cong: ns mỗi phần tử tăng dần theo stride — từ 0,246 ns (stride 4) lên 2,334 ns (stride 128), rồi bão hòa (stride 256 chỉ cao hơn 13%). Toàn bộ khác biệt là tận dụng dòng: ở stride 4, mỗi dòng nạp về phục vụ nhiều phần tử nên chi phí chia đều rất nhỏ (dùng cả thùng); ở stride 128, mỗi phần tử là một dòng riêng nên trả trọn chi phí nạp dòng (một lon mỗi thùng) — chi phí mỗi phần tử nhảy ~10 lần vì mất đi sự chia sẻ dòng.

Và đây là điều bất ngờ: ngưỡng bão hòa rơi vào ~128 byte, không phải 64. Từ stride 64 lên 128, ns/phần tử vẫn tăng mạnh (0,902 → 2,334, gấp 2,6 lần) — nghĩa là ở stride 64 các phần tử vẫn chia sẻ dòng, nên dòng lớn hơn 64. Chỉ từ 128 lên 256 nó mới phẳng (+13%). Vậy dòng cache của host này là 128 byte — đây là một lõi ARM kiểu Apple Silicon, dùng dòng 128 byte, khác với con số 64 byte quen thuộc của x86. Tiêu đề nói "64 byte" (giá trị phổ biến), nhưng đo trên máy này ra 128. Kích thước dòng tùy kiến trúc — chỉ đo mới chắc máy của bạn.

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

Tôi vào đo với mô hình ngây thơ: "đọc một byte thì tốn một byte băng thông; đọc ít dữ liệu thì nhanh". Con số bác ngay: chạm một byte nạp cả một dòng (128 byte trên máy này). Nếu bạn đọc dữ liệu thưa — một phần tử mỗi dòng — bạn phí gần như toàn bộ mỗi dòng nạp về, và chi phí mỗi phần tử đắt gấp ~10 lần so với đọc liền. Băng thông thật bạn tiêu là số dòng × kích thước dòng, không phải số byte bạn thực sự dùng. Một cấu trúc dữ liệu buộc truy cập thưa (con trỏ rải rác, trường xa nhau) âm thầm đốt băng thông gấp nhiều lần.

Nhưng nếu vì thế mà đóng đinh "dòng cache luôn là 64 byte, nhớ con số đó là đủ" thì cũng sai. Đo trên host ARM này ngưỡng bão hòa ở ~128 byte → dòng 128 byte, không phải 64. Apple Silicon và một số ARM dùng dòng 128 byte; x86 dùng 64; có kiến trúc khác nữa. Nếu bạn tối ưu (căn lề, padding chống false sharing) theo con số 64 cố định trên một máy dùng 128, bạn có thể tính sai. Con số 64 là mặc định x86, không phải hằng số vũ trụ — đo kích thước dòng của máy mục tiêu mới chắc.

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

Việc đầu tiên: gói dữ liệu dùng cùng lúc vào cùng một dòng cache, tránh truy cập thưa. Nếu bạn luôn đọc vài trường của một struct cùng nhau, đặt chúng cạnh nhau (vừa một dòng); nếu duyệt một mảng, giữ nó liền và tuần tự. Truy cập thưa (con trỏ tới node rải rác, trường nằm cách xa, cột trong AoS mà chỉ cần một trường) khiến mỗi dòng nạp về chỉ dùng một phần nhỏ — đốt băng thông gấp bội. Đây là gốc rễ của SoA thắng AoS khi chỉ cần một trường.

Việc thứ hai: đo kích thước dòng của máy mục tiêu, đừng giả định 64. Cho tối ưu nhạy với dòng — căn lề để tránh một cấu trúc bắc cầu hai dòng, padding chống false sharing — dùng đúng kích thước dòng của phần cứng. Trên Linux đọc /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size, hoặc std::hardware_destructive_interference_size trong C++17, hoặc đo như bài này. Trên x86 thường 64, trên Apple Silicon 128 — sai con số này làm padding thừa hoặc thiếu.

Cái "bán theo thùng" này chi phối hiệu năng ở mọi tầng, chỉ đổi tên đơn vị. Trong Java, một mảng int[] liền mạch tận dụng trọn mỗi dòng cache, còn một Integer[] (mảng con trỏ tới object rải khắp heap) biến mỗi phần tử thành một cú nhảy dòng riêng — đúng kiểu "một lon mỗi thùng", và là một lý do các thư viện primitive-collection (Eclipse Collections, fastutil) tồn tại. Cả làn sóng columnar storage (Parquet, Arrow, ClickHouse) cũng dựa trên chính điều này: khi truy vấn chỉ cần vài cột, lưu các giá trị cùng cột liền nhau khiến mỗi dòng cache (và mỗi trang đĩa) nạp về toàn dữ liệu hữu ích, thay vì lôi cả bản ghi rồi vứt phần lớn. Còn khi đọc từ đĩa hay mạng, "dòng cache" đổi tên thành block/page nhưng bài học không đổi — đọc tuần tự dùng trọn khối, đọc rải rác phí gần cả khối. Nguyên tắc xuyên suốt: đơn vị của bộ nhớ (và lưu trữ) là khối, không phải byte.

Muốn tự thấy thì cấp một mảng lớn hơn cache (vài chục MB), rồi cộng một byte mỗi stride byte, với stride = 4, 8, 16, 32, 64, 128, 256, chia thời gian cho số phần tử chạm để ra ns mỗi phần tử. Bạn sẽ thấy đường cong tăng dần rồi bão hòa: khi stride nhỏ, nhiều phần tử chia sẻ một dòng nên rẻ; khi stride đạt kích thước dòng, mỗi phần tử một dòng riêng nên đắt nhất; vượt qua đó thì phẳng. Điểm nó bắt đầu phẳng cho bạn kích thước dòng cache của máy — có thể là 64 (x86) hoặc 128 (Apple Silicon). Rồi thử một thí nghiệm ngược: đọc tất cả phần tử (stride 4) so với đọc một phần tử mỗi dòng (stride bằng kích thước dòng) trên cùng mảng — tổng thời gian gần bằng nhau dù bản thứ hai đọc ít phần tử hơn nhiều, vì cả hai đều nạp cùng số dòng. Ba mươi giây đó cho thấy điều mà "đọc một byte tốn một byte" giấu đi: bộ nhớ chuyển theo dòng, và cả cách bạn gói dữ liệu lẫn kích thước dòng của máy quyết định bạn tận dụng hay lãng phí băng thông.