Hình dung bạn tính một con số trên bảng trắng rồi viết nó lên đó, để ba chỗ sau cần chỉ việc liếc lại thay vì tính lại từ đầu — hợp lý, khỏi phí công. Nhưng nếu giữa hai lần liếc, có khả năng ai đó lén xóa bảng và ghi số khác, thì con số cũ không còn tin được: bạn buộc phải tính lại cho chắc. Trình biên dịch đối xử với những biểu thức lặp lại y hệt — nó vui vẻ tính một lần rồi tái dùng, trừ khi nó không dám chắc giá trị còn nguyên. Và cái ranh giới "có ai xóa bảng không" hóa ra mới là chỗ đáng để tâm, chứ không phải việc bạn có tự tay lưu biến tạm hay không.

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 đo trong container gcc:13 (ARM) 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: 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 — đúng con số viết sẵn trên bảng.

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à chỗ tôi nhầm: 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 — đúng cảnh ai đó xóa bảng giữa hai lần liếc. 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), tức lời hứa "cái bảng này của riêng tôi, không ai xóa". 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ề đến code hằng ngày

Điều đầ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 biểu thức 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.

Điều 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".

Và đây là chỗ đáng nhớ, vì CSE là một trong những tối ưu mà các tầng cao làm mạnh hơn C nhiều, nhờ chúng biết nhiều hơn về aliasing. JIT của JVM CSE rất tích cực, và vì mô hình bộ nhớ Java kiểm soát chặt hơn con trỏ trần, nó thường chứng minh được "không đổi" ở những chỗ C phải bó tay — nhưng đổi lại, một trường volatile hay một lời gọi synchronized là bức tường tuyệt đối chặn CSE, vì đó là điểm đồng bộ. Rực rỡ nhất là CSDL: bộ tối ưu truy vấn có hẳn bước common subexpression / common table expression — một WITH hay một subquery lặp lại được tính một lần rồi tái dùng, đúng CSE nâng lên tầm bảng dữ liệu. Và bài học aliasing cũng lặp lại: một hàm có tác dụng phụ trong mệnh đề WHERE chặn bộ tối ưu gộp, y như phép ghi qua con trỏ chặn CSE. Mẫu số chung: "tính một lần dùng lại" là tối ưu phổ quát ở mọi tầng, và thứ quyết định nó có chạy được không luôn là cùng một câu hỏi — giữa hai lần dùng, có gì có thể đã đổi giá trị không; loại bỏ được sự mơ hồ đó (bằng restrict, bằng kiểu bất biến, bằng hàm thuần) là mở khóa cho máy tối ưu.

Muốn tự thấy thì 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.