Hai phần trước đo độ trễ tầng cache và kích thước dòng cache. Nhưng có một tính chất tinh vi hơn của cache mà ít người để ý, và nó làm code chậm bất thường theo cách rất khó lần: tính kết hợp (associativity).

Hình dung một bãi giữ xe có hàng nghìn chỗ, nhưng luật gửi xe kỳ quặc: biển số xe của bạn quyết định bạn được đỗ ở dãy nào, và mỗi dãy chỉ có đúng 6-7 ô. Nếu tám người có biển số "hợp tuổi" cùng bị chỉ về một dãy, thì dù cả bãi còn trống mênh mông, dãy đó không đủ chỗ — người thứ tám phải đợi ai đó ra. Cache của CPU vận hành y hệt: nó không cho một dòng dữ liệu đỗ ở bất kỳ chỗ nào — mỗi địa chỉ chỉ vào được một tập (set) cố định, và mỗi set giữ được vài dòng. Hệ quả: nếu nhiều địa chỉ tình cờ ánh xạ về cùng một set và vượt số chỗ, chúng đá nhau ra — conflict miss — dù tổng dữ liệu bạn dùng nhỏ hơn cache rất nhiều. Tôi đo trong container gcc:13 trên host ARM, và con số cho thấy chỉ vài chục byte cũng có thể miss cache liên tục.

Mỗi địa chỉ vào một set, mỗi set chỉ vài chỗ

Cache là tập-kết-hợp (set-associative). Nó chia thành nhiều set (dãy đỗ xe), mỗi set có N đường (way) — N là associativity (ví dụ cache 8-way nghĩa là mỗi set giữ được 8 dòng). Một địa chỉ chỉ được cache vào đúng một set, xác định bởi vài bit giữa của địa chỉ (set = (địa_chỉ / cỡ_dòng) % số_set) — chính là "biển số quyết định dãy".

Điều nguy hiểm: nếu bạn truy cập nhiều địa chỉ cách nhau đúng một bội lũy thừa 2 lớn (như 4 KB, 64 KB), các bit giữa của chúng giống nhau — nên chúng dồn hết vào cùng một set. Khi số địa chỉ như vậy vượt số way, chúng liên tục đẩy nhau ra khỏi cache. Đây là conflict miss: cache còn rất nhiều chỗ trống ở các set khác, nhưng cái set bạn cần thì đầy, nên bạn miss dù tổng dữ liệu tí xíu (giống va chạm băm khi nhiều khóa dồn một bucket).

Cách đo: đuổi con trỏ qua K địa chỉ cách nhau một stride nhất định, tăng K. Nếu stride là lũy thừa 2 (dồn cùng set), thời gian sẽ nhảy khi K vượt số way — và K đó chính là associativity. Nếu stride không lũy thừa 2 (rải đều các set), thời gian phẳng dù K lớn.

Đo: 8 con trỏ cũng conflict, và nó lộ số way

Tôi đuổi con trỏ qua K node cách nhau stride, so hai stride: 64 KB (lũy thừa 2) và 64 KB + 512 (không lũy thừa 2):

Đuổi con trỏ K node cách nhau stride, ns/truy cập, host ARM, g++ -O2:

    K   | stride 64 KB (lũy thừa 2) | stride 64 KB + 512 (không lũy thừa 2)
   -----|---------------------------|--------------------------------------
    2–6 |  0,910 ns  (L1 hit)       |  0,910 ns
     8  |  3,115 ns  (NHẢY!)        |  0,910 ns
    16  |  4,48 ns                  |  0,911 ns
    32  |  4,50 ns                  |  0,910 ns
    48  |  6,14 ns                  |  0,910 ns

Nhìn cột stride 64 KB (lũy thừa 2): với K từ 2 đến 6, mọi truy cập tốn 0,910 ns — các node vừa vặn trong các way của cùng một set, nằm trong L1. Đến K = 8, thời gian nhảy vọt lên 3,115 ns — cái set đó chỉ chứa được ~6–7 dòng, nên 8 node bắt đầu đá nhau ra, phải nạp lại từ tầng dưới. K càng lớn càng chậm (4,5 → 6,1 ns). Điều đáng kinh ngạc: tổng dữ liệu bạn thật sự dùng ở K=8 chỉ là 8 con trỏ — vài chục byte — nhỏ hơn cache hàng triệu lần, mà vẫn miss liên tục. Đó là conflict miss thuần túy: cả bãi xe trống mà một dãy vẫn kẹt.

Nhìn cột stride 64 KB + 512 (không lũy thừa 2): phẳng lì 0,910 ns ở mọi K, kể cả K=48. Vì các địa chỉ giờ rải đều khắp các set (bit giữa khác nhau), không set nào bị quá tải. Cùng số node, cùng số truy cập, cùng khoảng cách xấp xỉ nhau — nhưng chênh 5–7 lần chỉ vì một cái stride tình cờ là lũy thừa 2 hay không.

Và ngưỡng conflict tiết lộ associativity: K=6 còn nhanh, K=8 đã chậm → cái set giữ được khoảng 6–7 dòng → cache này (L1) khoảng 6–7-way (đo trên host ARM này; số way khác nhau theo máy).

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

Tôi vào đo với một giả định rất hợp lý: "nếu dữ liệu tôi dùng nhỏ hơn dung lượng cache, nó chắc chắn nằm hết trong cache, không miss". Con số bác ngay: chỉ 8 con trỏ (vài chục byte) mà chậm gấp 3–4 lần, vì chúng cách nhau đúng 64 KB (lũy thừa 2) nên dồn vào cùng một set, và set đó chỉ có ~6 way — thừa ra thì đá nhau. Dung lượng cache tổng cộng vô nghĩa nếu dữ liệu của bạn tập trung vào ít set. "Nhỏ hơn cache" chỉ đảm bảo không capacity miss (tràn dung lượng), không đảm bảo tránh conflict miss (tràn một set).

Nhưng nếu vì thế mà nghĩ ngược lại — "stride/khoảng cách giữa các địa chỉ không quan trọng, miễn cùng số truy cập thì cùng tốc độ" — thì cũng sai, và sai theo cách khó chịu nhất: cùng K node, cùng số lần chạm, khoảng cách gần bằng nhau (64 KB vs 64 KB + 512), nhưng cái stride lũy thừa 2 dồn hết vào một set (chậm 5–7 lần) còn stride lẻ rải đều (nhanh). Sự khác biệt nằm ở một tính chất số học của địa chỉ — bit giữa — mà không có trong Big-O, không có trong mã nguồn, chỉ lộ ra khi đo. Đây là lý do các mảng 2D với chiều là lũy thừa 2 "đẹp" (1024×1024) đôi khi chậm hơn kích thước lẻ (1024×1025) — cột của chúng conflict trong cache.

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

Việc đầu tiên: tránh các bước nhảy lũy thừa 2 "đẹp" trong truy cập bộ nhớ nóng — thêm padding lệch. Nếu bạn truy cập một cột của mảng 2D, hay lấy cùng offset trong nhiều khối cách đều lũy thừa 2, chúng có thể conflict trong cache. Cách chữa kinh điển: làm chiều/khoảng cách không là lũy thừa 2 — ví dụ cấp mảng [N][1025] thay vì [N][1024], hoặc thêm vài phần tử padding — để các truy cập rải đều các set. Đây là một tối ưu "kỳ lạ" nhưng thật: thêm dữ liệu thừa lại làm nhanh hơn.

Việc thứ hai: biết cache của bạn nhỏ hơn nó tưởng khi truy cập lệch. Dung lượng cache là dung lượng lý tưởng — chỉ đạt được khi truy cập rải đều các set. Với mẫu truy cập lệch (dồn ít set), cache hiệu dụng nhỏ hơn nhiều (chỉ associativity dòng mỗi set nóng). Khi thiết kế cấu trúc dữ liệu cho hiệu năng, nghĩ tới việc các truy cập có rải đều không, hay dồn vào cùng vài set.

Cái bẫy "lũy thừa 2 quá đẹp hóa ra hại" này quen thuộc đến mức các thư viện tính toán hiệu năng cao đều biết né. Thư viện đại số tuyến tính (BLAS, thư viện học sâu) thường đệm chiều của ma trận lên một số không-lũy-thừa-2 (padding to a non-power-of-2 stride) đúng để tránh conflict miss khi duyệt cột — bạn khai 1024 nhưng bên trong nó cấp phát 1024 cộng vài phần tử. Ngay cả người viết Java hay Go, tuy không kiểm soát địa chỉ trực tiếp, vẫn gặp bóng dáng nó: một HashMap/map dung lượng lũy thừa 2 băm kém với các khóa có bit thấp trùng nhau sẽ dồn vào ít bucket, cùng tinh thần "địa chỉ số học quyết định phân bố". Bài học chung: hiệu năng bộ nhớ phụ thuộc tính số học của địa chỉ, không chỉ dung lượng — và một kích thước tròn trịa tưởng vô hại có thể là kích thước tệ nhất.

Muốn tự thấy thì cấp một buffer lớn và đuổi con trỏ qua K node cách nhau đúng 64 KB (một lũy thừa 2), lặp nhiều lần, đo ns mỗi truy cập. Tăng K từ 2, 4, 6, 8, 16: bạn sẽ thấy tới một K nào đó (số way của cache) thời gian nhảy vọt — dù bạn chỉ chạm K con trỏ, vài chục byte. Đó là conflict miss: các node dồn vào một set và đá nhau ra. Rồi đổi khoảng cách thành 64 KB + 512 (không lũy thừa 2) và đo lại: lần này thời gian phẳng ở mọi K, vì các node rải đều các set. Cuối cùng, thử một ma trận vuông kích thước 1024 so với 1025 và cộng theo cột (truy cập lệch một hàng mỗi bước) — bản 1024 (lũy thừa 2) có thể chậm hơn 1025 vì cột của nó conflict. Ba mươi giây đó cho thấy điều mà "dữ liệu nhỏ hơn cache thì an toàn" giấu đi: cache có cấu trúc set, mỗi set chỉ vài chỗ, và một khoảng cách địa chỉ tình cờ là lũy thừa 2 có thể nhồi mọi truy cập vào một set — biến một cache lớn thành một cái chật ních dù bạn dùng rất ít dữ liệu.