Một mảng hai chiều trong C lưu theo hàng (row-major): các phần tử của cùng một hàng nằm liền nhau trong bộ nhớ. Điều đó khiến thứ tự hai vòng lồng khi duyệt mảng trở nên quan trọng bậc nhất: cùng một phép tính, đổi thứ tự vòng trong với vòng ngoài, và 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ự không? Tôi đo, và câu trả lời có một nửa 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 được 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 một phần tử rồi bỏ; cache-miss gần như mỗi bước.
Tôi đo trong container gcc:13 (AArch64): 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), 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 thứ tự 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 compiler làm hộ". gcc có một pass tên loop-interchange (đổi 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ờ: -O3 tự đổi 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ắn 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 đổi thứ tự duyệt không đổi kết quả — compiler chứng minh được là an toàn và cứ thế đổi.
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ỗ đo hớ của tôi được sửa 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 đổi thứ tự — cột-trong vẫn chậm 11,1 lần. Vì sao? Vì với số thực, đổi 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ự). Đổi 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ừ một con số 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 bài học đo hớ đầy đủ: 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: 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 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 đổi 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ì sao điều này quan trọng khi lập trình
Hệ quả đầ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 và 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.
Hệ quả thứ hai: hiểu vì sao một tối ưu kích hoạt hay không — thường là vì đúng đắn, không phải vì 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.
Hệ quả thứ ba là bài học đo lường bao trùm: đo ở đúng kiểu dữ liệu và đúng mức tối ưu bạn sẽ ship. Con số mang theo: thứ tự vòng lồng quyết định stride và do đó cache — cột-trong chậm 16,9 lần hàng-trong (số nguyên, -O2); -O3 có loop-interchange bật mặc định TỰ sửa thứ tự xấu cho SỐ NGUYÊN (về 1,0×; tắt -fno-loop-interchange thì 17,8× trở lại), nhưng KHÔNG sửa cho FLOAT (11,1× còn nguyên) vì đổi thứ tự cộng làm đổi làm tròn — chỉ -ffast-math mới cho, và khi đó tổng đổi giá trị. Compiler có thể cứu locality, nhưng chỉ trong giới hạn đúng đắn — viết đúng thứ tự vẫn là việc của bạn.
Thử ba mươi giây
Viết hai vòng cộng một ma trận int A[N][N]: một bản for(i) for(j) s+=A[i][j] và một 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 đã đổi 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. Ba mươi giây (well, vài phút vì ma trận lớn) đó 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 đó.
