Một hàm ba phép nhân, gcc rút thành đúng một con số nạp sẵn — nếu tôi cho nó biết đầu vào

Hình dung một đầu bếp nấu tiệc. Nếu biết trước chính xác bao nhiêu khách, anh ta tính sẵn mọi định lượng ở nhà — bao nhiêu gạo, bao nhiêu thịt — rồi in ra một tờ danh sách hoàn chỉnh, tới nơi chỉ việc lấy đúng số đã ghi. Nhưng nếu khách "tới mới biết", anh ta phải đứng đó nhân chia lại từng món mỗi lần có người vào. Cùng công thức, cùng phép tính; khác nhau duy nhất ở chỗ con số có biết trước hay không. Trình biên dịch làm đúng anh đầu bếp đó với code của bạn, và cái "tính sẵn ở nhà" ấy mạnh hơn nhiều so với cái ai cũng biết là 2 + 3 thành 5.

Tối ưu này gọi là gấp hằng số (constant folding), và nó đi xa hơn nhiều những phép cộng hiển nhiên. Kết hợp với người anh em lan truyền hằng (constant propagation), nó có thể lấy cả một hàm phức tạp và, nếu đầu vào là hằng số, biến toàn bộ thành một con số nạp sẵn — tính toán biến mất khỏi lúc chạy. Tôi đo cái biến mất đó trong container gcc:13 (ARM) bằng đồng hồ và mã máy.

Gấp hằng và lan truyền: hai bước đi cùng

Gấp hằng số là việc trình biên dịch tính mọi biểu thức chỉ gồm hằng số ngay lúc biên dịch, thay bằng kết quả. Viết 3600 * 24 * 365 thì mã máy chứa thẳng 31536000, không có phép nhân nào lúc chạy — bạn được viết công thức cho dễ đọc mà không trả giá tốc độ.

Lan truyền hằng là bước đi kèm, và là chỗ nó trở nên mạnh. Nếu trình biên dịch biết chắc một biến mang giá trị hằng — bạn gán int k = 100, hay một tham số được truyền hằng số vào một hàm đã inline — nó thay mọi lần dùng k bằng 100. Mà khi k đã thành 100, các biểu thức chứa k giờ toàn hằng, nên gấp hằng lại nhảy vào tính tiếp. Hai bước lặp qua lại: lan truyền tạo ra hằng mới, gấp hằng tính chúng, lộ ra hằng mới hơn nữa, lan truyền tiếp... cho tới khi không còn gì để gấp. Kết quả có thể ngoạn mục hơn nhiều so với 2 + 3.

Đo: một hàm phức tạp rút thành một con số

Tôi viết một hàm f(k) làm việc thật: ba phép nhân 64-bit, vài phép xor và dịch bit trộn lẫn. Rồi tôi gọi nó hai cách. Cách thứ nhất, all_const(), gọi f(100) — k là hằng số 100 viết thẳng trong mã. Cách thứ hai, runtime_val(), gọi f(*pv) với pv trỏ tới một biến volatile — giá trị chỉ biết lúc chạy. Nhìn mã máy hai hàm:

Cùng hàm f() (3 phép nhân + xor + dịch), gcc -O2, mã máy:
  all_const   (k = 100 hằng)     :  5 lệnh, 0 phép nhân
  runtime_val (k từ volatile)    : 22 lệnh, 3 phép nhân

Hàm all_const chỉ còn 5 lệnh và không một phép nhân nào. Mở nó ra, toàn bộ thân hàm là bốn lệnh mov/movk nạp một số 64-bit rồi ret — trình biên dịch đã lan truyền k = 100 xuyên qua cả hàm, gấp hết ba phép nhân và mọi phép trộn, tính ra kết quả cuối cùng lúc biên dịch, và nhét nó vào mã dưới dạng một hằng số literal. Đúng tờ danh sách tính sẵn ở nhà. Còn runtime_val giữ nguyên 22 lệnh với 3 phép nhân — vì k đến từ volatile, trình biên dịch không biết giá trị của nó, buộc phải sinh mã tính đủ f() mỗi lần gọi. Và thời gian:

Thời gian mỗi lời gọi:
  all_const   (k = 100 hằng)  : 0,000 ns
  runtime_val (k từ volatile) : 0,992 ns

Bản hằng số chạy 0 nano giây — không phải vì nó nhanh, mà vì không còn gì để chạy: kết quả đã có sẵn dưới dạng một literal. Bản runtime tốn ~1 ns thật để làm ba phép nhân mỗi lần. Cùng một hàm, cùng một trình biên dịch, khác biệt duy nhất là đầu vào có phải hằng số biết trước lúc biên dịch hay không.

Cú vấp: lan truyền hằng đi xa hơn tôi tưởng

Định kiến của tôi là "trình biên dịch chỉ gấp những biểu thức hằng hiển nhiên như 2 + 3 hay 3600 * 24". Con số bác bỏ điều đó: nó lan truyền hằng rất xa — đẩy giá trị 100 xuyên qua một hàm với ba phép nhân, xor, dịch bit, tính sẵn toàn bộ thành một literal duy nhất. Đây không phải "gấp một biểu thức", mà là "thực thi cả một đoạn chương trình lúc biên dịch". Trình biên dịch, khi biết đủ, có thể chạy giúp bạn phần tính toán ngay khi dịch, để lúc chạy chỉ còn việc đọc kết quả.

Nhưng — và đây là mặt còn lại của bài học — phép màu này dừng ngay khi chạm một giá trị "chạy mới biết". Chỉ cần k đến từ một nguồn mà trình biên dịch không thể biết trước — đọc từ file, từ argv, từ mạng, hay từ một biến volatile như trong đo của tôi — thì cả chuỗi lan truyền sụp đổ: không có hằng số nào để đẩy đi, không có gì để gấp, và toàn bộ tính toán phải sinh ra để chạy thật (22 lệnh, 3 phép nhân, ~1 ns). Đúng cảnh khách tới mới biết, đành tính tại chỗ. Ranh giới giữa "0 ns" và "tính đủ" không nằm ở độ phức tạp của phép tính, mà ở một câu hỏi duy nhất: trình biên dịch có biết giá trị này lúc dịch không?

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

Điều đầu tiên, rất thực dụng: viết hằng số dưới dạng biểu thức dễ đọc, đừng tự "tối ưu" bằng tay. 60 * 60 * 24 rõ ràng hơn 86400, và trình biên dịch gấp nó thành cùng một literal — bạn được cả sự rõ ràng lẫn tốc độ. Tự tính sẵn 86400 chỉ làm code khó đọc mà không nhanh hơn một nano giây nào. Cùng vậy với các hằng cấu hình: khai báo const int BUFSIZE = 4096; ... BUFSIZE * 8 và để trình biên dịch lo phần số học.

Điều thứ hai giải thích vì sao inline và hằng số là cặp bài trùng. Như bài inline đã đo, lợi lớn của inline không phải bỏ lệnh call mà là mở khóa tối ưu xuyên biên — và tối ưu xuyên biên số một chính là lan truyền hằng. Khi bạn gọi một hàm với đối số hằng (một cờ, một kích thước, một chế độ), inline đưa hằng đó vào thân hàm, lan truyền hằng chuyên biệt hóa thân hàm cho đúng chỗ gọi, gấp hằng và khử mã chết dọn phần thừa. Đó là lý do một hàm tổng quát gọi với tham số hằng thường sinh ra mã ngắn gọn đến bất ngờ.

Và đây là chỗ đáng nhớ, vì "dời tính toán sang càng sớm càng tốt" là một nguyên lý vượt xa gấp hằng số của C. JVM làm phiên bản runtime của nó: JIT quan sát một giá trị thực tế không đổi (một trường static final, một cấu hình đọc một lần) rồi coi nó như hằng và gấp các biểu thức phụ thuộc — constant folding lúc chạy, thứ compiler tĩnh không làm được vì giá trị chưa biết lúc dịch. Rust và C++ đẩy theo hướng ngược: const fn/constexpr cho phép bạn yêu cầu chạy cả hàm lúc biên dịch (bài sau sẽ đo). Ở tầng hệ thống, đây chính là tinh thần của precompute/materialized view: CSDL tính sẵn kết quả một truy vấn hay gợi ý và lưu lại, để lúc đọc chỉ việc lấy — cùng ý "làm sớm phần biết trước". Mẫu số chung: mọi tính toán mà kết quả đã cố định đều nên bị đẩy tới thời điểm sớm nhất có thể (biên dịch, nạp lớp, dựng view) để lúc nóng chỉ còn đọc — và cách rẻ nhất để mở khóa nó là cho hệ thống biết giá trị đó là cố định, đừng che nó sau một lớp mờ đục.

Muốn tự thấy thì viết uint64_t f(uint64_t k){ return k*k*k + k*7 - 3; } và một hàm gọi nó với hằng: uint64_t g(){ return f(1000); }. Biên dịch gcc -O2 -S -o out.s file.c rồi tìm hàm g: bạn sẽ thấy nó không có phép nhân nào, chỉ nạp một con số — trình biên dịch đã tính 1000³ + 7000 - 3 giúp bạn. Giờ đổi g thành nhận tham số g(uint64_t k){ return f(k); } và xem lại: phép nhân xuất hiện, vì k không còn là hằng. Ba mươi giây đó cho bạn thấy ranh giới compile-time/runtime bằng mắt — và vì sao "cái gì biết trước thì để trình biên dịch tính".