Bạn viết a = x*y + z; rồi vài dòng sau b = x*y * 2;. Phép x*y xuất hiện hai lần — máy có tính nó hai lần không? Nhiều người được dạy: "lưu vào biến tạm t = x*y rồi dùng t cho khỏi tính lại". Đó chính là loại biểu thức con chung (Common Subexpression Elimination — CSE), một tối ưu mà trình biên dịch làm sẵn. Câu hỏi tôi mang vào: tự tay lưu tạm có nhanh hơn không, và khi nào thì CSE không xảy ra? Tôi vào đo với một niềm tin sai và tìm ra chỗ mà lưu tạm mới thật sự có ích.
Tính một lần, dùng lại
CSE dựa trên một quan sát đơn giản: nếu cùng một biểu thức được tính nhiều lần và giá trị của nó không đổi giữa các lần, thì tính một lần rồi tái dùng là đủ. Với:
a = x*y + z;
b = x*y * 2;
c = x*y - z;
x*y xuất hiện ba lần với cùng x, y không đổi, nên compiler tính nó một lần, giữ trong một thanh ghi, và hai chỗ sau chỉ đọc lại. Tôi xác nhận điều này trong container gcc:13 (ARM AArch64): hàm chứa ba lần x*y, biên dịch -O2, objdump cho thấy đúng một lệnh mul. Ba lần viết ra, một lần tính.
Vậy nếu tôi tự tay lưu t = x*y rồi dùng t? Tôi viết hai phiên bản — một bản lặp lại x*y ba lần, một bản lưu t — và so mã máy. Chúng giống hệt nhau (chỉ khác thứ tự toán hạng của một phép cộng giao hoán, add x0,x1,x2 so với add x0,x2,x1 — cùng nghĩa). Thời gian cũng bằng nhau: 0,683 so với 0,703 ns mỗi lần gọi, chênh trong khoảng nhiễu.
Đó là đo hớ của tôi: lưu tạm bằng tay không làm code nhanh hơn — compiler đã CSE rồi. Cái bạn được từ t = x*y chỉ là dễ đọc (một cái tên cho ý nghĩa), không phải tốc độ. Nhưng nếu dừng ở đây thì tôi đã bỏ lỡ ca thật sự quan trọng.
Khi CSE bị chặn: aliasing
CSE dựa trên giả định "giá trị không đổi giữa các lần dùng". Điều gì xảy ra khi giữa hai lần dùng có một phép ghi bộ nhớ, và compiler không chắc phép ghi đó có đổi giá trị biểu thức không? Xét:
long a = p[0]*p[1];
q[0] = 7; // ghi qua q
long b = p[0]*p[1]; // p[0], p[1] có còn như cũ?
Nếu q trỏ vào p[0] (aliasing — hai con trỏ cùng chỉ một ô nhớ), thì q[0] = 7 đã đổi p[0], và p[0]*p[1] lần hai khác lần đầu. Compiler không biết p và q có trùng không, nên để an toàn nó phải nạp lại p[0], p[1] và nhân lại. objdump xác nhận đúng vậy: hàm này có hai cặp lệnh nạp (ldp) và tính biểu thức hai lần. CSE bị chặn.
Cách gỡ là restrict — một lời hứa với compiler rằng p và q không bao giờ trùng (như bài strict aliasing đã bàn về giả định không chồng lấn). Với long *restrict p, long *restrict q, compiler tin q[0] = 7 không đụng tới p, nên p[0]*p[1] lần hai chắc chắn bằng lần đầu — CSE lại chạy: một lần nạp, một lần tính.
Với phép nhân, khác biệt thời gian nhỏ (nạp lại từ cache và nhân lại đều rẻ trên ARM này: 0,742 so với 0,737 ns). Nhưng khi biểu thức bị tính lại là phép đắt, cái giá hiện rõ. Đổi phép nhân thành phép chia:
chia lặp, con trỏ có thể trùng : 2 lệnh sdiv -> 0,975 ns
chia lặp + restrict : 1 lệnh sdiv -> 0,730 ns (nhanh 1,34 lần)
restrict nhanh 1,34 lần vì nó cho phép CSE bỏ hẳn một phép chia. Đây mới là chỗ "lưu tạm" — hay đúng hơn là giúp compiler CSE — thật sự đáng: không phải khi bạn viết x*y hai lần trong một biểu thức thuần, mà khi một phép ghi bộ nhớ đứng giữa và aliasing ngăn compiler chắc chắn.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng lưu tạm vì tưởng nó nhanh — hãy lưu tạm vì nó rõ. t = x*y cho một cái tên có nghĩa và tránh lặp lại biểu thức dài, đó là lý do chính đáng. Nhưng đừng nghĩ bạn đang tối ưu: compiler CSE mọi biểu thức thuần trong một khối, mã sinh ra y hệt. Viết cho người đọc; tốc độ đã có -O2 lo. Điều này cũng đúng với các biểu thức chung phức tạp hơn — một chỉ số mảng lồng như arr[i*n+j] dùng nhiều lần trong một khối cũng được compiler tính phần i*n+j một lần, bạn không phải tự tách ra một biến idx.
Hệ quả thứ hai: aliasing, không phải cú pháp, mới quyết định CSE có xảy ra. Khi biểu thức đọc bộ nhớ và giữa các lần dùng có ghi qua con trỏ khác, compiler buộc phải giả định xấu nhất (có thể trùng) và tính lại. Đây là chi phí ẩn trong nhiều vòng xử lý mảng: một phép ghi vào mảng đích chặn compiler tái dùng giá trị đọc từ mảng nguồn. Nếu bạn biết chúng không trùng, restrict mở lại cả một loạt tối ưu — CSE, và cả những tối ưu khác phụ thuộc "giá trị bộ nhớ không đổi".
Hệ quả thứ ba là bài học đo lường: cùng một tối ưu có thể vô hình hoặc rất đáng, tùy nó chặn phép rẻ hay phép đắt. CSE một phép nhân trên ARM này gần như không đổi đồng hồ; CSE một phép chia thì thấy ngay 1,34 lần. Trước khi nhọc công "giúp compiler", hãy hỏi biểu thức bị tính lại có đắt không — và đo. Con số mang theo: compiler tự CSE mọi biểu thức chung trong một khối thuần (x*y ba lần → một lệnh mul, bản viết lặp và bản lưu tạm sinh mã giống hệt, thời gian bằng nhau) nên lưu tạm bằng tay chỉ để dễ đọc; nhưng ghi qua con trỏ có thể trùng (aliasing) chặn CSE — objdump thấy hai phép chia thay vì một, và restrict khôi phục CSE cho phép đắt nhanh 1,34 lần. Aliasing quyết định, và cái giá tùy phép rẻ hay đắt.
Thử ba mươi giây
Viết long f(long*p,long*q){ long a=p[0]*p[1]; q[0]=1; long b=p[0]*p[1]; return a+b; } rồi gcc -O2 -S -o - t.c, tìm f: và đếm số lệnh mul (hoặc ldp) — bạn sẽ thấy hai, vì q có thể trùng p. Giờ thêm restrict: long f(long*restrict p,long*restrict q), biên dịch lại — số lệnh rớt xuống một. Bạn vừa tận mắt thấy aliasing chặn CSE, và một từ khóa mở lại nó. Thử đổi p[0]*p[1] thành p[0]/p[1] để thấy khác biệt còn rõ hơn ở phép chia — cùng lúc hiểu vì sao restrict đáng giá đúng ở những vòng đọc-ghi bộ nhớ nặng.
