Nhiều phần trong sê-ri này chạm tới cache như một thủ phạm giấu mặt. Phần này gọi thẳng tên hiện tượng tệ nhất của nó: cache thrashing — khi mẫu truy cập của bạn làm các dòng cache liên tục đá nhau ra trước khi kịp tái dùng, biến mỗi truy cập thành một lần miss. Điều đáng sợ là nó xảy ra cùng một thuật toán, cùng một số phép tính — chỉ khác cách bạn đi qua dữ liệu. Big-O không nhìn thấy nó, nhưng đồng hồ thì có. Tôi đo trong container gcc:13 trên host ARM, dùng ví dụ kinh điển nhất: nhân ma trận với hai thứ tự vòng lặp khác nhau, cộng một thí nghiệm về tái dùng.
Đá nhau ra trước khi kịp tái dùng
Cache giữ dữ liệu nóng gần CPU, nhưng nó nhỏ. Khi bạn nạp một dòng mới mà cache đã đầy, một dòng cũ bị đá ra (theo LRU — ít dùng gần đây nhất). Thrashing là khi việc đá-ra này xảy ra dồn dập và vô ích: bạn nạp một dòng, dùng một chút, rồi nó bị đá ra trước khi bạn quay lại dùng tiếp — nên lần sau bạn phải nạp lại từ đầu. Cache có đó mà như không, mọi truy cập trả độ trễ bộ nhớ đầy đủ.
Hai nguồn thrashing chính. Một: working set vượt cache khi tái dùng. Nếu bạn lặp đi lặp lại qua một vùng lớn hơn cache, thì tới lúc quay lại đầu vùng, những dòng đầu đã bị đá sạch — mỗi vòng đều miss. Hai: mẫu truy cập tồi. Ngay cả khi tổng dữ liệu vừa cache, nếu bạn đi nhảy cóc (stride lớn, truy cập theo cột) hoặc dồn vào ít tập, bạn phí phần lớn mỗi dòng và đá dữ liệu hữu ích ra sớm. Tôi đo cả hai.
Đo: cùng số FLOP, đổi thứ tự vòng lặp → nhanh 3,1 lần
Host ARM, g++ -O2:
(A) Lặp lại một vùng nhiều lượt (ns mỗi dòng cache chạm):
working set 64 KB (vừa L1) | 0,232 ns <- lượt sau đọc từ cache
working set 4 MB (vừa L2) | 0,463 ns
working set 64 MB (vượt cache) | 0,909 ns <- mỗi lượt nạp lại (thrash)
(B) Nhân ma trận 1024x1024 float (CÙNG 2,1 tỷ FLOP, chỉ đổi thứ tự vòng lặp):
ijk (đọc B theo CỘT -> thrash) | 2,65 GFLOP/s
ikj (đổi thứ tự, đọc theo HÀNG) | 8,13 GFLOP/s -> 3,1x nhanh hơn
tiled (chia khối 64, vừa cache) | 7,79 GFLOP/s -> 2,9x nhanh hơn
Đọc ra hai điều. Một (tái dùng — working set vs cache): lặp lại một vùng 64 KB (vừa L1) tốn 0,232 ns mỗi dòng, vì sau lượt đầu mọi lượt đọc từ cache. Cùng kiểu lặp trên vùng 64 MB (vượt cache) tốn 0,909 ns — chậm ~4 lần — vì mỗi lượt, tới khi quay lại đầu vùng thì LRU đã đá sạch, phải nạp lại từ RAM. (Đây là truy cập tuần tự nên prefetch giấu bớt, chênh chỉ 4 lần; với truy cập ngẫu nhiên khoảng cách này lên tới trăm lần.)
Hai (thứ tự vòng lặp — cú sốc chính): nhân hai ma trận 1024×1024 tốn đúng 2,1 tỷ phép nhân-cộng dù bạn viết vòng lặp thế nào. Nhưng thứ tự ijk (vòng trong chạy k, đọc B[k][j] — nhảy theo cột, mỗi truy cập một dòng mới) làm thrash: chỉ 2,65 GFLOP/s. Đổi sang thứ tự ikj (đọc B và C theo hàng, liền mạch) đạt 8,13 GFLOP/s — nhanh 3,1 lần, cùng số phép tính, chỉ hoán vị hai vòng lặp. Và tiled (chia ma trận thành khối 64×64 vừa cache, xử lý từng khối) đạt 7,79 GFLOP/s — 2,9 lần. Cùng thuật toán O(n³), cùng số FLOP, mà tốc độ chênh 3 lần chỉ vì cách duyệt quyết định cache hit hay thrash.
Một lần tôi đo hớ: "thứ tự vòng lặp không quan trọng" và "nhỏ hơn cache thì không thrash"
Tôi vào đo với niềm tin thuật toán thuần túy: "cùng độ phức tạp O(n³), cùng số phép nhân-cộng, thì viết vòng lặp thế nào cũng chạy như nhau — thứ tự chỉ là chi tiết". Đo phá tan: ijk và ikj làm y hệt 2,1 tỷ phép, nhưng ikj nhanh 3,1 lần, vì ijk đọc ma trận B theo cột (stride lớn) khiến mỗi truy cập là một dòng cache mới, đá dữ liệu hữu ích ra liên tục. Thứ tự vòng lặp không phải chi tiết — nó là khác biệt giữa dùng cache và phá cache. Big-O đếm số phép; nó không đếm dòng cache, mà chính dòng cache định đoạt hằng số.
Nhưng đo cũng chỉnh niềm tin ngược: "chỉ cần tổng dữ liệu nhỏ hơn cache thì không bao giờ thrash, khỏi lo". Sai theo hai cách. Thứ nhất, nếu bạn lặp đi lặp lại qua một vùng lớn hơn cache (rất thường gặp: nhiều pass trên một mảng lớn), mỗi lượt đá sạch dữ liệu trước khi bạn quay lại — thrash (đo được L1 0,23 vs RAM 0,91 ns mỗi dòng). Thứ hai, ngay cả dữ liệu nhỏ hơn cache vẫn thrash nếu địa chỉ dồn vào cùng vài tập (conflict miss) — vài chục byte cũng có thể đá nhau liên tục. "Nhỏ hơn cache" đảm bảo không tràn dung lượng, không đảm bảo tái dùng tốt hay rải đều.
Bài học đo lường: cache thrashing = dòng cache bị đá ra trước khi tái dùng -> miss dồn dập, chậm hàng lần dù CÙNG số phép. Đo: nhân ma trận ijk (đọc B theo cột, thrash) 2,65 vs ikj (theo hàng) 8,13 GFLOP/s = 3,1x, CÙNG 2,1 tỷ FLOP; tiled 2,9x. Lặp lại vùng > cache: L1 0,23 vs RAM 0,91 ns/dòng (mỗi lượt nạp lại). 'Cùng O(n) thứ tự vòng lặp không quan trọng' SAI (thứ tự/tiling định đoạt, 3,1x); 'nhỏ hơn cache thì không thrash' SAI (lặp qua vùng > cache đá sạch; conflict miss đá dù nhỏ). Nếu tin "thứ tự không quan trọng" tôi viết ijk và mất 3x; nếu tin "nhỏ hơn cache là an toàn" tôi không giải thích được miss dồn dập.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: duyệt dữ liệu theo cách nó nằm trong bộ nhớ — hàng liền hàng, tuần tự — và chọn thứ tự vòng lặp cho truy cập liền mạch. Với ma trận lưu theo hàng, đừng đi theo cột ở vòng trong; hoán vị vòng lặp để truy cập liền. Đây là tối ưu miễn phí (chỉ đổi thứ tự) mà cho vài lần tốc độ. Quy tắc: vòng lặp trong cùng nên chạy trên chỉ số biến thiên nhanh nhất của bố cục bộ nhớ.
Hệ quả thứ hai: chia khối (blocking/tiling) khi phải tái dùng dữ liệu lớn hơn cache. Nếu thuật toán của bạn quét đi quét lại một mảng lớn (nhân ma trận, tích chập, xử lý ảnh, join trong CSDL), hãy chia thành khối vừa cache và làm xong hết việc trên một khối trước khi chuyển khối khác — để dữ liệu ở lại cache suốt thời gian được dùng. Đây là kỹ thuật nền tảng của mọi thư viện tính toán hiệu năng cao (BLAS, thư viện học sâu).
Hệ quả thứ ba là tinh thần đo lường: cùng một thuật toán có thể nhanh hay chậm nhiều lần tùy cách duyệt — thrash là chi phí Big-O không thấy. Con số mang theo: thứ tự vòng lặp/tiling định đoạt cache hit hay thrash (đo nhân ma trận 3,1x chỉ do đổi thứ tự); working set > cache khi tái dùng -> thrash; giữ dữ liệu nóng vừa cache và duyệt liền mạch. Khi một vòng lặp chậm bất thường mà số phép không đổi, hãy nghĩ tới cache trước tiên — và đo để biết bạn đang hit hay thrash.
Thử ba mươi giây
Viết nhân hai ma trận vuông (ví dụ 1024×1024) theo thứ tự vòng lặp i, j, k (vòng trong cộng dồn A[i][k]*B[k][j]) và bấm giờ. Rồi hoán vị thành thứ tự i, k, j (đưa k ra giữa, j vào trong) và bấm giờ lại: bạn sẽ thấy bản ikj nhanh vài lần — dù cùng số phép nhân-cộng — vì ijk đọc B theo cột (mỗi truy cập một dòng cache mới, thrash) còn ikj đọc B theo hàng (liền mạch, tái dùng dòng). Rồi thử chia khối: xử lý ma trận theo các ô 64×64 vừa cache, bạn sẽ thấy nhanh tương đương hoặc hơn. Cuối cùng, làm một thí nghiệm về tái dùng: cộng dồn một mảng vừa L1 nhiều lượt, rồi làm lại với mảng lớn hơn cache — bản lớn chậm hơn hẳn dù mỗi lượt đọc cùng số phần tử, vì mỗi lượt phải nạp lại từ RAM. Ba mươi giây đó cho bạn thấy điều mà "cùng O(n³) thì như nhau" giấu đi: số phép chỉ là một nửa câu chuyện; cách bạn đi qua dữ liệu — thứ tự vòng lặp, chia khối, tái dùng — quyết định cache là bạn hay kẻ thù, và khoảng cách đó đo được bằng lần.
