Hình dung một cái tủ thuốc nhiều ngăn kéo, mỗi ngăn chứa 32 lọ. Muốn lấy một lọ, bạn buộc phải kéo cả ngăn ra. Nếu 32 lọ bạn cần nằm gọn trong một ngăn, một cú kéo là xong. Nhưng nếu mỗi lọ nằm ở một ngăn khác nhau, bạn phải kéo ra 32 cái ngăn, mỗi ngăn chỉ lấy đúng một lọ rồi đẩy vào — cùng số lọ, nhưng công sức gấp mấy chục lần. Cache của CPU vận hành đúng như cái tủ đó, và bài này đo xem cái giá của việc "lấy rải rác" nặng đến đâu.

Chuyện bắt đầu từ một tình huống ai cũng gặp: 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ự đi qua. Trực giác bảo chúng phải chạy như nhau. Đo thì bản theo cột chậm gần hai chục lần. Thủ phạm là 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" giấu đi hoàn toàn.

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ử — đúng như cái ngăn kéo 32 lọ. 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. 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 là 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 cả một hàng — mỗi phần tử cách nhau một hàng, rơi vào một dòng cache khác, và nếu hàng đủ lớn thì còn rơi vào 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 cả ở 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.

Con số làm tôi thấy thấm nhất là chỗ băng thông. 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 khoảng 34 GB/s dòng cache — chỉ là hầu hết bị lãng phí. Nghĩa là cái máy không hề "nghỉ ngơi" trong lúc chạy chậm; nó è cổ kéo đúng lượng byte như khi chạy nhanh, nhưng phần lớn đổ đi. Cùng số phần tử, cột buộc CPU nạp gấp khoảng 32 lần số byte dòng cache, cộng thêm lỗi TLB vì stride 16 KB vượt trang nhớ.

Hai trực giác bị đo cho gãy

Tôi vào đo với trực giác thuật toán thuần túy: "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". Con số nói thẳng: cột chậm 17,9 lần hàng, chỉ vì 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 đúng 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 nó lên hàng chục lần.

Nhưng đo cũng đập một trực giác ngược lại, tinh vi hơn, mà tôi cũng từng tin: "đọc ít phần tử thì nhanh; truy cập thưa 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. Thứ 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 một 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 ra dù bạn chỉ thèm 4 byte trong đó.

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

Điều đầu tiên gần như là một món quà: 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 nằm ở 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 gần như miễn phí: chỉ đổi chỗ hai dòng for, code nhanh lên cả chục lần cho các thao tác duyệt toàn ma trận. Ít có thay đổi nào rẻ mà lãi đậm như vậy.

Điều 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 chính là lý do các thư viện BLAS nhanh khủng khiếp: chúng sắp lại truy cập để không phí dòng cache.

Và cái bẫy này không nằm yên trong C. Nó theo lên mọi tầng, chỉ đổi tên. numpy hay pandas: cộng theo axis ngược với cách mảng lưu là bạn đang duyệt cột trên một mảng row-major — cùng cú sập băng thông này, chỉ ẩn dưới một lời gọi hàm trông vô hại. Java lưu mảng hai chiều thành mảng-của-mảng, a[i][j], nên duyệt j ở vòng trong mới liền bộ nhớ; đảo lại là đập cache y hệt. Còn phía database thì cả một cuộc cách mạng dựa trên đúng nguyên lý này: khi truy vấn phân tích chỉ cần vài cột, kho dữ liệu cột (columnar — Parquet, ClickHouse) thắng đậm kho dòng vì nó đặt các giá trị cùng cột nằm liền nhau trong bộ nhớ, biến "quét một cột" từ kiểu duyệt-cột-phí-dòng thành kiểu duyệt-liền-mạch. 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.

Muốn tự thấy thì 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 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 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, có khi hơn, việc bạn chạm bao nhiêu.