Bạn viết hai vòng lặp duyệt hết một ma trận — một theo hàng, một theo cột. Cùng số phần tử, cùng phép cộng, chỉ khác thứ tự. Trực giác nói chúng phải chạy như nhau. Nhưng đo lại thấy bản theo cột chậm gần hai chục lần. Thủ phạm là một hệ quả trực tiếp của dòng cache: CPU nạp bộ nhớ theo cả dòng, nên truy cập bước lớn (stride) khiến mỗi lần chạm chỉ dùng một mẩu nhỏ của dòng nạp về, phí phần còn lại. Tôi đo trong container gcc:13 trên host ARM, và đây là một trong những khác biệt lớn nhất mà "cùng số phép" hoàn toàn giấu đi.
Nạp cả dòng, nên bước lớn thì phí
CPU không nạp từng phần tử — nó nạp cả dòng cache (128 byte trên máy này, phần 6). Với int32 (4 byte), một dòng chứa 32 phần tử. Nếu bạn duyệt liền mạch (stride 1), một lần nạp dòng phục vụ 32 phần tử — dùng trọn dòng. Nhưng nếu bạn chạm cách nhau xa (stride lớn), mỗi lần chạm rơi vào một dòng riêng: CPU vẫn nạp cả 128 byte nhưng bạn chỉ dùng 4 — phí 31/32 mỗi dòng.
Ví dụ kinh điển: ma trận 2D lưu theo hàng (row-major, mặc định của C). Duyệt theo hàng (m[r][0], m[r][1], ...) là stride 1 — liền mạch. Duyệt theo cột (m[0][c], m[1][c], ...) là stride bằng một hàng — mỗi phần tử cách nhau cả hàng, rơi vào một dòng cache khác (và, nếu hàng đủ lớn, một trang nhớ khác → TLB miss). Tôi đo cả hai trên ma trận 4096×4096 int32 (64 MB, vượt cache).
Đo: cột chậm gần 18 lần
Ma trận 4096×4096 int32 (64 MB, vượt cache), host ARM:
duyệt | ns/phần tử | băng thông hữu ích | dùng dòng cache
--------------|------------|--------------------|------------------
THEO HÀNG (stride 1) | 0,211 | 18,9 GB/s | 32/32 phần tử (trọn dòng)
THEO CỘT (stride 16 KB) | 3,788 | 1,1 GB/s | 1/32 (4/128 byte, phí 31/32)
-> cột chậm hơn hàng: 17,9x
Cùng ma trận, cùng số phần tử (16 triệu), nhưng duyệt theo hàng tốn 0,211 ns mỗi phần tử còn theo cột tốn 3,788 ns — chậm hơn 17,9 lần. Lý do nằm ở dòng cache: duyệt hàng dùng cả 32 phần tử mỗi dòng (được prefetch nạp trước, băng thông hữu ích 18,9 GB/s, gần trần bộ nhớ), còn duyệt cột chỉ dùng 1 trên 32 — mỗi lần nạp một dòng đầy đủ mà chỉ lấy 4 byte, vứt 124 byte còn lại. Băng thông hữu ích của cột sụp còn 1,1 GB/s, dù hệ thống bộ nhớ vẫn bận rộn chuyển ~34 GB/s dòng cache — chỉ là hầu hết bị lãng phí. Cùng số phần tử, nhưng cột buộc CPU nạp gấp ~32 lần số byte dòng cache, cộng thêm lỗi TLB vì stride 16 KB vượt trang nhớ.
Một lần tôi đo hớ: "hàng hay cột như nhau" và "đọc ít phần tử là nhanh"
Tôi vào đo với trực giác thuật toán thuần: "duyệt hết ma trận là O(n²), theo hàng hay cột cũng cùng số phép, cùng thời gian". Đo phá tan: cột chậm 17,9 lần hàng — chỉ khác thứ tự truy cập. Vì CPU nạp theo dòng cache, thứ tự quyết định bạn dùng bao nhiêu của mỗi dòng nạp về. Duyệt liền mạch dùng trọn dòng; duyệt bước lớn phí 31/32. "Cùng số phần tử thì cùng thời gian" bỏ qua thứ thực sự tốn: số byte dòng cache phải kéo từ bộ nhớ, mà bước lớn làm phình lên hàng chục lần.
Nhưng đo cũng phá một niềm tin ngược, tinh vi hơn: "đọc ít phần tử thì nhanh; truy cập thưa (ít dữ liệu) rẻ hơn truy cập dày". Sai: một truy cập thưa với stride lớn nạp nhiều dòng cache dù chạm ít phần tử — mỗi phần tử kéo về một dòng 128 byte đầy đủ nhưng chỉ dùng 4. Cái quyết định thời gian không phải số phần tử bạn đọc, mà số byte dòng cache CPU phải chuyển (phần 6). Đọc 1 phần tử mỗi dòng cách xa nhau đắt ngang đọc cả dòng — vì phần cứng vẫn phải kéo cả dòng.
Bài học đo lường: CPU nạp theo DÒNG CACHE (128B = 32 int32), nên STRIDE LỚN PHÍ dòng cache. Đo (ma trận 64MB): duyệt theo HÀNG (stride 1, dùng 32/32 phần tử mỗi dòng) 0,211 ns/phần tử = 18,9 GB/s hữu ích; theo CỘT (stride 16KB, 1 phần tử/dòng, dùng 4/128 byte) 3,788 ns = 1,1 GB/s hữu ích = chậm 17,9x. Cột nạp ~32x byte dòng cache cho cùng số phần tử + TLB miss. 'Hàng hay cột như nhau' và 'đọc ít phần tử là nhanh' đều SAI — số BYTE dòng cache di chuyển mới quyết định. Nếu tin "hàng cột như nhau" tôi viết vòng duyệt cột chậm 18x; nếu tin "đọc ít là nhanh" tôi coi thường cái giá của truy cập thưa.
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 thứ tự bộ nhớ — chiều trong cùng khớp cách lưu. Với ma trận row-major (C/C++, numpy mặc định), chỉ số cột phải ở vòng trong cùng; với column-major (Fortran, một số thư viện), ngược lại. Đây là tối ưu "miễn phí": chỉ đổi thứ tự hai vòng lặp, tăng tốc chục lần cho các thao tác duyệt toàn ma trận.
Hệ quả thứ hai: khi buộc phải truy cập ngang thớ, dùng chuyển vị hoặc chặn khối (tiling). Nếu thuật toán cần cả duyệt hàng lẫn cột (như nhân ma trận), chuyển vị một ma trận trước, hoặc chặn (blocking/tiling) — xử lý từng khối nhỏ vừa cache để tái dùng mỗi dòng cache nạp về nhiều lần trước khi nó bị đẩy ra. Đây là lý do các thư viện BLAS nhanh: chúng sắp lại truy cập để không phí dòng cache.
Hệ quả thứ ba là tinh thần đo lường: đơn vị chi phí là dòng cache di chuyển, không phải phần tử chạm — và stride quyết định bạn dùng hay phí mỗi dòng. Con số mang theo: stride lớn (duyệt cột) phí ~31/32 mỗi dòng cache -> chậm ~18x duyệt liền (đo: 3,79 vs 0,21 ns/phần tử); băng thông hữu ích sụp (1,1 vs 18,9 GB/s). Duyệt theo thứ tự bộ nhớ; chuyển vị/tiling khi buộc truy cập ngang. Cùng một O(n²), cùng số phần tử, mà thứ tự truy cập đặt bạn vào một trong hai thế giới nhanh chậm cách nhau gần hai chục lần — đo mới thấy dòng cache trừng phạt bước lớn thế nào.
Thử ba mươi giây
Cấp một ma trận vuông lớn hơn cache nhiều (ví dụ 4096×4096 số int, 64 MB), lưu phẳng row-major, rồi cộng tất cả phần tử hai cách và bấm giờ ns mỗi phần tử. Một: theo hàng, for r: for c: s += m[r*N + c] — chỉ số trong cùng chạy liền (stride 1). Hai: theo cột, for c: for r: s += m[r*N + c] — mỗi bước nhảy cả một hàng (stride N). Bạn sẽ thấy bản theo cột chậm cả chục lần dù đúng cùng số phép cộng — vì mỗi phần tử cột rơi vào một dòng cache riêng, CPU nạp 128 byte mà chỉ dùng 4. Rồi thử chuyển vị ma trận trước khi duyệt cột: tốc độ trở lại như duyệt hàng. Ba mươi giây đó cho bạn thấy điều mà "cùng số phần tử thì cùng thời gian" giấu đi: bộ nhớ chuyển theo dòng, không theo phần tử, và một bước nhảy lớn biến mỗi lần chạm thành một dòng cache gần như bỏ phí — thứ tự bạn đi qua dữ liệu quan trọng ngang, hay hơn, việc bạn chạm bao nhiêu.
