Hình dung một tủ hồ sơ nhiều ngăn kéo, mỗi ngăn là một hàng giấy tờ xếp sát nhau. Cần lấy cả một hàng, bạn kéo một ngăn ra rồi rút lần lượt — nhanh gọn. Nhưng nếu bạn cần lấy "tờ thứ ba của mỗi ngăn", bạn phải mở ngăn này, rút một tờ, đóng lại, mở ngăn kế, rút một tờ, đóng lại... Cùng số tờ giấy, nhưng cách thứ hai tốn công gấp bội chỉ vì bạn đi ngang qua cách bộ nhớ được sắp xếp. Mảng hai chiều trong C lưu theo hàng đúng như cái tủ đó, và thứ tự hai vòng lồng khi bạn duyệt nó quyết định bạn đang rút giấy theo ngăn, hay đang mở-đóng ngăn liên tục.

Cụ thể: các phần tử của cùng một hàng nằm liền nhau trong bộ nhớ (row-major). Nên thứ tự hai vòng lồng trở nên quan trọng bậc nhất — cùng một phép tính, đổi vòng trong với vòng ngoài, bạn có thể nhanh gấp chục lần hoặc chậm đi chục lần. Câu hỏi thực tế: chênh lệch đó lớn cỡ nào, và compiler có tự sửa giúp khi bạn viết sai thứ tự? Tôi đo trong container gcc:13 (AArch64), và câu trả lời có một nửa làm tôi bất ngờ.

Thứ tự vòng quyết định bước truy cập

Duyệt một ma trận A[i][j] có hai cách. Hàng-trong (for i { for j {...} }): vòng trong chạy theo j, tức theo chiều các phần tử liền nhau trong bộ nhớ — bước (stride) 1. Mỗi lần một dòng cache (64 byte) được nạp về, cả 16 số nguyên trong đó đều dùng ngay, đúng như căn lề dữ liệu và dòng cache mô tả. Cột-trong (for j { for i {...} }): vòng trong chạy theo i, mỗi bước nhảy qua cả một hàng — bước N. Mỗi truy cập rơi vào một dòng cache khác, dùng đúng một phần tử rồi bỏ; cache-miss gần như mỗi bước. Đúng cảnh mở-đóng ngăn kéo liên tục.

Tôi cộng tổng một ma trận số nguyên 4096×4096 (64 MB, lớn hơn cache rất nhiều), theo hai thứ tự vòng.

-O2, hàng-trong (stride 1) : 0,2116 ns/phần tử
-O2, cột-trong  (stride N) : 3,5861 ns/phần tử   -> chậm 16,9 lần

16,9 lần — chỉ vì đổi chỗ hai dòng for. Đây là một trong những khác biệt hiệu năng lớn nhất mà một thay đổi nhỏ code có thể gây ra, và nó thuần túy là chuyện cache.

Một nửa bất ngờ: compiler cứu được số nguyên

Tôi vào đo với niềm tin: "compiler không tự sửa nổi thứ tự vòng xấu — locality là chuyện bạn phải tự viết đúng, đừng mong nó làm hộ". gcc có một pass tên loop-interchange (đảo thứ tự vòng), nhưng tôi đoán nó hiếm khi kích hoạt vì điều kiện an toàn chặt. Đo lại ở -O3:

-O3, cột-trong (số nguyên) : 0,2118 ns/phần tử   -> 1,0× (bằng hàng-trong!)

Bất ngờ thật: -O3 tự đảo thứ tự vòng cột-trong thành hàng-trong, xóa sạch cái phạt 16,9 lần. Để chắc chính pass đó làm việc, tôi tắt nó: -O3 -fno-loop-interchange — và cột-trong chậm trở lại 17,8 lần. Vậy đúng là loop-interchange (bật mặc định ở -O3) đã cứu tôi. Với số nguyên, phép cộng có tính kết hợp, nên đảo thứ tự duyệt không đổi kết quả — compiler chứng minh được là an toàn và cứ thế đảo.

Nửa còn lại: với float, compiler không dám

Nhưng câu chuyện chưa xong, và đây là chỗ tôi phải sửa lại chính mình theo cả hai chiều. Tôi đổi ma trận sang số thực float và đo lại ở -O3:

-O3, hàng-trong (float) : 0,5651 ns/phần tử
-O3, cột-trong  (float) : 6,2510 ns/phần tử   -> chậm 11,1 lần

Lần này -O3 không đảo thứ tự — cột-trong vẫn chậm 11,1 lần. Vì sao? Vì với số thực, đảo thứ tự cộng làm đổi kết quả: phép cộng dấu phẩy động không có tính kết hợp (làm tròn ở mỗi bước phụ thuộc thứ tự). Đảo thứ tự duyệt ma trận nghĩa là cộng các số theo trình tự khác, ra một tổng làm tròn khác — compiler coi đó là đổi hành vi quan sát được nên không dám interchange. Chỉ khi tôi cho phép bằng -ffast-math:

-O3 -ffast-math, cột-trong (float) : 0,1261 ns/phần tử   -> 1,0×

Interchange lập tức kích hoạt, cột-trong nhanh bằng hàng-trong. Nhưng có cái giá thật: tổng tính ra đổi giá trị (biến sink của tôi nhảy từ con số này sang con số khác) — đúng như ffast-math đã cảnh báo, bạn đổi độ chính xác lấy tốc độ. Vậy hóa ra niềm tin "compiler không cứu" của tôi đúng một nửa và sai một nửa: nó có cứu số nguyên (tôi đã đánh giá thấp nó), nhưng không cứu float (vì ràng buộc đúng đắn), và ranh giới nằm ở một chỗ tinh vi bất ngờ — tính kết hợp của phép cộng. Cùng một cấu trúc vòng, compiler hành xử khác hẳn chỉ tùy kiểu dữ liệu.

Thứ tự vòng còn quyết định vector hóa

Cache-miss không phải hậu quả duy nhất của thứ tự sai. Thứ tự vòng còn quyết định compiler có vector hóa được không. Vòng hàng-trong (stride 1) nạp các phần tử liền nhau, nên compiler gói được 4 hay 8 phần tử vào một thanh ghi vector và cộng một lần — đó là một phần lý do bản hàng-trong nhanh tới 0,21 ns. Vòng cột-trong (stride N) truy cập rời rạc, không gói vector được: compiler buộc phải xử lý từng phần tử một, cộng thêm chi phí lệnh bên cạnh cái phạt cache. Nghĩa là thứ tự xấu bị phạt hai lần — vừa mất locality cache, vừa mất vector hóa. Khi -O3 interchange được (số nguyên), nó khôi phục cả hai: cột-trong sau khi thành hàng-trong lại vector hóa được và chạm dòng cache tuần tự. Đây là lý do một lần đổi thứ tự vòng có thể mang lại khác biệt cả chục lần chứ không phải vài phần trăm.

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

Điều đầu tiên: viết đúng thứ tự vòng ngay từ đầu — đừng ỷ vào compiler. Với số nguyên ở -O3 bạn có thể may mắn được interchange cứu, nhưng với float, hay ở -O2, hay khi vòng có phụ thuộc dữ liệu phức tạp, compiler sẽ không sửa và cái phạt chục lần là của bạn. Quy tắc đơn giản mà luôn đúng: cho vòng trong chạy theo chiều bộ nhớ liền nhau (chỉ số cuối của mảng row-major), để mỗi dòng cache được dùng hết.

Điều thứ hai: hiểu vì sao một tối ưu kích hoạt hay không — thường là vì đúng đắn, chứ không phải compiler lười. Loop-interchange không đổi float không phải vì gcc yếu, mà vì đổi sẽ cho kết quả khác. Đây là mẫu chung: rất nhiều tối ưu (interchange, vector hóa reduction, kết hợp lại) bị chặn bởi ngữ nghĩa dấu phẩy động, và bạn mở khóa chúng bằng -ffast-math nếu chấp nhận sai số — một quyết định có ý thức, không phải mặc định.

Và cái nguyên tắc "duyệt theo chiều dữ liệu nằm" vượt xa C. Java lưu mảng int[][] thực ra là mảng-của-mảng, nhưng vòng for i { for j { a[i][j] }} vẫn thắng vòng ngược lại vì đi dọc từng hàng liền khối — và các thư viện ma trận nặng như ND4J hay JBLAS đều gọi xuống BLAS được viết cache-blocking chính vì lẽ đó. Go, Rust, NumPy cùng câu chuyện: NumPy còn cho bạn chọn order='C' (row-major) hay order='F' (column-major) và hiệu năng đảo chiều theo đúng thứ tự bạn duyệt. Rõ nhất là CSDL: một index chỉ nhanh khi câu query đi theo thứ tự nó sắp, và một composite index (a,b) giúp WHERE a=? ORDER BY b nhưng gần như vô dụng cho WHERE b=? — đúng y chuyện stride, chỉ đổi tên. Mẫu số chung ở mọi tầng: dữ liệu nằm theo một trật tự, và bạn phải đi theo trật tự đó; đi ngang qua nó luôn phải trả giá, dù là cache-miss hay full-scan.

Muốn tự thấy thì viết hai vòng cộng ma trận int A[N][N]: bản for(i) for(j) s+=A[i][j] và bản for(j) for(i) s+=A[i][j], với N=4096. Đo ở -O2 — bản cột-trong sẽ chậm hơn chục lần. Giờ đo lại ở -O3 — chúng gần như bằng nhau, vì compiler đã đảo thứ tự. Rồi đổi int thành float và đo lại ở -O3: bản cột-trong lại chậm hẳn, vì giờ interchange bị chặn bởi ngữ nghĩa float. Vài phút đó (ma trận lớn nên không phải ba mươi giây thật) cho bạn thấy tận mắt: locality là vua, compiler là đồng minh có điều kiện, và kiểu dữ liệu quyết định điều kiện đó.