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ó có thể làm code chậm bất thường theo cách rất khó lần: tính kết hợp (associativity). Cache không cho một dòng dữ liệu nằm ở bất kỳ chỗ nào trong nó — 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, 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).
Đ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.
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).
Một lần tôi đo hớ: "dữ liệu nhỏ hơn cache thì luôn ở trong cache" và "stride nào cũng như nhau"
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". Đo phá tan: 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 đo cũng phá một niềm tin ngược: "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 độ". 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.
Bài học đo lường: cache là tập-kết-hợp — mỗi địa chỉ vào MỘT set (theo bit giữa), mỗi set giữ vài way. Địa chỉ cách nhau LŨY THỪA 2 dồn cùng set; vượt số way -> ĐÁ NHAU ra (conflict miss) dù tổng dữ liệu NHỎ hơn cache nhiều (đo: 8 con trỏ, vài chục byte, chậm 3-4x ở K=8; stride 64KB conflict, stride 64KB+512 phẳng 0,9 ns tới K=48). Ngưỡng conflict = associativity (đo ~6-7 way). 'Nhỏ hơn cache' KHÔNG đảm bảo nằm trong cache; stride 2^k gây conflict. Nếu tôi tin "nhỏ hơn cache thì an toàn" tôi không giải thích được miss bất thường; nếu tin "stride không quan trọng" tôi dùng kích thước lũy thừa 2 và trúng conflict.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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.
Hệ quả thứ ba là tinh thần đo lường: hiệu năng cache phụ thuộc địa chỉ số học, không chỉ dung lượng — và conflict miss là một cạm bẫy vô hình. Con số mang theo: cache set-associative: địa chỉ cách nhau lũy thừa 2 dồn cùng set, vượt số way thì conflict miss dù tổng dữ liệu nhỏ hơn cache (đo: 8 con trỏ chậm 3-4x, stride lẻ phẳng); associativity = K nơi bắt đầu conflict (~6-7 way). Tránh stride 2^k, thêm padding lệch. Cùng thuật toán, cùng lượng dữ liệu, mà một lựa chọn kích thước tưởng vô hại có thể đốt hiệu năng — đo mới thấy.
Thử ba mươi giây
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 bạn 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.
